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

[Valentin Albillo]

.
Hi, all:

This is my 200th post so it's perfectly fitting to wrap up here and now my S&SMC#23 by posting my very own solution to the final 6th Step, namely:

Step the Sixth:

• "We'll call "Selfie" to any positive N-digit integer number which has the property that if you sum its N digits raised to the Nth power you get the original number backwards. For instance, the 7-digit number 5271471 is a Selfie:
  
        5271471 => 5^7 + 2^7 + 7^7 + 1^7 + 4^7 + 7^7 + 1^7 = 1741725, which is 5271471 backwards
  
  Write a program to find all Selfies from 1 to 9 digits long (for 10-digit HP calcs, 29 in all) or from 1 to 11 digits long (for 12-digit HP calcs, 37 in all). 0 is not a positive number so it's not a Selfie."

My Solution:

This is my solution for the HP-71B, a 12-line program (437 bytes) which finds and outputs all Selfies from 1 up to 11 digits long in less than 3 min on my POPS system.:

       1  DESTROY ALL @ OPTION BASE 0 @ DIM R(9) @ L=48 @ FOR K=1 TO 11
       2  DIM F(K),S(K),D$(K) @ DISP K;": "; @ M=10^K @ T=M/10
       3  H=0 @ FOR I=1 TO 9 @ R(I)=I^K @ NEXT I
       4  H=H+1 @ F(H)=F(H-1)
       5  I=F(H) @ N=S(H-1)+R(I) @ IF N<M THEN S(H)=N @ D$(H)=D$(H-1)&CHR$(I+L) ELSE 11
       6  IF H#K THEN 4 ELSE IF N<T THEN 10 ELSE B$=STR$(N) @ A$=D$(H)
       7  IF SPAN(B$,A$) THEN 10 ELSE IF SPAN(A$,B$) THEN 10
       8  FOR I=1 TO K @ P=POS(A$,B$[I,I]) @ IF P THEN A$[P,P]="" ELSE 10
       9  NEXT I @ B$=REV$(B$) @ IF B$=TRIM$(B$,"0") THEN DISP B$;" ";
      10  IF F(H)#9 THEN F(H)=F(H)+1 @ GOTO 5
      11  H=H-1 @ IF H THEN 10
      12  DISP @ NEXT K

Notes:

• We only search for numbers having from 1 to 11 digits because for 12-digit numbers there are some whose sum of the 12th-powers of their digits exceeds 10^12 and thus cannot be checked correctly with 12-digit integer arithmetic. For instance:
  
        888888888888 -> Sum = 12*8^12 = 824633720832, which is still within range and can be correctly checked
        888888888889 -> Sum = 11*8^12+1*9^12 = 1.03834378058E12, which exceeds the integer range and can't be checked properly
  
  thus the search is limited to 11-digit numbers or less (there are no 12-digit Selfies anyway). The same applies to 10-digit calcs, which can only search for numbers up to 9-digit long.
• Line 7 uses the SPAN keyword from STRNGLEX to help speed the search but it's use is optional and can simply be deleted. Without it the program is 8% shorter (11 lines, 371 bytes) but 18% slower (200 sec. vs. 170 sec.)

Let's run it:

>RUN
        1 : 1 2 3 4 5 6 7 8 9
        2 :
        3 : 704 351 173
        4 : 8028 4361 4749
        5 : 48039 72729 84745
        6 : 438845
        7 : 7180089 8180124 5271471 5136299
        8 : 15087642 77439588
        9 : 802115641 351589219 579533274 638494435
       10 : 4777039764
       11 : 52249382004 30609287624 60605588394 15694046123 41919540249 97653680744 87561939628

There are 37 Selfies up to 11 digits long in all (for 12-digit calcs) and 29 up to 9 digits long (for 10-digit calcs). There are no 12-digit Selfies.

The program uses my generalized loops (first featured in S&SMC#21) to perform an exhaustive search for Selfies. The key to speed the search enormously is to check as few numbers as necessary (this will reduce the search time exponentially), then to implement minor but welcome optimizations which will further reduce the seach time by a significant linear factor.

The procedure goes like this: for N-digits numbers, there's no need to check every number from 00...00 to 99...99, we only need to check the smallest N for each permutation of its N-digits. This alone reduces the search exponentially, as stated. Let's see an example with 2-digit numbers:

For 2-digit numbers, in a naive exhaustive search we would simply compute the sum of the 2nd power (squares) of every number from 00 to 99 and see if the sum has the Selfie property, i.e., it equals the original number in reverse. If so, it is displayed as a solution and we would then proceed to the next 2-digit number and so on. We would check 10^2 = 100 numbers in all, the 100 values from 00 to 99.

However, we might notice that 12 and 21 have the exact same sum of their squared digits because addition is conmutative: Sum(12) = 1^2+2^2 = 5 = 2^2+1^2 = Sum(21), so we don't actually need to compute and check the sums for every digit permutation, checking just the first one (12) will do, no need to also check 21.

This, combined with the fact that the sum must be 2-digit too (so we need to check only those numbers which have 2-digit sums, i.e.: 10 >= Sum(N) <= 99 ) means that instead of the 100 numbers from 00 to 99 we only need to check these 40:

      04 05 06 07 08 09 13 14 15 16 17 18 19 23 24 25 26 27 28 29
      33 34 35 36 37 38 39 44 45 46 47 48 49 55 56 57 58 66 67 77

and thus the search has been reduced from 100 to just 40 numbers, i.e.: by a factor of 2.5x. For greater number of digits the reduction factor increases exponentially and thus the time for the full search decreases exponentially as well.

What do we need to do to implement this concept ? Two things:

• first, we need to generate and check only the lowest value for every permutation of digits, i.e: for N = 2 digits we'll generate and check 17 but not 71. For N=3 digits, we'll generate and check 047 but not its five permutations (074, 407, 470, 704, 740), as they all have the same sum of the 3rd powers of their digits. This means that for N=10 digits, you'll only generate and check *one* of the 3,628,800 permutations possible, thus speeding up the search by a factor of ~ 3.6 million.
• second, for each generated number (say 047) we have to check if the sum of the Nth powers of its digits is a permutation of the number being checked, i.e.; the sum of the cubed digits of 047 is 0^3+4^3+7^3 = 407, which indeed is a permutation of 047, the number being checked, so the reverse of the sum, 704, is a Selfie and we display it as one of the 3-digit Selfies.
  
  This will reduce the search time exponentially. Combined with other optimizations (generating efficiently the numbers to check, computing efficiently the sums, skipping N-digit numbers with sums > or < N-digits, checking efficiently if an N-digit number is or not a permutation of another, etc.) will help to further reduce the time by a linear factor which can be ~ 10x or more, i.e., further reducing an already fast 30 min. search to less than 3 min.

This is not the only efficient approach possible. There's another way to conduct the search by keeping tallies but my HP-71B implementation of that second approach isn't included here as it runs slower than the first (though for some non-HP-71B implementations it can run more than 2x faster).

Thanks for your interest and nice solutions, see you all in S&SMC#24 next Autumn.
V.
.