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

[Jeff O.]

(05-17-2018 09:12 PM)Valentin Albillo Wrote:  

Jeff O Wrote:My usual inclination with such problems is to just go ahead and try for a brute force method, then try to optimize. The DM42 is fast, I would like to see how many digits it could handle in a reasonable time by brute force, so if I get the time I may have a go at it.

(05-17-2018 09:12 PM)Valentin Albillo Wrote:  Please do. I haven't created a solution for the DM42 but I guesstimate that with correct programming it can solve the 11-digit version in 5 min. to 1 hour running time.

(05-24-2018 06:14 AM)PeterP Wrote:  ...but I wanted to ask for your opinion about posting it or not given that it is indeed past your suggested deadline.

Peter,
Based on Valentin's "please do" stated above, I'm going on the assumption that it is OK to post. If interested, see below, which details my "clumsy" solution.

As a start, I went ahead and created a brute-force program with which I identified the 30 selfies from 1 to 10 digits:

1
2
3
4
5
6
7
8
9
173
351
704
4361
4749
8028
48039
72729
84745
438845
5136299
5271471
7180089
8180124
15087642
77439588
351589219
579533274
638494435
802115641
4777039764

For the sake of completeness, here are the 11-digit selfies, determined using a revised program as described in my post below:
15 694 046 123
52 249 382 004
30 609 287 624
97 653 680 744
60 605 588 394
87 561 939 628
41 919 540 249

I implemented this program on Free42 with the intent to download to my DM42 to see how fast it might go on that machine. The above results were obtained running Free42 on my desktop PC. Output was to the virtual printer. It produces the first 19 (i.e., 6-digit or fewer selfies) nearly instantaneously, then slows down considerably. Takes about maybe 2.5 minutes to get the 7-digit, then maybe 25 minutes for the 8-digit, and awhile for the 9-digit. I let the program run most of yesterday and then overnight, and this morning was rewarded with the lone 10-digit selfie. It looks like finding the seven 11-digit selfies would take about 20 days, so I think I’ll probably wait until I figure out some optimized method to find those rather than continuing to run my program.

My brute force method does not look directly for selfies, it looks for numbers which have the property that if you sum its N digits raised to the Nth power you get the original number back (let’s call them inverse selfies), then it simply reverses those to create the selfie. I quickly found that not all inverse selfies will be a selfie when reversed. Specifically those that end in zero will not, since when an N digit number ending in zero is reversed, it becomes an N-1 digit number. I thought that perhaps filtering out numbers ending in zero, i.e., not summing their digits to the Nth power to see if they were inverse selfies and so reducing the quantity of numbers to be checked by 10%, might speed things up. Unfortunately, performing that check on every number seemed to take longer, or at least was no quicker, than summing the digits to the Nth power for all numbers and then checking only inverse selfies to see if they end in zero. (I found two such numbers, 370 and 24678050, before I revised the program to eliminate them.) In any case, a 10-fold or more increase in speed is really needed to make this practical.

I can see some ways to determine that some numbers need not be checked, for example, no 10-digit number with three or more nines need be checked since all those will sum to an 11 digit number, no 10 digit number with six as the largest digit can be a selfie since thoese will not sum to a 10 digit number. I’ll keep thinking about the problem to see if I can develop a method that will be much quicker - hopefully it won’t keep me awake at night.

Here is the brute force program listing:

00 { 90-Byte Prgm }
01▸LBL "VA6_6"
02 CLA
03 CF 29
04 FIX 00
05 RCL 02
06 ARCL ST X
07 ALENG
08 STO 00
09 0
10▸LBL 04
11 ATOX
12 X=0?
13 GTO 05
14 48
15 -
16 RCL 00
17 Y↑X
18 +
19 GTO 04
20▸LBL 05
21 CLX
22 RCL 02
23 X≠Y?
24 GTO 08
25 10
26 ÷
27 FP
28 X=0?
29 GTO 08
30 ARCL ST Y
31 0
32 STO 01
33▸LBL 06
34 ATOX
35 X=0?
36 GTO 07
37 48
38 -
39 RCL 01
40 10↑X
41 ISG 01
42 DEG
43 ×
44 +
45 GTO 06
46▸LBL 07
47 R↓
48 PRX
49▸LBL 08
50 ISG 02
51 DEG
52 GTO "VA6_6"
53 END

edited to correct typo and add clarity to one item
edit no. 2 - added the 11-digit selfies to the list