[math-fun] Prime Question: Whoops
What I meant was, Let a prime be a good prime if a digit can be deleted leaving either the empty string or a good prime. Are there infinitely many good primes?
No no no, these probabilistic arguments are going the wrong direction.
Let a prime be a good prime if a digit can be deleted leaving either the empty string or a good prime. Are there infinitely many good primes?
Let's be very naive and say that all we know is the prime number theorem, Pr(n is prime) =~ 1/ln(n). Then E(# n-digit good primes) / E(# (n-1)-digit good primes) =~ (# ways to add a digit) * (Pr(an n-digit number is prime), which is around (10n) * (1/(n ln 10)) = 10/ln 10 =~ 4.34. So the number of good primes should grow exponentially. In fact, the quick Mma hack gives this count (NJAS note): # n-digit good primes: 4, 16, 94, 585, 3788, 25768, 182762 Successive ratios are 4., 5.875, 6.2234, 6.47521, 6.80253, 7.0926, so 4.34 looks like a serious underestimate. I'd guess most of the difference comes from the higher odds of getting a prime after adding a digit 0,3,6,9 for congruence mod 3 reasons that have already been mentioned. Hmm: if this goes in the EIS, let's use the apparently accepted term, "deletable prime" (says Google). --Michael Kleber kleber@brandeis.edu
I agree. Deletable prime it is. ----- Original Message ----- From: "Michael Kleber" <kleber@brandeis.edu> To: <math-fun@mailman.xmission.com> Sent: Thursday, February 27, 2003 12:07 PM Subject: Re: [math-fun] Prime Question: Whoops
Hmm: if this goes in the EIS, let's use the apparently accepted term, "deletable prime" (says Google).
--Michael Kleber kleber@brandeis.edu _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
First, what about other bases besides ten? [This is normally dan asimov's question, isn't it?] Second, the probability calculation is ignoring the fact that there are several ways to add a digit and get the same result -- in particular, inserting a digit next to an identical digit produces the same number no matter which side of the digit the insertion happens on. This immediately reduces your "10n" to at most "9.5n", I think. The reduction is relatively more severe for base 2. --ms -----Original Message----- From: math-fun-admin@mailman.xmission.com [mailto:math-fun-admin@mailman.xmission.com]On Behalf Of Michael Kleber Sent: Thursday, February 27, 2003 12:08 To: math-fun@mailman.xmission.com Subject: Re: [math-fun] Prime Question: Whoops No no no, these probabilistic arguments are going the wrong direction.
Let a prime be a good prime if a digit can be deleted leaving either the empty string or a good prime. Are there infinitely many good primes?
Let's be very naive and say that all we know is the prime number theorem, Pr(n is prime) =~ 1/ln(n). Then E(# n-digit good primes) / E(# (n-1)-digit good primes) =~ (# ways to add a digit) * (Pr(an n-digit number is prime), which is around (10n) * (1/(n ln 10)) = 10/ln 10 =~ 4.34. So the number of good primes should grow exponentially. In fact, the quick Mma hack gives this count (NJAS note): # n-digit good primes: 4, 16, 94, 585, 3788, 25768, 182762 Successive ratios are 4., 5.875, 6.2234, 6.47521, 6.80253, 7.0926, so 4.34 looks like a serious underestimate. I'd guess most of the difference comes from the higher odds of getting a prime after adding a digit 0,3,6,9 for congruence mod 3 reasons that have already been mentioned. Hmm: if this goes in the EIS, let's use the apparently accepted term, "deletable prime" (says Google). --Michael Kleber kleber@brandeis.edu _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Thu, 27 Feb 2003, Mike Speciner wrote:
First, what about other bases besides ten? [This is normally dan asimov's question, isn't it?]
Yeah, I was just short on time when I sent that email. All the same, except that...
Second, the probability calculation is ignoring the fact that there are several ways to add a digit and get the same result -- in particular, inserting a digit next to an identical digit produces the same number no matter which side of the digit the insertion happens on. This immediately reduces your "10n" to at most "9.5n", I think. The reduction is relatively more severe for base 2.
Oh! Good point. Actually it reduces it to "9n", right? -- you eliminate duplication by saying that you may never insert the digit 'd' immediately after an existing 'd', so there are only b-1 choices in each slot. So the slightly-less-dumb probabilistic argument is that ultimately adding another digit (in base b) multiplies the number of good primes by around (b-1)/ln b. For b=2 this is around 1.44, so there's cetainly the danger that bad luck will snuff out the good primes before there are enough of them that the asymptotics win out. Oh! -- technically that's exactly what happens, I suppose: the decided lack of 1-digit primes in base 2 means the recursive definition can't even get started :-). If we define base-2 deletable primes to include 2 and 3 and work up from there, things start off dicey with small numbers of digits: d base-2 d-digit deletable primes ---------------------------------- 2 2=10, 3=11 3 5=101, 7=111 4 11=1011, 13=1101 5 19=10011, 23=10111, 29=11101 6 37=100101, 43=101011, 47=101111, 53=110101, 59=111011, 61=111101 7 73=1001001, 79=1001111, 83=1010011, 101=1100101, 107=1101011, 109=1101101 So we seem to make it out of immediate danger; the sequence of number of deletable base-2 primes with d digits goes: d: 1, 2, 3, 4,... #: 0, 2, 2, 2, 3, 6, 6, 11, 18, 31, 49, 87, 155, 253, 427, 781, 1473, 2703,... For base b>2, here's how the count starts, in case anyone cares. I haven't really thought about the numbers at all, but since I wrote the maple program to be base-independent, here's a bit of data for them as care: base # deletable base-b primes with 1, 2, 3, 4, 5 digits: ------------------------------------ 3: 1, 2, 4, 7, 13 4: 2, 3, 9, 26, 75 5: 2, 6, 14, 32, 69 6: 3, 7, 32, 135, 597 7: 3, 7, 21, 59, 184 8: 4, 14, 50, 238, 1123 9: 4, 14, 58, 221, 911 10: 4, 16, 94, 585, 3788 11: 4, 16, 73, 288, 1117 12: 5, 25, 186, 1398, 11500 13: 5, 22, 97, 404, 1775 14: 6, 34, 242, 1840, 15211 15: 6, 33, 237, 1515, 9924 16: 6, 38, 293, 2367, 20132 17: 6, 38, 197, 962, 5048 Hmm, interesting -- base p (prime) definitely looks like it yields relatively few deletable primes. Clearly much more to this story. Here's to empirical observation... --Michael Kleber kleber@brandeis.edu
participants (4)
-
David Wilson -
Jud McCranie -
Michael Kleber -
Mike Speciner