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

[Jeff O.]

(10-24-2019 01:26 PM)Jeff O. Wrote:  ...but I may continue looking for refinements, as it is an enjoyable pastime. (edit - see below)

Obviously, I cannot leave well enough alone. Late last week, another approach to identify the “selfies” after summing the digits of the input number occurred to me. The new method replaces the “disassemble-sort-re-assemble” method of my much prior work, and the “check-and-mask-digit” method of my latest work. It occurred to me that after summing the digits to the nth power of my input number, all I had to do was sum the digits of that result to the n-th power and compare to the first sum of digits to the nth power. If they match, then I have found a selfie. (Actually a reverse of the selfie, which is then reversed to give the selfie after checking for a trailing zero.). My logic for this was as follows:

1. Let the digits^n of n-digit number A sum to n-digit number B
2. Let the digits^n of n-digit number B sum to n-digit number C
3. If B=C, then the digits^n of n-digit number C must also sum to n-digit number B
4. Therefore, number C (and B, of course) must contain the same digits as number A, i.e., is a permutation of the digits in A.

No. 4 is a conjecture, not an assertion. I guess I hoped that there was some well-known proof that the sum of n digits to the nth power is unique if it sums to an n-digit number. I had no reason to think there was such a proof, but a guy can hope, right? I exchanged a PM with Valentin, he quickly found some cases where a given number can be generated by more than one combination of digits to a power, so I assume my hoped-for proof does not exist.

But, absent the desired proof, I believe the worst that could happen is that my algorithm would find a given solution more than once, i.e. I don't think any solutions would be missed. That is based on the following reasoning. I’m fairly confident that my method checks one (and only one) example of each possible combination of n digits. So let’s say that an n-digit number produces a sum of d^n that is a selfie but is not composed of the digits of the input number. That result is still a selfie, so it will be reported. When the digits of that selfie are checked (before or after that instance), it would again produce that selfie.

To conclude, this new version is down to 100 steps, finds all 37 selfies for 1 to 11 digit numbers, and runs about 25% faster than the prior program presented in the post immediately above. Free42 completes the task in about 12 seconds, and my DM42 did so in 52 minutes. (It also finds no duplicates, so for up to 11 digits, my conjecture appears to be correct?)

Here is the code:

Code:


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

A zipped raw file is attached at the bottom. Here is the program listing outside of a "code" box to allow easy pdf creation:
000 { 167-Byte Prgm }
001 LBL "Σd↑n"__
002 11__________ Steps 2 through 8 clear registers 1 through 11 and 20
003 0___________
004 STO 20______ initialize register 20 which keeps track of number of digits in number
005 LBL 01______
006 STO IND ST Y_
007 DSE ST Y____
008 GTO 01______
009 LBL 02______ Label 02, begin main routine
010 1.011_______ Store 1.011...
011 STO 00______ ...for ISG to check digits
012 LBL 03______ Label 3, check digits to see if they equal 9
013 9___________ Enter 9
014 RCL IND 00__ recall digit
015 X≠Y?________ is it not equal 9?
016 GTO 04______ if not, go to routine to increment
017 ISG 00______ if equal to 9, increment counter to...
018 GTO 03______ ...loop back to check next digit
019 STOP________ if register 11 equal 9, all unique combinations up to 99,999,999,999 have been checked
020 LBL 04______ routine to increment registers
021 RCL 20______ recall number of digits
022 RCL 00______ recall loop counter
023 IP__________ take integer part since it has ISG target coded
024 X>Y?________ is current digit pointer greater than current number of digits
025 STO 20______ if so, store new number of digits
026 STO 00______ store back in counter for DSE to increment registers
027 1___________ Enter 1
028 RCL+ IND 00_ Recall and increment digit pointed to by counter
029 LBL 05______ label for loop to set all digits up to counter to new value
030 STO IND 00__ store new value
031 DSE 00______ decrement counter
032 GTO 05______ loop back to store new value in next lower digit position
033 RCL 20______ recall number of digits in current input number
034 STO 00______ store for power to raise digits to form sum d^n
035 LBL 07______
036 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
037 RCL 20______ recall number of digits in current input number for loop index to form sum d^n. Only sum digits greater than 1.
038 0___________
039 LBL 09______ Label to sum d^n
040 RCL IND 18__
041 RCL 00______
042 Y↑X_________
043 +___________
044 DSE 18______
045 GTO 09______
046 STO 14______ store sum d^n in register 14
047 LOG_________ take common log
048 IP__________ take integer part
049 1___________ Enter 1
050 +___________ Add 1 to determine number of digits
051 RCL 00______ recall number of digits
052 X≠Y?________ digits in original not equal digits in sum d^n?
053 GTO 10______ if not equal, cannot be selfie, skip all checks
054 CLA_________ clear alpha register
055 FIX 00______ Fix 0 to eliminate zeros after decimal for integers
056 CF 29_______ clear flag 29 to eliminate radix symbol display for integers, else it would get copied to alpha register
057 ARCL 14_____ copy sum d^n into alpha register
058 0___________ enter zero
059 LBL 08______ Label for loop to sum d^n of sum d^n of input number
060 ATOX________ move char# of leftmost digit of sum d^2 into X
061 X=0?________ is it zero?
062 GTO 11______ if zero, all digits shifted out, go to label to see if sum d^n of sum d^n equals original sum d^n
063 48__________ if not zero…
064 -___________ ...subtract 48 to convert char# to actual digit
065 RCL 00______ recall number of digits
066 Y↑X_________ raise digit to nth power
067 +___________ add to running sum of d^n
068 GTO 08______ loop back to sum next d^n
069 LBL 11______ recall number of digit being checked
070 X<>Y________ swap
071 RCL 14______ recall originla sum d^n
072 X≠Y?________ does sum d^n of sum d^n not equal original sum d^n?
073 GTO 10______ if not equal, cannot be selfie, skip to check next number
074 10__________ enter 10
075 MOD_________ determine rightmost digit
076 X=0?________ is FP zero, i.e., was rightmost digit zero?
077 GTO 10______ if so, cannot be selfie since reverse will be fewer digits, skip all checks
078 RCL 14______ if not, recall sum d^n
079 STO- 14_____ store in reg 14 to clear it. (steps 78 through 89 reverse the digits in the number to produce selfie)
080 LBL 16______
081 FP__________ take fractional part
082 STO+ 14_____ add to register holding reversed sum d^n
083 LASTX_______ recall input number
084 IP__________ take integer part
085 0.1_________ enter 0.1
086 STO÷ 14_____ divide current reversed number by 0.1 to shift left one digit
087 ×___________ multiply input number by 0.1 to shift one digit right
088 X≠0?________ is input number not zero, indicating more digits to shift?
089 GTO 16______ if not zero, loop back to shift and add again
090 RCL 14______ if zero, number has been reversed, recall reversed sum d^n
091 PRX_________ print number for which d…d=reverse of sum d^n
092 LBL 10______ routine to check if original number padded with zeroes to 11 digits have been checked
093 11__________ enter 11
094 RCL 00______ recall number of digits in original number (or padded with zeroes previously)
095 X=Y?________ are they equal
096 GTO 02______ if so, done checking original number and all padded with zero to 11 digits, go generate the next number
097 ISG 00______ increment the number of digits
098 DEG_________ no op
099 GTO 07______ go back to sum d^(n+1)
100 END_________

edit - shaved a couple of steps by using stack registers for a couple of loops instead of a storage register.