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

[Jeff O.]

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.