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

[Gerald H]

(08-07-2017 07:57 PM)Werner Wrote:  Free42 (what else?) is fast enough. Well, still a couple of hours.
1 405 349 897 ^3 = 2 775 577 757 352 755 375 573 357 273

Cheers, Werner

Nice to see another harpoon on the side of the Great White Whale.

& quite likely it's a 2nd member of the set of such cubes.

[Werner]

That's a bit cryptic, Gerald.
Have you found a 2nd number?
I improved my program to verify only the 4880 numbers out of 1e6 that, when cubed, have their last 6 digits in {2,3,5,7} and to check the most significant digit first. It can now find the first solution in 2 minutes, on my small laptop.
Werner

[Gerald H]

Sadly no, I haven't independently found a desired cube, but I have no reason to believe yours is the same as Joe's.

However I still seek the White Whale.

[DavidM]

(08-08-2017 03:39 PM)Werner Wrote:  I improved my program to verify only the 4880 numbers out of 1e6 that, when cubed, have their last 6 digits in {2,3,5,7} and to check the most significant digit first. It can now find the first solution in 2 minutes, on my small laptop.
Werner

A 98.3% reduction in time consumed? That's a nice day's work!

Care to share some pseudocode for your algorithm? With that kind of speed, it would seem not so far out of reach for some of the faster handhelds -- at least the ones that can be left on external power for a while. Looking for any past that first one is still likely a pipe dream, however.

Then again, perhaps your "small laptop" is speedier than you think!

[Joe Horn]

(08-08-2017 05:20 PM)Gerald H Wrote:  Sadly no, I haven't independently found a desired cube, but I have no reason to believe yours is the same as Joe's.

It is the same one, as it must be, because it is the only one which exists.

EDIT: I've checked by brute force every cube between 1 and 2.5E35, and this is the only one in that range. That's no proof that it's the only one between 1 and infinity, of course. But the Achilles in me says, "Yep, that's the only one there is."

[David Hayden]

(08-09-2017 01:02 PM)Joe Horn Wrote:  I've checked by brute force every cube between 1 and 2.5E35, and this is the only one in that range.

My revised program has checked possible bases up to 15 digits, so that means cubes on the order of 1E45 and has still found only that one.

[Joe Horn]

(08-09-2017 02:27 PM)David Hayden Wrote:  

(08-09-2017 01:02 PM)Joe Horn Wrote:  I've checked by brute force every cube between 1 and 2.5E35, and this is the only one in that range.

My revised program has checked possible bases up to 15 digits, so that means cubes on the order of 1E45 and has still found only that one.

Holy smokes, you're way ahead of me! This is great news, because it means I can shut down that UBASIC task and free up a CPU core.

[Gerald H]

I would suggest that the quest for a 2nd Horn cube is doomed to success & accuse those seeking it of logical intuitionism

https://en.wikipedia.org/wiki/Intuitionism

Brouwer himself

https://en.wikipedia.org/wiki/L._E._J._Brouwer

made such an assertion concerning the non-occurrence of 666 in the decimal expansion of pi.

The 666 was eventually found, & similarly for the 2nd, 3rd, 4th.....Horn cubes.

[Paul Dale]

I must admit that I've seen no proof that the are any further cubes of the required form.
That doesn't mean there aren't. It seems fairly reasonable that there would be. The onus of proof in this case lies with those claiming there is only a single solution.


Pauli

[Joe Horn]

(08-10-2017 07:44 AM)Paul Dale Wrote:  The onus of proof in this case lies with those claiming there is only a single solution.

Just thinking out loud: Since mathematics has not yet advanced far enough to even begin to prove such conjectures, the proof lies outside ANYBODY'S purview. This should come as no surprise, since mathematics (in its current stage of development) cannot even put a dent in the simple 3x+1 Problem. Our only option at this time is to enjoy searching for a counterexample using computer programming, which is why I titled this discussion "Fun with Numbers".

[DavidM]

(08-10-2017 01:26 PM)Joe Horn Wrote:  ...Our only option at this time is to enjoy searching for a counterexample using computer programming, which is why I titled this discussion "Fun with Numbers".

Like many challenges and questions posted here, it gives us a framework within which we can exercise our analytical methods to puzzle solving.

This "puzzle" has given me two distinctly different challenges:

- Blowing the dust off of my old version of Delphi in an attempt to incorporate a particular "biginteger" toolset. I've completed that, but unfortunately it doesn't appear to play nicely in a multi-threaded sandbox (which was another reason I wanted to try it).

- Attempting a SysRPL/Saturn approach that reaches the known root within a "reasonable" time on a real 50g. Haven't started this one yet, but I suspect it will largely depend on the ability to reduce the candidate pool before checking. There's probably a "sweet spot" in the pre-checking of root digits that balances benefit and cost, and I'm curious as to how that will play out.

Whether this is fun or not probably depends on the wiring of our brains. I suspect most regular visitors here have some common wiring patterns in our grey matter.

[Werner]

(08-09-2017 03:20 AM)DavidM Wrote:  Care to share some pseudocode for your algorithm?

I change it every day ;-)

I'm currently running with all 5'010'048 order-11 numbers precomputed, that is, all
numbers < 1e11, that, when cubed, have their 11 least significant digits in {2,3,5,7}.
This is the largest set I can use, as the next order will exceed 1e34 when cubed.
I had to write a specific routine to compute the 5 million order-11 numbers as brute force doesn't work with a range of 100 billion numbers ;-)

I use numbers A + b, where b is the 11-digit precomputed part and A = a.10^11.
Then (A + b)^3 = (X-r) + r

X = (A+b)^3, rounded to 34 digits
r = MOD(b^3,1e11), numbers known to consist only of 2,3,5 and 7
X-r is a number that ends in 11 zeroes, as the exact value of (A+b)^3 ends with the 11 digits of r.
This way I can go up to 1e34x1e11 = 1e45.

Then, I started narrowing down the numbers to verify, as follows:
All cubed numbers must start with either 2,3,5 or 7. For each of these, they must even be between x.222...eYY and x.777...eYY.
So I loop over

loop
(2.222.. eyy)^(1/3) < A < (2.777.. eyy)^(1/3)
(3.222.. eyy)^(1/3) < A < (3.777.. eyy)^(1/3)
(5.222.. eyy)^(1/3) < A < (5.777.. eyy)^(1/3)
(7.222.. eyy)^(1/3) < A < (7.777.. eyy)^(1/3)
yy := yy+1;
end loop;

A is increased in steps of 1e11, and at each step all 5 million numbers A+b are verified. Each step takes about 3 minutes ;-). At that rate I'll reach A=1e15 in 5 days. Trouble is, David Hayden has already gone that far and found nothing, and I'm not sure how to go beyond ;-)

Werner

[DavidM]

(08-10-2017 08:17 PM)Werner Wrote:  I change it every day ;-)

I'm currently running with all 5'010'048 order-11 numbers precomputed, that is, all
numbers < 1e11, that, when cubed, have their 11 least significant digits in {2,3,5,7}. ...

Well I just had to ask, didn't I. Interesting approach. The available memory in the 50g wouldn't allow for a very large pool of pre-configured suffixes, I'm afraid. I think I'll start with my original plan, which was to use a Saturn routine to cube/validate the last 5 digits of the current root before proceeding to check the entire root. That will exclude a fairly large percentage of the possible targets (about 98+% I believe). Even with that, I'm thinking a runtime >24hrs is likely.

I bet Claudio could work up a NewRPL version that would find the known root in a few minutes, though.

[Arno K]

I did it with a list of all 6-digit integer candidates (7 did not work, out of Memory on my virtual Prime) and then started a brute force attack in a loop, after cubing I first ruled out the first digit if it was 1, only then I checked all digits to be 2,3,5 or 7. Took about an hour to find the first solution, as it makes intense use of strings. So I now start thinking about another way to rule out digits from the beginning.
Arno

[DavidM]

(08-11-2017 04:43 PM)DavidM Wrote:  I think I'll start with my original plan, which was to use a Saturn routine to cube/validate the last 5 digits of the current root before proceeding to check the entire root. That will exclude a fairly large percentage of the possible targets (about 98+% I believe). Even with that, I'm thinking a runtime >24hrs is likely.

Probably should have done this simple test before posting the above, but thought I'd share this now that I have:

Timing a simple SysRPL loop that simply checks a loop counter shows a speed of about 2100 cycles/sec on a real 50g. While that seems fairly fast, it isn't fast enough to pursue the above-mentioned strategy for this application. Knowing in advance that the known-target is at the 1405349897th loop iteration, that implies a minimum of over 7 days worth of cycles just for the looping structure itself. The actual root/cube checking would add considerable more time, so I won't pursue that method any further.

I'll probably try a modified (lower "order") form of Werner's approach, and I may also go ahead and put together a Saturn routine for testing an exact integer to see how long it takes. That will help define whether this is worth pursuing further on this platform. Either way, it's been an interesting exercise.

Thanks Joe!

[David Hayden]

The biginteger library that I was using was based on base 2 so at least half of the time in my program was spent computing the digits in a number. So I cobbled together an small infinite precision class in base 10. It only has to do addition, multiplication and comparison. The new code running in a single thread takes 4.004 seconds to find the solution we have so far.

I had a multi-threaded version but found that cygwin (a system that provides a unix-like environment under windows) doesn't properly support multiple threads. Once I get this multi-threaded it should run at least twice as fast on my 4-core system. I also hope to look at the math a little more and see if I can pull some further algorithmic tricks to speed it up more.

[DavidM]

(08-14-2017 10:11 PM)David Hayden Wrote:  The biginteger library that I was using was based on base 2 so at least half of the time in my program was spent computing the digits in a number. So I cobbled together an small infinite precision class in base 10. It only has to do addition, multiplication and comparison. The new code running in a single thread takes 4.004 seconds to find the solution we have so far.

I had a multi-threaded version but found that cygwin (a system that provides a unix-like environment under windows) doesn't properly support multiple threads. Once I get this multi-threaded it should run at least twice as fast on my 4-core system. I also hope to look at the math a little more and see if I can pull some further algorithmic tricks to speed it up more.

That's nice performance, especially given your "cobbled together" solution. I suspect your cobbling is pretty well done. Just curious: how are you narrowing down the base selection? My initial testing was done with a simple "check the last digit of the base before proceeding" approach, then I shifted to something similar to Werner's pre-loading of base suffixes which sped things up quite a bit. The last version I tried pre-computes the pool of 7-digit suffixes (on my laptop that takes about 23 seconds) then finds that known root about 7 seconds later.

I was pretty disappointed when I realized that the multi-threaded attempt actually ran a tad slower than the single-threaded version on my 4-core laptop. Apparently something about the BigInteger library I'm using does a lot of locking behind the scenes. My reading indicates that this may actually be a memory manager issue with Delphi's compiled code when certain types of objects are used (notably strings fall into this category). So I don't want to blame it all on the BigInteger library.

Although "close" doesn't count for anything in this exercise, I was curious as to whether I'd find any matches if I simply ignored the first digit of the cube. I was pleasantly surprised to find one very quickly -- 1202247 missed being a match by only the first digit. I left the test running for quite a while but didn't find any others. Perhaps there are others out there that are only off by a single digit, and I wonder if we might learn anything that might narrow down the search by finding them.

[David Hayden]

(08-15-2017 04:31 AM)DavidM Wrote:  Just curious: how are you narrowing down the base selection?

See post #15 of this thread where I explain my algorithm.

As for multithreading, allocating and deallocating memory probably requires a lock so you might want to see if you can avoid that as much as possible.

[DavidM]

(08-15-2017 12:20 PM)David Hayden Wrote:  As for multithreading, allocating and deallocating memory probably requires a lock so you might want to see if you can avoid that as much as possible.

The author of the BigInteger library I'm using (Rudy Velthuis) mentions in his documentation that the BigInteger instances should be considered immutable, thus resulting in new allocations occurring every time an operation is performed that changes a value. Which, of course, is quite frequently while the main loop of the thread is running. It doesn't appear that there is any way to "pre-allocate" a variable and rewrite its contents. I suspect this is at the heart of the thread contention I've seen.

[David Hayden]

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.