Fun with Numbers: The Pan-Prime-Digit Cube Hypothesis

[Gerald H]

(08-16-2017 04:26 PM)David Hayden Wrote:  My program just finished going through 16-digit values of N without finding another solution. So if there is a second pan-prime-digit cube, it is larger than 10^48. I think I'll try my hand at proving that no other solution exists.

Good luck!

However to save time you might consider my proof first.

[Werner]

(08-16-2017 04:26 PM)David Hayden Wrote:  My program just finished going through 16-digit values of N without finding another solution. So if there is a second pan-prime-digit cube, it is larger than 10^48. I think I'll try my hand at proving that no other solution exists.

I verified the numbers < 1e49 already. My current program is valid for x^3 < 1e51
Still running on Free42 on my laptop ;-)

Werner

[DavidM]

(08-17-2017 12:50 PM)Werner Wrote:  I verified the numbers < 1e49 already. My current program is valid for x^3 < 1e51
Still running on Free42 on my laptop ;-)

That's a good example of the power of Free42 in the hands of a skilled craftsman. I doubt the original team that worked on the 42 would have ever guessed that a simulator based on their product design would eventually be used for this kind of number crunching.

Just for giggles I added a feature to my Windows app today that sets the current base to a decimal number containing anywhere from 16 to 116 pseudo-random digits, then checks sequentially from there for 30 seconds before moving on to the next random base. I can run several instances of the app simultaneously, so when my laptop isn't busy doing something else I'll launch several instances and leave one set to a standard search while the others use the "lottery approach". I suspect my chances are better playing the lottery than they are at finding a new PD cube, but it's fun to watch it try.

[pier4r]

has free42 "enough digits" for the search? I mean, does it start to write 1eY after a while, losing the less significant digits?

[Werner]

Well, that is the challenge as numbers keep growing ;-)
For x < 1e17, I can cube it exactly quite easily, as Free42 carries 34 digits, so
x^3 calculated as x.x^2 has a single roundoff error

Then,
x^3 = B + r, where
r = MOD(x^3,1e17) = MOD(x.MOD(x^2,1e17),1e17) (for x<1e17, x^2 is exact)
r are the 17 trailing digits of x^3
B = x^3 - r, a number (< 1e51) ending in 17 zeroes.

By tomorrow I will have passed 1e51 for x^3 and I'll have to find something new.
(I already did btw)

PS. Currently running with the 20 million numbers < 1e12 that, when cubed, have the trailing 12 digits in {2,3,5,7} and narrowing down the cubes to match the first 8 digits. Verification of a number focuses first on the digits 'in the middle' as we know that the 8 leading and 12 trailing digits are all 2,3,5 and 7
Verifying cubes larger than 1e50 and smaller than 1e51 will take 3.5 hours, estimated.
Pre-computing an extra order of numbers speeds up the process by a factor 2.5, but order 12 seems to be the maximum, memory-wise. REGS can hold the 20 million, but not the 80 million needed for order 13.

Cheers, Werner

[pier4r]

Ah so you are having nice fun. Well done and thanks for sharing!

[David Hayden]

I'm working through the 17 digit suffixes now. The code now reads/writes input/ouput to files. I decompress the input on the fly and similarly compress the output. Even compressed, the file of 16 digit suffixes is 8GB.

The number of possible suffixes seems to be growing by a factor of about 4 for each new digit added. I had hoped that it would start shrinking and eventually drop to zero but that doesn't seem to be the case.

I've made zero progress on a mathematical proof. It occurs to me that the digits are obtained by remainder operations similar to the way some encryption algorithms work. So a mathematical proof might be impossible.

Joe Horn, how do you come up with these torture devices?

Dave

[Joe Horn]

(08-18-2017 03:47 PM)David Hayden Wrote:  Joe Horn, how do you come up with these torture devices?

If I knew, I'd be able to avoid them!

[David Hayden]

I made it through the 17-digit suffixes without finding another solution. I found 20,510,922,752 of them. Even compressed, the file takes 30GB on my hard disk. I think it's time for another round of optimization.

[pier4r]

(08-21-2017 02:10 PM)David Hayden Wrote:  I made it through the 17-digit suffixes without finding another solution. I found 20,510,922,752 of them. Even compressed, the file takes 30GB on my hard disk. I think it's time for another round of optimization.

Could you share the details?

Programming language? Platform? Setup? Code? (maybe an online repo?)

About that size should be interesting, like the free42 approach of werner.

[David Hayden]

(08-21-2017 03:39 PM)pier4r Wrote:  Could you share the details?

The code is written in C++. The idea is to build up lists of larger and larger suffixes to possible solutions. The input file is text. The first line is the number N of digits in the OUTPUT. This line is followed by a bunch of lines that contain all possible suffixes of length N-1. It writes to the output a file in the same format, but for one larger suffix size. You can kick start it with the input file:

Quote:1
0

Which generates as its output:

Code:

2
3
5
7
8

This means that any solution must end in 3,5,7, or 8. This file can be used as the input file to 2-digit suffixes. The output of that run can find 3 digit suffixes etc.

If the program finds a solution along the way, it writes it to the standard error output.

[Claudio L.]

This is an interesting thread! I don't have much time to try anything, but from what I've read the solutions are focusing on computing cubes of numbers and seeing which ones have the proper digits.
Has anyone tried the opposite way? Look at numbers with the correct digits, discard all the ones that cannot be perfect cubes (by the sum of their digits), and simply take the cube root of the ones left?
Here's the way I would try if I could:
Since only 2,3,5,7 are allowed as digits, a base-4 system could encode all possible digits. So let's use a binary integer to encode the digits, 2 bits per digit. For example with two 64-bit numbers combined into a 128-bit you can have 64 digits. Now all we have to do is count from 1 to 2^128 :-))
Write a routine that (decodes and) adds the digits to discard the ones that are not perfect cubes. There's other possibilities: for example a table with the last 2 or 3 digits can help cross out a few more.
If a number has a chance of being a perfect cube, then and only then we do 1/3*ln(A), then exp(), take the nearest integer, cube it and see if it matches.

I have no idea which percentage of numbers could be discarded this way, so it might be a terrible idea, but the inner loop is just bits, tables and ANDs, so it should be relatively efficient until it finds a candidate.

I just thought looking at it backwards might be worth exploring too.

[DavidM]

(08-23-2017 12:03 AM)Claudio L. Wrote:  ...
Has anyone tried the opposite way? Look at numbers with the correct digits, discard all the ones that cannot be perfect cubes (by the sum of their digits), and simply take the cube root of the ones left?
...

I had given some thought to this initially, but got hung up when thinking about how to generate all of the potential cubes that only contained the proper digits. Your idea about starting with a base 4 iteration and mapping the result to the proper digits is a nice way to achieve that. I also didn't realize until your mention of it that cubes have a characteristic "sum of digits" result (1, 8, or 9 apparently).

I'd still like to try to get something going on a 50g that will find the first known base within a reasonable (couple days?) time. I'd already been planning on a strategy involving the "only check numbers with good suffixes" approach. Perhaps I'll experiment with this one instead when I can get enough focused time to play with it!

[Claudio L.]

(08-23-2017 03:20 AM)DavidM Wrote:  

(08-23-2017 12:03 AM)Claudio L. Wrote:  ...
Has anyone tried the opposite way? Look at numbers with the correct digits, discard all the ones that cannot be perfect cubes (by the sum of their digits), and simply take the cube root of the ones left?
...

I had given some thought to this initially, but got hung up when thinking about how to generate all of the potential cubes that only contained the proper digits. Your idea about starting with a base 4 iteration and mapping the result to the proper digits is a nice way to achieve that. I also didn't realize until your mention of it that cubes have a characteristic "sum of digits" result (1, 8, or 9 apparently).

I'd still like to try to get something going on a 50g that will find the first known base within a reasonable (couple days?) time. I'd already been planning on a strategy involving the "only check numbers with good suffixes" approach. Perhaps I'll experiment with this one instead when I can get enough focused time to play with it!

Forget my idea. Seemed as a good starting point but then I realized that:

\((n+1)^3 = n^3 + (3n^2 + 3n +1)\)

In other words, the distance between one perfect cube and the next is \(3n^2 + 3n +1\). We are talking n around 12 to 16 digits, the distance for n=1e12 is 3e24, versus counting in base-4 across many, many numbers in that 3e24 range.
So my idea of going backwards would be orders of magnitude slower for large numbers, even if perhaps quick in the low range. There's no point in using it for large numbers.

One thing I see is the need for a command to extract individual digits from a number, so I added a DIGITS command to newRPL, where you provide the start and end range (in powers of 10, 0=unity, 1=tens, 2=hundreds, -1=tenths, etc.) and it extracts the digits, without having to go the string route.

[DavidM]

(08-23-2017 09:15 PM)Claudio L. Wrote:  Forget my idea. Seemed as a good starting point but then I realized that:

\((n+1)^3 = n^3 + (3n^2 + 3n +1)\)...

I haven't begun my 50g version yet (other than the brief loop timing), so no lost effort there. My first "check" was going to be converting the known cube to a base 4 number (mapping 2->0, 3->1, 5->2, 7->3) and seeing how far down the list it was. Without doing the math, my guess is it would have shown up requiring too many iterations anyway. But thanks for letting me know! I'm back to my original mostly-Saturn-code plan now it seems. Even that may not be speedy enough, as I'm probably only going to be able to limit the suffix check to 6 digits due to memory constraints. I'll eventually get around to at least trying this.

(08-23-2017 09:15 PM)Claudio L. Wrote:  One thing I see is the need for a command to extract individual digits from a number, so I added a DIGITS command to newRPL, where you provide the start and end range (in powers of 10, 0=unity, 1=tens, 2=hundreds, -1=tenths, etc.) and it extracts the digits, without having to go the string route.

Cool! Even Joe's tortuous "ear worm" challenges can cause creative results in unintended ways...

[Claudio L.]

(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.

[DavidM]

(08-23-2017 11:53 PM)Claudio L. Wrote:  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 that I had already implemented a couple versions of this for the PC (using a Delphi app) -and- having already seen Werner's description of his method, you have almost exactly described the method I was already planning to try on the 50g.

And, yes, 6 digit suffixes should number 4880. 7-digits yield 19520, 8-digits yields 78176, etc.

In order to speed things up a bit I'm planning to pre-build a list of 4880 6-digit ZINTS as a placeholder for all the suffixes from each "round". With each additional digit prefix, I'll update the zints and their count (in place via a Saturn routine) for the next round. That will keep me from having to create new suffix lists on the fly, and should reduce some of the GC events as well. Once I've reached the 6-digit suffix realm, I'll just keep it at that and run successive tests with incremental values of (n*10^6)+suffix.

[Paul Dale]

I do kind of wonder if it is worth using an highly optimised binary integer library (it is almost impossible to beat GNU's GMP here) or a less optimised decimal library for this sort of thing.


Pauli

[Werner]

(08-23-2017 11:53 PM)Claudio L. Wrote:  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.

That is part of it, yes. But soon you'll realise that this is too slow once the numbers get bigger and bigger.
I still use Free42 for now, and I precomputed all 20'031'232 12-digit numbers that have the trailing 12 digits of their cube in {2,3,5,7}, in ascending order (that is important, read on)
Then I started to narrow down the number of cubes to verify, by generating all prefixes with P numbers. We know the cubes must all be 2's, 3's, 5's and 7's, so all cubes must start with (P=1) 2,3,5, or 7 or (P=2) 22, 23, 25, 27, 32, 33 ... and so on. If you take P=6 we have 4^6 = 4096 prefixes, and I loop over them.
For each prefix <pf>, then, we know the cubes must be between
<pf>2222222.. and <pf>7777777... and so
(<pf>22222..)^(1/3) < x < (<pf>77777...)^(1/3)
Each additional order of P you generate will roughly halve the number of x's to verify.
For each x, then, I look up the next trailing 12 digits in my precomputed table (well it's REGS really) by a dichotomic search, and then verify each y
y := x-MOD(x,1e12) + REGS(i)
until y is larger than the upper limit (possibly going beyond the end of REGS and continuing at the beginning with x+1e12)

My current program (that is not finished yet ;-) will use this technique (with P=10) and a few other optimisations for 1e17 < x < 1e22.
I can use Free42 for x<1e34, but I'm afraid things will bog down even so.

BTW I'm pretty sure my technique can be used on a real 50g to find the first solution quite fast. I was planning on doing that to prove Joe wrong ("no current HP programmable calculator is fast enough to find the number in a reasonable amount of time")
;-))

Cheers, Werner

[pier4r]

(08-23-2017 09:58 PM)DavidM Wrote:  Cool! Even Joe's tortuous "ear worm" challenges can cause creative results in unintended ways...

Sure everything that is non-trivial foster the search of new ideas. Actual digits may be helpful also in userRPL (although one could create a program to extract those).