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

« Next Oldest  Next Newest »

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