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

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