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