[VA] Short & Sweet Math Challenges #23: "May the 4th Be With You !" Special
|
06-22-2018, 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 brute-force 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 brute-force 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 { 249-Byte 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 { 51-Byte 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 Jean-Marc Baillard for the SORT subroutine. Dave - My mind is going - I can feel it. |
|||
06-24-2018, 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 |
|||
06-25-2018, 12:42 PM
Post: #43
|
|||
|
|||
RE: [VA] Short & Sweet Math Challenges #23: "May the 4th Be With You !" ...
(06-24-2018 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 |
|||
06-25-2018, 01:41 PM
Post: #44
|
|||
|
|||
RE: [VA] Short & Sweet Math Challenges #23: "May the 4th Be With You !" ...
(06-25-2018 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 |
|||
07-18-2018, 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 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:
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:
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. . All My Articles & other Materials here: Valentin Albillo's HP Collection |
|||
07-18-2018, 01:10 AM
Post: #46
|
|||
|
|||
RE: [VA] Short & Sweet Math Challenges #23: "May the 4th Be With You !" ...
(07-18-2018 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 thought-out, 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 |
|||
10-24-2019, 01:26 PM
(This post was last modified: 11-05-2019 12:47 PM by Jeff O..)
Post: #47
|
|||
|
|||
RE: [VA] Short & Sweet Math Challenges #23: "May the 4th Be With You !" ...
I'm guessing no one was expecting an update regarding further work on this, but a couple of recent things brought it back to my attention. First, the HHC 2019 programming contest was related, and second, Valentin's posting of his web site led me to re-read his challenge and my input. For posterity’s sake, I decided to go ahead and add my new work to the original thread. (Apologies in advance for the length of this post, brevity is not a strength of mine.)
As noted in my old post above, I ended up solving the sixth part of Valentin's challenge, with optimizations to reduce the search space, but with the knowledge that other portions of the program were decidedly not optimized. I was particularly dissatisfied with my method to determine if the digits in the sum of the digits to the n-th power were a permutation of the digits in the n-digit input number: (06-22-2018 08:20 PM)Jeff O. Wrote: I did this in what I am sure is a very clunky fashion: As I said, I found the above dissatisfying, but the program worked, Valentin wrapped up the challenge, and I returned to the mundane tasks of everyday life. After the HHC 2019 programming contest was presented, I realized that it was related to Valentin's challenge, limited to 3-digit numbers and eliminating the "selfie" constraint, i.e., just looking for 3-digit numbers whose digits to the 3rd power summed to the input number, not the reverse. After creating a brute-force method to solve the programming contest, I revisited my "selfie" program to see how it might be used. First I removed the few lines that did the "selfie" part, and it quickly found the four answers to the contest. Then somewhere along the line I re-read my old post, remembered my dissatisfaction and decided to see if I could improve on the previous version, especially the permutation identification part quoted above. When I originally worked on the problem, I tried to think of a better way to do it. Doing it manually, I envisioned something like the following process: 1. Write down both numbers 2. Pick a digit in the first number, look for it in the second 3. If a is match found, mark out the digit from each number, go back to step 2. If all digits get checked and matched, go to step 5. If they do not match, go to step 4. 4. If a match for any digit in the input number cannot be found in the second, the numbers cannot be permutations of each other. 5. All digits found and uniquely matched, so the numbers are permutations of each other. For example, check 12345 against 34521 Pick the 5 from 12345, matches the 5 from 34521, strike out both, leaving 1234X vs. 34X21. These might be re-written as 1234 and 3421. Now check the 4, leaving 123X vs. 3X21 or 123 vs. 321, and so on until checking 1 vs. 1, and thus finding the two starting numbers to be permutations of each other. Now check 12745 vs. 34521. As above, 5 matches 5, leaving 1274X vs. 34X21 (or 1274 vs. 3421), 4 matches 4, leaving 127XX vs. 3XX21 (127 vs. 321). The next time around, 7 is not found in 321, so we abort the check and declare that the originals are not permutations. (I’m sure the above described procedure is quite simple and obvious to MoHPC Forum members, but I find it useful to spell out even the simple things, so I may remember them more readily in the future should the need arise.) For the purposes of the following discussion, the “first” number is the sum of the digits of the input number to the n-th power, and the “second” number is the input number. I think I considered the above method back in 2018 but got hung up on how I might check each digit and delete matches. It sounded like a lot of breaking, shifting and re-storing that did not immediately seem to be much if any better than my dissemble-sort-reassemble method. That’s when I dropped further work. When I returned to the problem recently, I revisited the above described manual procedure, and realized that rather than delete the digits as checked and repack to create new numbers, if I could find a way to identify that a match had been found and no longer check those digits, I would not need to reassemble at each step. It is relatively easy to extract single digits from the first number and create a number with one less digit, so each digit is eliminated from further checking at each step. For checking against the second, I determined that I did not need to eliminate the matches and reconstitute the second number without that digit, I just needed to make sure that a digit could not be matched again. So if a match is found, rather than delete and re-assemble, I changed that digit to a value that could not be a match to any further digits extracted from the original number. My input numbers were generated by the method I used (described below) as individual digits in sequential storage registers. So if a match was found, I stored pi in the register that held the matching digit. I was then free to check all future digits against all registers that represented the second number with no possibility that that digit could be matched again. With a bit of work, I was able to implement the above method, and pleased to find that it worked quite well. The revised program is reduced to 120 steps compared to 143 of the original, plus the need for the separate 23 step SORT routine is eliminated. With the above major change and a couple of other improvements, the new version runs in less than half the time of the original. On my DM42, all selfies are found in 1 hour and 9 minutes vs. 2 hours 34 minutes of the original. With Free42 on my desktop, it finds them all in 18 seconds vs. 45 seconds for the original program. I'm fairly happy with the improvement, but I may continue looking for refinements, as it is an enjoyable pastime. (edit - see below for an update to this post and the following post for a new method.) Here is the code: Code: 000 { 209-Byte Prgm } My number generator generates the following sequence of numbers to check (read top to bottom, left to right): Code: 1 13 26 44 79 118 226 399 ... 3333 ... 111111111 ... In case it is not immediately apparent what is going on with the above sequence of numbers to check, a description of the procedure used to create the sequence is as follows: 1. Start with all 11 registers representing the (up to) 11 digit number set to zero. 2. Recall the digit in the ones position 3. Is it 9? 4. If not, increment it, the 11 registers now represent the next number. Check for sum d^n being a permutation, then return to step 2. 5. If it is equal to 9, check the digit to the left in the tens position. 6. Is it 9? 7. If not, increment it and also set the value in the ones position to that new value, the 11 registers now represent the number to be evaluated. 8. If it is equal to 9, check the digit to the left in the hundreds position. 9. Is it 9? 10. If not, increment it and also set the values in the tens and ones positions to that new value, the 11 registers now represent the next number to be evaluated. 11. If it is equal to 9, check the digit to the left in the thousands position. 12. And so on. To be honest, I'm not quite sure how I arrived at the above method to create the sequence of numbers. It took me a while to figure out how it worked and what I was doing in my program again after 15 months. Probably some well-known technique that I stumbled upon. The full listing of all numbers generated by the above procedure would include 167,959 numbers. The interested reader will likely notice that the above listing contains no numbers that include any zeros. Yet there are several numbers containing at least one zero which satisfy the goal that the digits of the n-digit number raised to the n-th power sum to the n-digit number itself. I developed and checked those as follows. After generating and checking each of the above numbers, I then padded them with zeros. So for a single digit number, say 5, I checked 5, 50, 500, 5000,…, 50 000 000 000. I did not raise the zeros to the higher powers, I only raised the original non-zero digits to the higher powers and summed those. This requires checking 11 numbers for every single-digit number in the above list, 10 numbers for every 2-digit number, 9 numbers for each 3-digit, etc. on up to 1 number for each 11-digit number in the above list. That increases the total count of the numbers needing to be checked to 352,704. Still quite a small fraction (0.0003527%) of the 99,999,999,999 numbers which would have to be checked via a brute-force method. Last but not least, attached is a zipped raw file in case you would like to play with the program in Free42 or your DM42. If you would like to simply determine those n-digit numbers whose digits raised to the n-th power sum to themself, i.e., remove the selfie constraint (and who wouldn't?), delete steps 93 through 109. Edit - as expected, I continued to attempt to improve my program. In an effort to speed it up, I developed a new way to determine the number of digits in the current number developed by my above described method. It appears to be only about 1% faster, so not as much improvement as I had hoped. But it is 6 steps shorter, so I would call it a better effort. I replaced the program listing above with the new version, and have attached a new zipped raw file. The original raw file is still attached for posterity. Dave - My mind is going - I can feel it. |
|||
11-04-2019, 07:18 PM
(This post was last modified: 11-05-2019 01:58 PM by Jeff O..)
Post: #48
|
|||
|
|||
RE: [VA] Short & Sweet Math Challenges #23: "May the 4th Be With You !" ...
(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:
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. Dave - My mind is going - I can feel it. |
|||
11-05-2019, 11:17 PM
(This post was last modified: 11-05-2019 11:21 PM by Albert Chan.)
Post: #49
|
|||
|
|||
RE: [VA] Short & Sweet Math Challenges #23: "May the 4th Be With You !" ...
(11-04-2019 07:18 PM)Jeff O. Wrote: My logic for this was as follows: Hi, Jeff O. I checked all (88) Armstrong numbers, and see how many A's can produce it. If B is an Armstrong number (B=C), A is unique → A,B has same sets of digits Confirmed (by brute force) that your conjecture is correct. |
|||
11-23-2019, 10:17 PM
(This post was last modified: 12-01-2019 06:17 PM by Jeff O..)
Post: #50
|
|||
|
|||
RE: [VA] Short & Sweet Math Challenges #23: "May the 4th Be With You !" ...
One final (hopefully) update: With some encouragement and advice from Valentin, I developed yet another version of my program. Valentin suggested that I eliminate excessive use of Y^X and instead pre-compute the digits to the powers (i.e., 0^N, 1^N, …9^N) and sum them according to the digits in the number. So instead of calculating 5^8, for example, merely sum the pre-computed value of 5^8 if there is a 5 in the 8-digit number under evaluation.
I was initially unsure if I could apply it due to the manner in which prior versions create and check numbers containing zeroes. See above for how I did that, suffice it to say that it would require creating and storing the values of 0 through 9 to the Nth power for each number, because my prior method changes the number of digits at each number checked. So pre-computing 0 through 9 to Nth power for each new number of digits at each number would not be expected to save much if any time. But I liked the idea, so I decided to see if I could alter my method of generating input numbers to allow it to be used. The goal would of course be to generate all one-digit numbers, then all two-digit numbers (including those with one trailing zero), then all three-digit (including those with one or two trailing zeroes), etc., on up to all 11 digit numbers. This would enable me to pre-compute 0^N, 1^N, …9^N only when the number of digits is increased by one, i.e., only 11 times for the entire run of the program, which is I’m sure what Valentin intended. With a little effort, I was able to do just that. My prior method of generating numbers would go like this: 19999999999 22222222222 22222222223 22222222224 etc. The new method inserts numbers with zeroes like this: 19999999999 20000000000 22000000000 22200000000 22220000000 22222000000 22222200000 22222220000 22222222000 22222222200 22222222220 22222222222 22222222223 22222222224 etc. Incorporating the pre-computation method was a bit tricky, as it requires storing those values for later recall. The most natural registers to store them would be 0 through 9, so that the digit value could point to the register containing that digit to the Nth power. But all of my prior versions stored the digits of my input numbers in register 1 through 11, so I chose to store the values of 0^N, 1^N, …9^N in registers 20 through 29. This requires adding 20 to the recalled digit value before indirectly recalling the appropriate d^N value to create the sum. I was able to handle this, and the latest version is indeed the quickest yet. Using Free42 on my laptop PC, this latest version completes the task in approximately 35.6 seconds, compared to 51.7 seconds for the prior version, an approximate 30% decrease in execution time. On my DM42, the timings are 35 minutes and 57 seconds for the latest version vs. 51 minutes and 40 seconds for the prior version, also essentially a 30% reduction. On a desktop PC that I also use at times, I get anomalous results. Initially, the timings were 12.9 seconds vs. 11.7 seconds. Then that PC received a Windows update, and now Free42 runs much more slowly. And, oddly enough, the new version is actually slower than the prior version, 49.9 seconds vs. 48.5 seconds. I am running the same version of Free42 on both PCs (the decimal version of 2.5.11), so I don't know why the timings are not consistent on one PC vs. the other, nor why the windows update would slow Free42 down by a factor of 4. For timing results, I guess I put the most faith in the DM42 results, so I believe that the method is demonstrably faster. Below is the program listing, and a zipped raw file is attached. I'd be interested in seeing timings using Free42 in other platforms if anyone has the time or inclination. 000 { 212-Byte Prgm } 001 LBL "Σd↑n"_____ 002 FIX 00_________ Fix 0 to eliminate zeroes after decimal for integers 003 CF 29__________ clear flag 29 to eliminate radix symbol display for integers, else it would get copied to alpha register 004 20_____________ Steps 4 through 9 clear registers 1 through 20 (need to clear 20 for 0^N for all N's, not done in subroutine) 005 0______________ 006 LBL 01_________ 007 STO IND ST Y___ 008 DSE ST Y_______ 009 GTO 01_________ 010 1______________ 011 STO 01_________ initialize register 1 to 1 012 XEQ 12_________ execute subroutine to calculate 1^N….9^N for N=1 013 GTO 98_________ go to label to calculate sum d^N for 1 014 LBL 02_________ Label 02, begin main routine 015 RCL 01_________ recall rightmost digit 016 X=0?___________ is it zero? 017 GTO 99_________ if so, prior number had trailing zero(es), go to routine to copy latest incremented number down to next lower register 018 1.011__________ Store 1.011... 019 STO 00_________ ...for ISG to check digits 020 LBL 03_________ Label 3, check digits to see if they equal 9 021 9______________ Enter 9 022 RCL IND 00_____ recall digit 023 X≠Y?___________ is it not equal 9? 024 GTO 04_________ if not, go to routine to increment 025 ISG 00_________ if equal to 9, increment counter to… 026 GTO 03_________ ...loop back to check next digit 027 STOP___________ if register 11 equal 9, all unique combinations up to 99,999,999,999 have been checked 028 LBL 04_________ routine to increment registers 029 RCL 12_________ recall number of digits 030 RCL 00_________ recall loop counter, which has counted up to register number containing first non-9 digit 031 IP_____________ take integer part 032 STO 19_________ store for use in storing new incremented values in lower registers 033 STO 19_________ store back in register zero without .011 rarget for use as DSE later 034 X>Y?___________ is register in which first non-9 found greater than current number of digits? 035 XEQ 12_________ if so, new number of digits established, go to subroutine to calculate 1^N, 2^N,…9^N 036 1______________ enter 1 037 STO+ IND 00____ add one to register in which first non-9 found 038 DSE 00_________ decrement register 0 039 DEG____________ no operation 040 0______________ enter 0 041 LBL 05_________ label for loop to store zeroes in registers N-1 to 1 042 STO IND 00_____ store zero 043 DSE 00_________ decrement register zero 044 GTO 05_________ loop back to store next zero 045 GTO 98_________ go to label to calculate sum d^N 046 LBL 99_________ label to store incremented value in lower registers after storing zeroes 047 RCL IND 19_____ recall new incremented value 048 DSE 19_________ decrement loop counter 049 STO IND 19_____ store new incremented value in next lower register 050 LBL 98_________ label to calculate sum d^N 051 RCL 12_________ recall current number of digits 052 0______________ enter zero 053 LBL 09_________ loop label for summing d^N 054 20_____________ enter 20 055 RCL+ IND ST Z__ add to value of digit in register N, N-1,…1 056 RCL IND ST X___ recall value in register 20 + the value of the digit 057 RCL+ ST Z______ add to running sum 058 R↑_____________ roll up… 059 X<>Y___________ … and swap to get stack in proper order 060 DSE ST Y_______ decrement register containing N, N-1…1 061 GTO 09_________ loop back to recall and sum next d^N 062 STO 14_________ store sum d^N in register 14 063 CLA____________ clear the alpha register 064 ARCL 14________ copy sum d^N into alpha register 065 ALENG__________ length of alpha register equals how many digits in number 066 RCL 12_________ recall current number of digits 067 X≠Y?___________ digits in original not equal digits in sum d^N? 068 GTO 02_________ if not equal, cannot be selfie, skip all checks 069 RCL 14_________ if equal, recall sum d^N 070 +/-____________ negate 071 LBL 08_________ Label for loop to sum d^N of sum d^N of input number 072 ATOX___________ move char# of leftmost digit of sum d^N into X 073 X=0?___________ is it zero? 074 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 075 28_____________ if not zero… 076 -______________ ...subtract 28 to convert char# to actual digit plus 20 077 RCL IND ST X___ recall d^N of value of digit 078 RCL+ ST Z______ add to negated sum d^N 079 GTO 08_________ loop back to recall next digit 080 LBL 11_________ Label to see if sum d^N of sum d^N equals original sum d^N 081 X≠Y?___________ zero will be in x, if sum d^N of sum d^N equals original sum d^N, zero will be in y 082 GTO 02_________ if not equal, cannot be selfie, go back to create and check next number 083 RCL 14_________ recall sum d^N 084 10_____________ enter 10 085 MOD____________ determine rightmost digit 086 X=0?___________ is FP zero, i.e., was rightmost digit zero? 087 GTO 02_________ if so, cannot be selfie since reverse will be fewer digits, skip all checks 088 RCL 14_________ if not, recall sum d^N, steps 88 through 99 reverse the digits in the number to produce selfie 089 STO- 14________ store in reg 14 to clear it. 090 LBL 16_________ label for loop to reverse digits 091 FP_____________ take fractional part 092 STO+ 14________ add to register holding reversed sum d^N 093 LASTX__________ recall input number 094 IP_____________ take integer part 095 0.1____________ enter 0.1 096 STO÷ 14________ divide current reversed number by 0.1 to shift left one digit 097 ×______________ multiply input number by 0.1 to shift one digit right 098 X≠0?___________ is input number not zero, indicating more digits to shift? 099 GTO 16_________ if not zero, loop back to shift and add again 100 RCL 14_________ if zero, number has been reversed, recall reversed sum d^N 101 PRX____________ print number for which d…d=reverse of sum d^N 102 GTO 02_________ 103 LBL 12_________ Subroutine to calculate 1^N, 2^N,...9^N and store in registers 21 through 29 104 STO 12_________ store new N 105 9______________ enter 9 for DSE loop 106 LBL 13_________ 107 RCL ST X_______ duplicate X register 108 RCL 12_________ recall number of digits 109 Y↑X____________ raise 0…9 to Nth power 110 20_____________ enter 20 111 RCL+ ST Z______ add to 0…9 112 X<>Y___________ swap 113 STO IND ST Y___ store d^N in register 20+d 114 RCL ST Z_______ recall current digit 115 DSE ST X_______ decrement 116 GTO 13_________ loop back to calculate next 117 RTN____________ subroutine return 118 END____________ edits - revised program now three steps shorter, added commented program listing, fixed a mistake, clarified some things. Dave - My mind is going - I can feel it. |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: