Hacker News Reader

Comment by misja | Hacker News Reader

Am I overlooking something, or is it obvious that if this is the single largest bi-truncatable prime known so far, that any larger one has to contain this prime in its middle?

So finding a new largest bi-truncatable prime is just a matter of trying to add each single digit at both sides of this prime; if any of them is again a prime, we have a new largest and if none of them is (which I guess is the case because the author must have tried this out already), then there exists no larger bi-truncatable prime.

View on HN

Yes, you're overlooking something. Look at the 61-digit prime, 9968667351197964859567689459993713773777797133337931717971339. 99% of all 61-digit primes are less than that prime. The 63-digit prime above it prepends a '2' and appends a '7'. If any of the 99% of 61-digit primes less than that prime prepend any digit between 3 and 9 while remaining bitruncatable, then they would be a bigger 63-digit prime.

There's no guarantee that the biggest N+2 digit prime comes from the biggest N digit prime. It could come from the smallest N digit prime if that's the only N digit prime that becomes an N+2 digit prime by prepending a 9.

If by "this" you mean the 83-digit prime in the question, then no. There's no indication that there are no other 83-digit bitruncatable primes - that's just the only one the author had found.

If you mean the sole 97-digit solution given in the comments, the implication that all the bitruncatable primes have been found and enumerated by your method, and the assertion that there are no such 99-digit primes - then yes, that looks pretty legit, though I'd want to see an independent verification before accepting it as a proof, since computer programs have bugs.

I've written some simple code and verified that commenter's numbers through 19 digits.

Edit: parallelized the code and proved through 19 digits. That's where I'm stopping due to the uint64 space limitations.

It looks exactly like a Project Euler question, I wouldn't be too surprised if it's already been solved there in the forums.

> I'd want to see an independent verification

I wrote a solver for this problem: https://github.com/jwilk/bitruncatable-primes

I haven't run it yet, because I don't have a powerful-enough machine at hand. It needs ~6 GB of RAM and ~20 CPU core-hours.

After fixing exorbitant memory use, I have now independenty verified that

7228828176786792552781668926755667258635743361825711373791931117197999133917737137399993737111177 (97 digits)

is indeed the biggest bi-truncatable prime.

This was done under assumption that zero digits are not allowed. If they are allowed, bigger bi-truncatable primes exists, such as:

90072457733413689120801410250233316614403998951220231333193991731791997911317971131797197339199333933 (101 digits)

I would say so, too. Given there are no bi-truncatable primes with length 99, there cannot be any larger ones.

Reply on news.ycombinator.com