Post Reply 
[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.
Find all posts by this user
Quote this message in a reply
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):
    if i == 0:
        if n == ''.join(sorted(str(s))):
            print str(s)[::-1]
    else:
        for j in range(k, 10):
            selfie(m, i - 1, j, n + str(j), s + j ** m)

for m in range(12):
    selfie(m, m, 0, '', 0)

The following 41 selfies are listed:
Code:
0
1
2
3
4
5
6
7
8
9
073
704
351
173
8028
4361
4749
48039
72729
84745
438845
7180089
8180124
5271471
5136299
05087642
15087642
77439588
802115641
351589219
579533274
638494435
4777039764
05694046123
52249382004
30609287624
60605588394
15694046123
41919540249
97653680744
87561939628

It takes about 3 seconds to run:
Code:
real    0m2.805s
user    0m1.942s
sys    0m0.054s

Four of them start with 0:
Code:
0
073
05087642
05694046123

They might not be considered selfies which agrees with:
Quote:all 37 Selfies up to 11 digits long
Find all posts by this user
Quote this message in a reply
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:
Code:
def selfie(m, i, k, n, s):
    if i == 0:
        if n == ''.join(sorted(str(s))):
            print str(s)[::-1]
    else:
        for j in range(k, 10):
            selfie(m, i - 1, j, n + str(j), s + j ** m)

for m in range(12):
    selfie(m, m, 0, '', 0)

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
Find all posts by this user
Quote this message in a reply
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
Find all posts by this user
Quote this message in a reply
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:
  • "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.
.

  
All My Articles & other Materials here:  Valentin Albillo's HP Collection
 
Visit this user's website Find all posts by this user
Quote this message in a reply
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
Find all posts by this user
Quote this message in a reply
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:

- 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

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 }        
001        LBL "Σd↑n"          
002        11                  Steps 2 through 9...
003        STO 00              ...clear registers  1 through 11 and 20
004        0                   
005        STO 20              initialize register 20 which keeps track of number of digits in number
006        LBL 01              
007        STO IND 00          
008        DSE 00              
009        GTO 01              
010        LBL 02              Label 02, begin main routine
011        1.011               Store 1.011...
012        STO 00              ...for ISG to check digits
013        LBL 03              Label 3, check digits to see if they equal 9
014        9                   Enter 9
015        RCL IND 00          recall digit
016        X≠Y?                is it not equal 9?
017        GTO 04              if not, go to routine to increment
018        ISG 00              if equal to 9, increment counter to...
019        GTO 03              ...loop back to check next digit
020        STOP                if register 11 equal 9,  all unique combinations up to 99,999,999,999 have been checked
021        LBL 04              routine to increment registers
022        RCL 20              recall  number of digits
023        RCL 00              recall loop counter
024        IP                  take integer part since it has ISG target coded
025        X>Y?                is current digit pointer greater than current number of digits
026        STO 20              if so, store new number of digits
027        STO 00              store back in counter for DSE to increment registers
028        1                   Enter 1 
029        RCL+ IND 00         Recall and increment digit pointed to by counter
030        LBL 05              label  for loop to set all digits up to counter to new value
031        STO IND 00          store new value
032        DSE 00              decrement counter
033        GTO 05              loop back to store new value in next lower digit position
034        RCL 20              recall number of digits in current input number
035        STO 00              store for power to raise digits to form sum d^n
036        LBL 07              
037        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
038        RCL 20              recall number of digits in current input number
039        STO 18              store for loop index to form sum d^n.  Only sum digits greater than 1.
040        0                   
041        LBL 09              Label to sum d^n
042        RCL IND 18          
043        RCL 00              
044        Y↑X                 
045        +                   
046        DSE 18              
047        GTO 09              
048        STO 14              store sum d^n in register 14
049        LOG                 take common log
050        IP                  take integer part
051        1                   Enter 1 
052        +                   Add 1 to determine number of digits
053        RCL 00              recall number of digits
054        X≠Y?                digits in original not equal digits in sum d^n?
055        GTO 10              if not equal, cannot be selfie, skip all checks
056        LBL 08              Steps 56 through 64 copy the digits of the input number in registers 1 through 11 to registers 21 through 31.
057        RCL IND ST X        recall digit of input number (or of current digit position)
058        20                  enter 20 
059        RCL+ ST Z           add 20 to number of digits/digit position
060        X<>Y                
061        STO IND ST Y        store value of digit in position 1 through 11 in 21 through 31
062        RCL ST Z            
063        DSE ST X            
064        GTO 08              loop back to store next digit
065        CLA                 clear alpha register
066        FIX 00              Fix 0 to eliminate zeros after decimal for integers
067        CF 29               clear flag 29 to eliminate radix symbol display for integers, else it would get copied to alpha register
068        ARCL 14             copy sum d^n into alpha register
069        20.02               enter 20.02 
070        RCL+ 00             add to number of digits to form index for looping and store/recall
071        STO 15              store index
072        LBL 11              
073        RCL 15              recall index
074        STO 16              store for checking each digit
075        ATOX                move char# of leftmost digit of sum d^2 into X
076        X=0?                is it zero?
077        GTO 14              if zero, all digits shifted out, go to label indicating sum d^n is permutation of original
078        48                  
079        -                   subtract 48 to convert char# to actual digit
080        LBL 13              
081        RCL IND 16          recall digit of input number
082        X=Y?                are they equal
083        GTO 12              if so, go to label to mask digit for further checks
084        X<>Y                if not, swap to get digit back in X
085        DSE 16              decrement index
086        GTO 13              loop back to check next digit of original number
087        GTO 10              if all digits checked without match, go to label for sum d^n not a permutation
088        LBL 12              Label for steps to mask digits after successful match
089        PI                  enter Pi for value that cannot match any integer
090        STO IND 16          store in digit of original number that was matched
091        GTO 11              loop back to check next digit of sum d^n
092        LBL 14              Label for indication that sum d^n is permutation of original number
093        RCL 14              recall sum d^n
094        10                  enter 10
095        MOD                 determine rightmost digit
096        X=0?                is FP zero, i.e., was rightmost digit zero?
097        GTO 10              if so, cannot be selfie since reverse will be fewer digits, skip all checks
098        RCL 14              if not, recall sum d^n
099        STO- 14             store in reg 14 to clear it. (steps 98 through 109 reverse the digits in the number to produce selfie)
100        LBL 16              
101        FP                  take fractional part
102        STO+ 14             add to register holding reversed sum d^n
103        LASTX               recall input number
104        IP                  take integer part
105        0.1                 enter 0.1
106        STO÷ 14             divide current reversed number by 0.1 to shift left one digit
107        ×                   multiply input number by 0.1 to shift one digit right
108        X≠0?                is input number not zero, indicating more digits to shift?
109        GTO 16              if not zero, loop back to shift and add again
110        RCL 14              if zero, number has been reversed, recall reversed sum d^n
111        PRX                 print number for which d…d=reverse of sum d^n
112        LBL 10              routine to check if original number padded with zeroes to 11 digits have been checked
113        11                  enter 11
114        RCL 00              recall number of digits in original number (or padded with zeroes previously)
115        X=Y?                are they equal
116        GTO 02              if so, done checking original number and all padded with zero to 11 digits, go generate the next number
117        ISG 00              increment the number of digits
118        DEG                 no op
119        GTO 07              go back to sum d^(n+1)
120        END

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            ...
 2    14    27    ...     88    119    227    444     799     ...        9999            ...    39999999999
 3    15    28     49     89    122    228    ...     888    4444       11111     1111111111    44444444444
 4    16    29     55     99    ...    229    499     ...     ...         ...            ...            ...
 5    17    33    ...    111    188    233    555     899    5555       99999    11111111111    49999999999
 6    18    34     59    112    189    ...    ...     999     ...      111111            ...    55555555555
 7    19    35     66    113    199    288    599    1111    6666         ...    19999999999            ...
 8    22    36    ...    114    222    289    666     ...     ...     1111111    22222222222    59999999999
 9    23    37     69    115    223    299    ...    1999    7777         ...            ...    66666666666
11    24    38     77    116    224    333    699    2222     ...    11111111    29999999999            ...
12    25    39     78    117    225    ...    777    2999    8888         ...    33333333333    99999999999

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.


Attached File(s)
.zip  Sumd^n.zip (Size: 335 bytes / Downloads: 1)
.zip  Sumd^n V2.zip (Size: 335 bytes / Downloads: 1)

Dave - My mind is going - I can feel it.
Find all posts by this user
Quote this message in a reply
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:

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 ST Y              
041        RCL 00                  
042        Y↑X                     
043        +                       
044        DSE ST Y                  
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

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.


Attached File(s)
.zip  Sumd^n V3.zip (Size: 286 bytes / Downloads: 3)

Dave - My mind is going - I can feel it.
Find all posts by this user
Quote this message in a reply
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:

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

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.
Find all posts by this user
Quote this message in a reply
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.


Attached File(s)
.zip  Sumd^n V4.zip (Size: 326 bytes / Downloads: 3)

Dave - My mind is going - I can feel it.
Find all posts by this user
Quote this message in a reply
Post Reply 




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