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

07182018, 12:17 AM
Post: #45




RE: [VA] Short & Sweet Math Challenges #23: "May the 4th Be With You !" ...
.
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:
This is my solution for the HP71B, a 12line 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(H1) 5 I=F(H) @ N=S(H1)+R(I) @ IF N<M THEN S(H)=N @ D$(H)=D$(H1)&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=H1 @ IF H THEN 10 12 DISP @ NEXT K Notes:
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 12digit calcs) and 29 up to 9 digits long (for 10digit calcs). There are no 12digit 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 Ndigits 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 Ndigits. This alone reduces the search exponentially, as stated. Let's see an example with 2digit numbers: For 2digit 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 2digit 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 2digit too (so we need to check only those numbers which have 2digit 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:
This is not the only efficient approach possible. There's another way to conduct the search by keeping tallies but my HP71B implementation of that second approach isn't included here as it runs slower than the first (though for some nonHP71B 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. . All My Articles & other Materials here: Valentin Albillo's HP Collection 

« Next Oldest  Next Newest »

User(s) browsing this thread: