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

[Jeff O.]

(05-24-2018 09:13 PM)Valentin Albillo Wrote:  

Jeff O. Wrote:In any case, a 10-fold or more increase in speed is really needed to make this practical. [...] 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.

Please do. I'll post my original solution at 23:xx (GMT+1) next Sunday so you've got plenty of time to refine and expand your own.

Thanks to both and best regards.
V.

So as to not use anyone else's concepts for the time being, I have not reviewed Peter's work. Should anything I say or present below be a repetition of concepts presented by Peter, I fully acknowledge his priority.

In an effort to reduce execution time, I developed a method which basically checks 10 numbers at a time. I guess a better way to describe it would be to say that it determines if there is a solution between successive numbers that end in zero.

Since it is still basically just brute force, i.e., does not break any ground in attacking the problem in a super-efficient manner, I won't explain the procedure in detail. If anyone wants an explanation, I can provide it.

Since it effectively checks 10 numbers at a time, it seemed like a program based on the procedure should theoretically be up to 10 times faster than the previous program, as it checks all N+1 digit numbers by counting up to N. In practice, it appears that the various manipulations required to implement it eliminate some of the time saving. The speed-up seems to be more like a factor of 4 to 5. But with that improvement, I went ahead and turned it loose to find the 11-digit selfies. After (only) several days (again, on Free42 running on a couple of PCs), it found the seven 11-digit selfies:

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

The new program listing is presented below. Unfortunately, this program does not technically meet the original challenge. It cannot determine the single digit selfies from 1 through 9 since if you start counting at 1, it is checking candidates starting at 10. I could add code to just print out 1 through 9 at the start, but that seems unnecessary.

As noted, this is still essentially just brute force, and would be totally impractical on a DM42. Running on a physical machine in minutes or hours would require a massive speed-up factor. I'll keep trying to think of some other method to attack the problem that would be faster, but there's not much time until Sunday. Then I'll have to decide if I want to admit defeat and review Valentin's solution, or let it haunt me the rest of my days...

00 { 112-Byte Prgm }
01▸LBL "SELF"
02 CLA
03 CF 29
04 FIX 00
05 RCL 02
06 ARCL ST X
07 10
08 ×
09 ALENG
10 1
11 +
12 STO 00
13 R↓
14▸LBL 04
15 ATOX
16 X=0?
17 GTO 05
18 48
19 -
20 RCL 00
21 Y↑X
22 -
23 X<0?
24 GTO 08
25 GTO 04
26▸LBL 05
27 R↓
28 RCL ST X
29 RCL 00
30 1/X
31 Y↑X
32 1
33 +
34 IP
35 STO 11
36 RCL 00
37 Y↑X
38 RCL- 11
39 X≠Y?
40 GTO 08
41 10
42 RCL× 02
43 RCL+ 11
44 ARCL ST X
45 0
46 STO 01
47▸LBL 06
48 ATOX
49 X=0?
50 GTO 07
51 48
52 -
53 RCL 01
54 10↑X
55 ISG 01
56 DEG
57 ×
58 +
59 GTO 06
60▸LBL 07
61 R↓
62 PRX
63▸LBL 08
64 ISG 02
65 DEG
66 GTO "SELF"
67 END