What is the largest bi-truncatable prime? • Hacker News Board

Re: What is the largest bi-truncatable prime?

#11

Post by dmurray » Fri, May 03, 2019, 3:51 PM UTC

jemfinch wrote: post #7

dmurray wrote: post #4

Earlier quoted context omitted.

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,…

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.

Re: What is the largest bi-truncatable prime?

#12

Post by ktm5j » Fri, May 03, 2019, 4:17 PM UTC

tomxor wrote: post #6

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.

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.

Re: What is the largest bi-truncatable prime?

#13

Post by Someone » Fri, May 03, 2019, 4:55 PM UTC

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)

Re: What is the largest bi-truncatable prime?

#14

Post by hervature » Fri, May 03, 2019, 4:57 PM UTC

enriquto wrote: post #10

tedunangst wrote: post #9

Earlier quoted context omitted.

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

Re: What is the largest bi-truncatable prime?

#15

Post by Someone » Fri, May 03, 2019, 6:51 PM UTC

hervature wrote: post #14

enriquto wrote: post #10

Earlier quoted context omitted.

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.

Re: What is the largest bi-truncatable prime?

#16

Post by tomxor » Fri, May 03, 2019, 7:52 PM UTC

ktm5j wrote: post #12

tomxor wrote: post #6

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.

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.

Re: What is the largest bi-truncatable prime?

#17

Post by Analemma_ » Fri, May 03, 2019, 9:19 PM UTC

hervature wrote: post #14

enriquto wrote: post #10

Earlier quoted context omitted.

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

Re: What is the largest bi-truncatable prime?

#18

Post by sotsoguk » Sat, May 04, 2019, 12:40 AM UTC

Someone wrote: post #13

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 fa…

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

Re: What is the largest bi-truncatable prime?

#19

Post by contravariant » Sat, May 04, 2019, 1:55 AM UTC

hervature wrote: post #14

enriquto wrote: post #10

Earlier quoted context omitted.

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.

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.

Re: What is the largest bi-truncatable prime?

#20

Post by jwilk » Sat, May 04, 2019, 7:03 AM UTC

dmurray wrote: post #4

misja wrote: post #2

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…

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,…

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