Post Reply 
Fun with Numbers: The Pan-Prime-Digit Cube Hypothesis
08-23-2017, 11:53 PM
Post: #56
RE: Fun with Numbers: The Pan-Prime-Digit Cube Hypothesis
(08-23-2017 09:58 PM)DavidM Wrote:  I haven't begun my 50g version yet (other than the brief loop timing), so no lost effort there.

OK, so here are a couple of thoughts:
I think the optimal code works by adding digits to the number one by one (without looking at his sources, I guarantee you this is Werner's method, or very similar).
Given a number N, when doing N*N*N, the last 'm' digits of the result are only determined by the last 'm' digits of N.
So to take advantage of that we would have to start with 1 digit for N. Create a list of all possible single digits that produce a cube with a valid single digit at the end { 3 5 7 8 }.
Set K= 2 (for 2 digit checks).
The main loop would scan this list, for each number on the list, it checks 10 cases, the number with the digits 0 thru 9 prepended, so it will take 3, and check 03,13,23,33,43,53...
The check should consist of 2 things:
a) If the result is the pandigit number we are looking for. If so, add it to the list of "found" numbers, and start the fireworks!.
b) If the last K digits of the result are valid digits. Now the K-1 last digits are already known to be valid (because they only depend on the digits we took from the list), so we actually only need to test if the K digit from the right is valid. If so, add it to a new list where we will put all numbers worth scanning on the next round.

And we are done. At the end of each loop, we can stop the program and see the results. The program will be able to continue where it left off by simply setting K=3 and running the loop again on the new list.
The resulting list for K=2 contains now 24 2-digit numbers, which we got by checking 40 out of the 100 numbers we should've checked. Since the next round (K=3) adds 1 digit (all 10 cases), we'll check only 240 numbers out of 1000. This will result in 77 candidates only for K=3, so we'll only need to check 770 numbers out of 10000 on the next round (K=4). This matches what Werner described, actually he mentioned 4880 for K=6, which I have not checked but have no reason to doubt either. That's why I think this is his algorithm.
Since for each round we throw away the previous list, it minimizes memory consumption and perhaps the 50g can actually get to the first result in our lifetime.
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
RE: Fun with Numbers: The Pan-Prime-Digit Cube Hypothesis - Claudio L. - 08-23-2017 11:53 PM



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