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

06222018, 08:20 PM
Post: #41




RE: [VA] Short & Sweet Math Challenges #23: "May the 4th Be With You !" ...
With some coaching and insights from Valentin, I attacked the problem from a more efficient direction and managed to create a program which is at least three orders of magnitude faster than my previous bruteforce efforts. The programs below calculate the 37 seflies from 1 to 11 digits in approximately 1 minute, 6 seconds on my probably not too fast desktop. Extrapolating run times, I calculated that it could run in something less than 3 hours on my DM42. So I plugged it into a USB power source and set it off. Two hours, 34 minutes later it completed the task, so it apparently is a realistic challenge for a physical machine.
The most useful information that Valentin provided was that it is not necessary to check and sum every number. While there are 89,999,999,999 11 digit numbers from 10,000,000,000 to 99,999,999,999, many, many, many of these contain the same digits and so will have the same sums to the 11th power. So if a way can be found to sum each combination just once, that will greatly reduce the quantity of numbers needing to be checked. (e.g., 54321 is the same as 43215 is the same as 12345 etc., so only one of these need be summed.) I think I actually realized this while working on the bruteforce methods, but saw no easy way to generate only the minimal set of combinations of digits. With Valentin's encouragement that this was the way to go, I was able to develop a method to sequentially generate the smallest combination of the digits for each set of n digits. The method may be difficult to decipher from the program listing (it happens in steps 10 through 42). I doubt that the method is particularly inisghtful, so in an effort to keep this post as short as possible, I won’t describe it. I can do so if there is any interest. Once the sum for a given set of n digits is created, you just have to see if its sum of digits to the nth power contains the same set of digits as the input number. If so, the reverse of that sum is a selfie. 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 Due to the way I “manufacture” the numbers to check, having to do with how I handled numbers with zeros in them, my program generates the selfies in the following order: 1 2 3 4 5 6 7 8 9 704 351 173 8028 4361 48039 4749 7180089 72729 84745 8180124 438845 5271471 5136299 15087642 802115641 77439588 351589219 52249382004 30609287624 579533274 638494435 4777039764 60605588394 15694046123 41919540249 97653680744 87561939628 The program is far from optimized, it would probably be possible to improve on the performance. But I believe that Valentin plans to wrap this one up soon, and I'm not sure I will have the time to try for further improvement. I wanted to get an "entry" in, so I'll go ahead and post this version. If I do find time and am able to improve the program before Valentin finalizes things, I'll provide an update. 00 { 249Byte Prgm } 01▸LBL "NM5" 02 11 03 STO 00 04▸LBL 01 05 0 06 STO IND 00 07 DSE 00 08 GTO 01 09▸LBL 02 10 1.011 11 STO 00 12▸LBL 03 13 9 14 RCL IND 00 15 X≠Y? 16 GTO 04 17 ISG 00 18 GTO 03 19 STOP 20▸LBL 04 21 RCL 00 22 IP 23 STO 00 24 1 25 RCL+ IND 00 26▸LBL 05 27 STO IND 00 28 DSE 00 29 GTO 05 30 11 31 STO 00 32 0 33▸LBL 06 34 RCL 00 35 1 36  37 10↑X 38 RCL× IND 00 39 + 40 DSE 00 41 GTO 06 42 STO 12 43 CLA 44 CF 29 45 FIX 00 46 ARCL ST X 47 ALENG 48 STO 00 49▸LBL 09 50 0 51▸LBL 07 52 ATOX 53 X=0? 54 GTO 08 55 48 56  57 RCL 00 58 Y↑X 59 + 60 GTO 07 61▸LBL 08 62 R↓ 63 STO 14 64 LOG 65 IP 66 1 67 + 68 RCL 00 69 X≠Y? 70 GTO 10 71 RCL 14 72 10 73 ÷ 74 FP 75 X=0? 76 GTO 10 77 ARCL 14 78 RCL 00 79 20 80 + 81 1000 82 ÷ 83 21 84 + 85 STO 16 86 STO 15 87▸LBL 11 88 ATOX 89 X=0? 90 GTO 13 91 48 92  93▸LBL 13 94 STO IND 15 95 ISG 15 96 GTO 11 97 ISG 13 98 DEG 99 XEQ "SORT" 100 20.02 101 RCL+ 00 102 STO 15 103 0 104▸LBL 12 105 RCL 15 106 21 107  108 IP 109 10↑X 110 RCL× IND 15 111 + 112 DSE 15 113 GTO 12 114 RCL 12 115 X≠Y? 116 GTO 10 117 RCL 14 118 STO 14 119▸LBL 14 120 FP 121 STO+ 14 122 LASTX 123 IP 124 0.1 125 STO÷ 14 126 × 127 X=0? 128 GTO 15 129 GTO 14 130▸LBL 15 131 RCL 14 132 PRX 133▸LBL 10 134 11 135 RCL 00 136 X=Y? 137 GTO 02 138 RCL 12 139 ARCL ST X 140 ISG 00 141 DEG 142 GTO 09 143 STOP 144 END 00 { 51Byte Prgm } 01▸LBL "SORT" 02 RCL 16 03 SIGN 04▸LBL 21 05 LASTX 06 LASTX 07 RCL IND ST L 08▸LBL 22 09 RCL IND ST Y 10 X<Y? 11 GTO 23 12 X<>Y 13 LASTX 14 + 15▸LBL 23 16 R↓ 17 ISG ST Y 18 GTO 22 19 X<> IND ST L 20 STO IND ST Z 21 ISG ST L 22 GTO 21 23 RTN 24 END Credit to Gamo for the reversing integer routine in steps 117 through 129. Credit to JeanMarc Baillard for the SORT subroutine. Dave  My mind is going  I can feel it. 

06242018, 02:57 PM
Post: #42




RE: [VA] Short & Sweet Math Challenges #23: "May the 4th Be With You !" ...
Here's a Python program for the sixth step:
Code: def selfie(m, i, k, n, s): The following 41 selfies are listed: Code: 0 It takes about 3 seconds to run: Code: real 0m2.805s Four of them start with 0: Code: 0 They might not be considered selfies which agrees with: Quote:all 37 Selfies up to 11 digits long 

06252018, 12:42 PM
Post: #43




RE: [VA] Short & Sweet Math Challenges #23: "May the 4th Be With You !" ...
(06242018 02:57 PM)Thomas Klemm Wrote: Here's a Python program for the sixth step: I gather that Valentin's original definition of a selfie as the reverse of the sum of powers is aimed at eliminating numbers which end in zero. I'm not a Python expert, but if you amend the third line of your program to test that the last digit of s is not zero, it will return Valentin's original 37 numbers (at some cost in execution speed). John 

06252018, 01:41 PM
Post: #44




RE: [VA] Short & Sweet Math Challenges #23: "May the 4th Be With You !" ...
(06252018 12:42 PM)John Keith Wrote: I gather that Valentin's original definition of a selfie as the reverse of the sum of powers is aimed at eliminating numbers which end in zero. Not sure about that. Might as well be to make it a bit more difficult. Quote:I'm not a Python expert, but if you amend the third line of your program to test that the last digit of s is not zero, it will return Valentin's original 37 numbers (at some cost in execution speed). Or then you simply filter them out after the computation: Code: python selfie.py  grep v ^0 

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. . 

07182018, 01:10 AM
Post: #46




RE: [VA] Short & Sweet Math Challenges #23: "May the 4th Be With You !" ...
(07182018 12:17 AM)Valentin Albillo Wrote: 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... Thanks for the original challenge but also for the several earlier, and now this detailed solution for the final section. Though most often I am not up these challenges of yours, I thoroughly enjoy pondering them (until I get frustrated) and then reading the various members' solutions. And your detailed explanations (like this one above) are excellent learning tools as they not only explain how you solved it, but also why you chose that technique and how it works, generally in a clear enough manner to see how to apply similar techniques in the future to other problems. Also, I've noted that your very detailed solutions have often inspired others to also explain their solutions in a similar, detailed manner, which is far more helpful to subsequent readers than a (possibly well thoughtout, but still) obscure code listing and a brief note claiming this solution is '3 bytes shorter' or some other similar claim to fame. Thanks to all that participated and shared their answers here, it's quite interesting to many of us quiet readers. Bob Prosperi 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)