What is the largest bi-truncatable prime? | Hacker News Reader

What is the largest bi-truncatable prime?

primepuzzles.net

37 pointsheadalgorithm19 comments

So, is there a truly largest one?

Let’s assume we have B(n) bitruncatable primes of length (n)

For B(n+2), we have at most 45 times that number (digit added at the front can’t be a zero; digit added at the back must be odd)

The fraction of them that’s prime is about 2/log(10^(n+1)) (factor 2 added because we already dropped all even numbers; n+1 in the denominator as being halfway between n and n+2 digits; neither factors affect the conclusion)

That gives us the recurrence relation

    B(n+2) ~= 90B(n)/log(10^(n+1))
            = 90B(n)/((n+1)log(10))
            = (90/log(10)) B(n)/(n+1)

That number gets smaller and smaller once n > 90/log(10) (about 39)

So, I think it’s very likely there is a largest one.

This line of thought applies to all integer bases > 2 (there isn’t a largest one in base 2 because there isn’t any in base 2)

I think B(n+2) is at most B(n)*36. you can’t append a 5 to get a prime number.

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.

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

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)

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.

I find it difficult be interested in these, primes are primes; bi-truncatable are base-10 specific. It feels more like numerology in the same way that we assign meaning to powers of 10 and the natural world does not.

"What's the smallest power of pi that spells your name when encoded in base64?"

There's probably an infinite set of such powers inside any neighborhood of zero.

I was going to say, that irrationality would mean that any power of pi would contain your name given enough digits.

That logic is incorrect. The base 2 Liouville number (https://en.wikipedia.org/wiki/Liouville_number) is transcendental, so surely irrational, but mostly contains two repeated characters.

That’s not true. To prove that any digit sequence will eventually appear, you need to show the number is normal (https://en.wikipedia.org/wiki/Normal_number), which is much, much harder to prove than being irrational or even transcendental. It has pretty much only been done for numbers specifically constructed to be normal, and so not including pi.

Strictly speaking that property hasn't been proven of pi (nor whether this would still hold for powers of pi). As you may have gathered irrationality is a weaker property.

Irrationality would be enough to guarantee that you can find a power where your name is right at the start. You do need log(pi)/log(10) (or whatever base you're using) to be irrational for that to work, but I think you can prove that using the fact that pi is transcendental.

I don't think anyone is trying to ascribe any meaning to this.. like the name of the site implies, it's just a puzzle.

yes, i wasn't suggesting it should ascribe meaning, only that it's particular artificiality does not allure me.

Reply on news.ycombinator.com