[VA] Short & Sweet Math Challenges #23: "May the 4th Be With You !" Special

[Jeff O.]

I'm guessing no one was expecting an update regarding further work on this, but a couple of recent things brought it back to my attention. First, the HHC 2019 programming contest was related, and second, Valentin's posting of his web site led me to re-read his challenge and my input. For posterity’s sake, I decided to go ahead and add my new work to the original thread. (Apologies in advance for the length of this post, brevity is not a strength of mine.)

As noted in my old post above, I ended up solving the sixth part of Valentin's challenge, with optimizations to reduce the search space, but with the knowledge that other portions of the program were decidedly not optimized. I was particularly dissatisfied with my method to determine if the digits in the sum of the digits to the n-th power were a permutation of the digits in the n-digit input number:

(06-22-2018 08:20 PM)Jeff O. Wrote:  I did this in what I am sure is a very clunky fashion:

- Break the number into its separate digits
- Sort the digits
- Reassemble into a number
- Compare to input number
- if equal, reverse the sum, that is the selfie
- if not equal, not a selfie, go back to create the next combination to check

As I said, I found the above dissatisfying, but the program worked, Valentin wrapped up the challenge, and I returned to the mundane tasks of everyday life.

After the HHC 2019 programming contest was presented, I realized that it was related to Valentin's challenge, limited to 3-digit numbers and eliminating the "selfie" constraint, i.e., just looking for 3-digit numbers whose digits to the 3rd power summed to the input number, not the reverse. After creating a brute-force method to solve the programming contest, I revisited my "selfie" program to see how it might be used. First I removed the few lines that did the "selfie" part, and it quickly found the four answers to the contest. Then somewhere along the line I re-read my old post, remembered my dissatisfaction and decided to see if I could improve on the previous version, especially the permutation identification part quoted above. When I originally worked on the problem, I tried to think of a better way to do it. Doing it manually, I envisioned something like the following process:

1. Write down both numbers
2. Pick a digit in the first number, look for it in the second
3. If a is match found, mark out the digit from each number, go back to step 2. If all digits get checked and matched, go to step 5. If they do not match, go to step 4.
4. If a match for any digit in the input number cannot be found in the second, the numbers cannot be permutations of each other.
5. All digits found and uniquely matched, so the numbers are permutations of each other.

For example, check 12345 against 34521

Pick the 5 from 12345, matches the 5 from 34521, strike out both, leaving 1234X vs. 34X21. These might be re-written as 1234 and 3421.

Now check the 4, leaving 123X vs. 3X21 or 123 vs. 321, and so on until checking 1 vs. 1, and thus finding the two starting numbers to be permutations of each other.

Now check 12745 vs. 34521.

As above, 5 matches 5, leaving 1274X vs. 34X21 (or 1274 vs. 3421), 4 matches 4, leaving 127XX vs. 3XX21 (127 vs. 321). The next time around, 7 is not found in 321, so we abort the check and declare that the originals are not permutations.

(I’m sure the above described procedure is quite simple and obvious to MoHPC Forum members, but I find it useful to spell out even the simple things, so I may remember them more readily in the future should the need arise.)

For the purposes of the following discussion, the “first” number is the sum of the digits of the input number to the n-th power, and the “second” number is the input number.

I think I considered the above method back in 2018 but got hung up on how I might check each digit and delete matches. It sounded like a lot of breaking, shifting and re-storing that did not immediately seem to be much if any better than my dissemble-sort-reassemble method. That’s when I dropped further work. When I returned to the problem recently, I revisited the above described manual procedure, and realized that rather than delete the digits as checked and repack to create new numbers, if I could find a way to identify that a match had been found and no longer check those digits, I would not need to reassemble at each step. It is relatively easy to extract single digits from the first number and create a number with one less digit, so each digit is eliminated from further checking at each step. For checking against the second, I determined that I did not need to eliminate the matches and reconstitute the second number without that digit, I just needed to make sure that a digit could not be matched again. So if a match is found, rather than delete and re-assemble, I changed that digit to a value that could not be a match to any further digits extracted from the original number. My input numbers were generated by the method I used (described below) as individual digits in sequential storage registers. So if a match was found, I stored pi in the register that held the matching digit. I was then free to check all future digits against all registers that represented the second number with no possibility that that digit could be matched again.

With a bit of work, I was able to implement the above method, and pleased to find that it worked quite well. The revised program is reduced to 120 steps compared to 143 of the original, plus the need for the separate 23 step SORT routine is eliminated. With the above major change and a couple of other improvements, the new version runs in less than half the time of the original. On my DM42, all selfies are found in 1 hour and 9 minutes vs. 2 hours 34 minutes of the original. With Free42 on my desktop, it finds them all in 18 seconds vs. 45 seconds for the original program.

I'm fairly happy with the improvement, but I may continue looking for refinements, as it is an enjoyable pastime. (edit - see below for an update to this post and the following post for a new method.)

Here is the code:

Code:

000        { 209-Byte Prgm }        
001        LBL "Σd↑n"          
002        11                  Steps 2 through 9...
003        STO 00              ...clear registers  1 through 11 and 20
004        0                   
005        STO 20              initialize register 20 which keeps track of number of digits in number
006        LBL 01              
007        STO IND 00          
008        DSE 00              
009        GTO 01              
010        LBL 02              Label 02, begin main routine
011        1.011               Store 1.011...
012        STO 00              ...for ISG to check digits
013        LBL 03              Label 3, check digits to see if they equal 9
014        9                   Enter 9
015        RCL IND 00          recall digit
016        X≠Y?                is it not equal 9?
017        GTO 04              if not, go to routine to increment
018        ISG 00              if equal to 9, increment counter to...
019        GTO 03              ...loop back to check next digit
020        STOP                if register 11 equal 9,  all unique combinations up to 99,999,999,999 have been checked
021        LBL 04              routine to increment registers
022        RCL 20              recall  number of digits
023        RCL 00              recall loop counter
024        IP                  take integer part since it has ISG target coded
025        X>Y?                is current digit pointer greater than current number of digits
026        STO 20              if so, store new number of digits
027        STO 00              store back in counter for DSE to increment registers
028        1                   Enter 1 
029        RCL+ IND 00         Recall and increment digit pointed to by counter
030        LBL 05              label  for loop to set all digits up to counter to new value
031        STO IND 00          store new value
032        DSE 00              decrement counter
033        GTO 05              loop back to store new value in next lower digit position
034        RCL 20              recall number of digits in current input number
035        STO 00              store for power to raise digits to form sum d^n
036        LBL 07              
037        RCL 00              Recall number of digits in input number, may be padded for inclusion of zeroes, use for power to raise digits to form sum d^n
038        RCL 20              recall number of digits in current input number
039        STO 18              store for loop index to form sum d^n.  Only sum digits greater than 1.
040        0                   
041        LBL 09              Label to sum d^n
042        RCL IND 18          
043        RCL 00              
044        Y↑X                 
045        +                   
046        DSE 18              
047        GTO 09              
048        STO 14              store sum d^n in register 14
049        LOG                 take common log
050        IP                  take integer part
051        1                   Enter 1 
052        +                   Add 1 to determine number of digits
053        RCL 00              recall number of digits
054        X≠Y?                digits in original not equal digits in sum d^n?
055        GTO 10              if not equal, cannot be selfie, skip all checks
056        LBL 08              Steps 56 through 64 copy the digits of the input number in registers 1 through 11 to registers 21 through 31.
057        RCL IND ST X        recall digit of input number (or of current digit position)
058        20                  enter 20 
059        RCL+ ST Z           add 20 to number of digits/digit position
060        X<>Y                
061        STO IND ST Y        store value of digit in position 1 through 11 in 21 through 31
062        RCL ST Z            
063        DSE ST X            
064        GTO 08              loop back to store next digit
065        CLA                 clear alpha register
066        FIX 00              Fix 0 to eliminate zeros after decimal for integers
067        CF 29               clear flag 29 to eliminate radix symbol display for integers, else it would get copied to alpha register
068        ARCL 14             copy sum d^n into alpha register
069        20.02               enter 20.02 
070        RCL+ 00             add to number of digits to form index for looping and store/recall
071        STO 15              store index
072        LBL 11              
073        RCL 15              recall index
074        STO 16              store for checking each digit
075        ATOX                move char# of leftmost digit of sum d^2 into X
076        X=0?                is it zero?
077        GTO 14              if zero, all digits shifted out, go to label indicating sum d^n is permutation of original
078        48                  
079        -                   subtract 48 to convert char# to actual digit
080        LBL 13              
081        RCL IND 16          recall digit of input number
082        X=Y?                are they equal
083        GTO 12              if so, go to label to mask digit for further checks
084        X<>Y                if not, swap to get digit back in X
085        DSE 16              decrement index
086        GTO 13              loop back to check next digit of original number
087        GTO 10              if all digits checked without match, go to label for sum d^n not a permutation
088        LBL 12              Label for steps to mask digits after successful match
089        PI                  enter Pi for value that cannot match any integer
090        STO IND 16          store in digit of original number that was matched
091        GTO 11              loop back to check next digit of sum d^n
092        LBL 14              Label for indication that sum d^n is permutation of original number
093        RCL 14              recall sum d^n
094        10                  enter 10
095        MOD                 determine rightmost digit
096        X=0?                is FP zero, i.e., was rightmost digit zero?
097        GTO 10              if so, cannot be selfie since reverse will be fewer digits, skip all checks
098        RCL 14              if not, recall sum d^n
099        STO- 14             store in reg 14 to clear it. (steps 98 through 109 reverse the digits in the number to produce selfie)
100        LBL 16              
101        FP                  take fractional part
102        STO+ 14             add to register holding reversed sum d^n
103        LASTX               recall input number
104        IP                  take integer part
105        0.1                 enter 0.1
106        STO÷ 14             divide current reversed number by 0.1 to shift left one digit
107        ×                   multiply input number by 0.1 to shift one digit right
108        X≠0?                is input number not zero, indicating more digits to shift?
109        GTO 16              if not zero, loop back to shift and add again
110        RCL 14              if zero, number has been reversed, recall reversed sum d^n
111        PRX                 print number for which d…d=reverse of sum d^n
112        LBL 10              routine to check if original number padded with zeroes to 11 digits have been checked
113        11                  enter 11
114        RCL 00              recall number of digits in original number (or padded with zeroes previously)
115        X=Y?                are they equal
116        GTO 02              if so, done checking original number and all padded with zero to 11 digits, go generate the next number
117        ISG 00              increment the number of digits
118        DEG                 no op
119        GTO 07              go back to sum d^(n+1)
120        END

My number generator generates the following sequence of numbers to check (read top to bottom, left to right):

Code:

 1    13    26     44     79    118    226    399     ...    3333         ...      111111111            ...
 2    14    27    ...     88    119    227    444     799     ...        9999            ...    39999999999
 3    15    28     49     89    122    228    ...     888    4444       11111     1111111111    44444444444
 4    16    29     55     99    ...    229    499     ...     ...         ...            ...            ...
 5    17    33    ...    111    188    233    555     899    5555       99999    11111111111    49999999999
 6    18    34     59    112    189    ...    ...     999     ...      111111            ...    55555555555
 7    19    35     66    113    199    288    599    1111    6666         ...    19999999999            ...
 8    22    36    ...    114    222    289    666     ...     ...     1111111    22222222222    59999999999
 9    23    37     69    115    223    299    ...    1999    7777         ...            ...    66666666666
11    24    38     77    116    224    333    699    2222     ...    11111111    29999999999            ...
12    25    39     78    117    225    ...    777    2999    8888         ...    33333333333    99999999999

In case it is not immediately apparent what is going on with the above sequence of numbers to check, a description of the procedure used to create the sequence is as follows:
1. Start with all 11 registers representing the (up to) 11 digit number set to zero.
2. Recall the digit in the ones position
3. Is it 9?
4. If not, increment it, the 11 registers now represent the next number. Check for sum d^n being a permutation, then return to step 2.
5. If it is equal to 9, check the digit to the left in the tens position.
6. Is it 9?
7. If not, increment it and also set the value in the ones position to that new value, the 11 registers now represent the number to be evaluated.
8. If it is equal to 9, check the digit to the left in the hundreds position.
9. Is it 9?
10. If not, increment it and also set the values in the tens and ones positions to that new value, the 11 registers now represent the next number to be evaluated.
11. If it is equal to 9, check the digit to the left in the thousands position.
12. And so on.

To be honest, I'm not quite sure how I arrived at the above method to create the sequence of numbers. It took me a while to figure out how it worked and what I was doing in my program again after 15 months. Probably some well-known technique that I stumbled upon.

The full listing of all numbers generated by the above procedure would include 167,959 numbers. The interested reader will likely notice that the above listing contains no numbers that include any zeros. Yet there are several numbers containing at least one zero which satisfy the goal that the digits of the n-digit number raised to the n-th power sum to the n-digit number itself. I developed and checked those as follows. After generating and checking each of the above numbers, I then padded them with zeros. So for a single digit number, say 5, I checked 5, 50, 500, 5000,…, 50 000 000 000. I did not raise the zeros to the higher powers, I only raised the original non-zero digits to the higher powers and summed those. This requires checking 11 numbers for every single-digit number in the above list, 10 numbers for every 2-digit number, 9 numbers for each 3-digit, etc. on up to 1 number for each 11-digit number in the above list. That increases the total count of the numbers needing to be checked to 352,704. Still quite a small fraction (0.0003527%) of the 99,999,999,999 numbers which would have to be checked via a brute-force method.

Last but not least, attached is a zipped raw file in case you would like to play with the program in Free42 or your DM42. If you would like to simply determine those n-digit numbers whose digits raised to the n-th power sum to themself, i.e., remove the selfie constraint (and who wouldn't?), delete steps 93 through 109.

Edit - as expected, I continued to attempt to improve my program. In an effort to speed it up, I developed a new way to determine the number of digits in the current number developed by my above described method. It appears to be only about 1% faster, so not as much improvement as I had hoped. But it is 6 steps shorter, so I would call it a better effort. I replaced the program listing above with the new version, and have attached a new zipped raw file. The original raw file is still attached for posterity.