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

[Valentin Albillo]

.
Hi, Jeff O.:

(06-02-2018 06:01 PM)Jeff O. Wrote:  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. [...] the speed-up seems to be more like a factor of 4 to 5. [...] After (only) several days (again, on Free42 running on a couple of PCs), it found the seven 11-digit selfies:

Congratulations, it's quite an achievement and I thank you for your efforts on this last part of my S&SMC#23. A factor of 400-500% faster over what sheer brute force produces is certainly a remarkable improvement.

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

It certainly is. The meat of the challenge is to produce the many-digit selfies, not the trivial ones. Insisting on that would be nitpicking on my part, which I don't usually indulge in.

Quote: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

Indeed. As far as I know, there are at least three ways to attack this problem. The first and most obvious is sheer brute force (very brute), but that stumbles at 10 or 11 digits at most and even then it takes excessively long times.

The second and third ways depend on the same idea but implement it differently and both reduce exponentially the required times, to the point that 11 digits can be reached in Emu71 in a few minutes, and using somewhat slow multiprecision software running on a decidedly slow old PC they can still find all the solutions with 10, 20, 30 and more digits in a few hours at most.

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

Time is not a problem, I'm also no nitpicker with deadlines and such. If you need more time, I'll glady postpone posting my solutions. Also, if you'd accept a hint or two in order to be able to implement the 2nd or 3rd ways, I'll gladly obligue. Perhaps it would spoil somewhat the pleasure of finding the idea by yourself but in the other hand it's also quite pleasurable to create a markedly non-trivial working solution starting from a little hint instead of sorely admitting defeat after so much effort and time.

Your choice ... :-D

Again, thanks for your interest and your great efforts, have a nice weekend.
V.
.