Re: [math-fun] Car Talk and prime numbers
From: "Michael Kleber"
Subject: Re: [math-fun] Car Talk and prime numbers
Heh: when was the last time someone responded to one of NJAS's questions by saying the equivalent of "See A096237"?
We (math-fun) discussed this in Feb-Mar 2003, eventually calling them "deletable primes," terminology which I think was preexisting. There seem to be infinitely many of them.
At the time, we came across one surprising observation, which (in the way of the web) is still sitting here: http://people.brandeis.edu/~kleber/temp/deletable.html
""" Question: Why do prime bases (in red) seem to have many fewer deletable primes than composite bases? """ A much simpler, in fact trivial, question is: Why do odd bases seem to have many fewer deletable primes than even ones? Then I'd posit that the real question is commuted to: Do prime bases have significantly fewer deletable primes than composite odd bases? Phil () ASCII ribbon campaign () Hopeless ribbon campaign /\ against HTML mail /\ against gratuitous bloodshed [stolen with permission from Daniel B. Cristofani] __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com
Phil Carmody wrote:
http://people.brandeis.edu/~kleber/temp/deletable.html """ Question: Why do prime bases (in red) seem to have many fewer deletable primes than composite bases? """
A much simpler, in fact trivial, question is: Why do odd bases seem to have many fewer deletable primes than even ones?
You're right, that does look like the right question to ask. When you say this is a trivial question, do you mean you know an answer, or just that it is easier to ask? --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
Look at the question this way: when you delete a digit from a random k-digit prime in base b, what is the probability that the result is a prime? The resulting number is a k-digit number in base b, so the first estimate of the probability is Product_{p<b^k} (1-1/p) ~ 1/log(b^k). However, if the digit removed is not the final one, the number cannot be divisible by any factor of b. So we can throw in a factor of 1/(1-1/p) = p/(p-1) for each prime p that divides b. Thus, if b is divisible by 2, the number of primes resulting from deletion can be expected to be about twice as high. A factor of 3 dividing b will enrich the primes by a factor of 3/2, etc. Note that only the unique prime factors count here - so the total enrichment is b/phi(b). This is not the density of deletable primes directly; this factor applies in each generation (to an increasingly good approximation; remember that we had to exclude the case where the last digit is deleted). This is complicated by the fact that many primes in any given base are deletable in multiple ways; so I am not prepared to make a quantitative prediction of relative densities. If this approximation is correct, one would expect slightly more deletable primes in base 105 (enrichment 105/48 = 35/16) than in base 106 (enrichment 106/52 = 53/26). Franklin T. Adams-Watters I assume that Phil was hinting that for b odd, all digits but one must be even, since removing an odd digit changes the parity. But this is essentially the special case p = 2 above: for b odd, half of all possible deletions will produce a number divisible by 2. The fact that the same digits are prohibited in each generation may make the number of deletable primes ultimately smaller in odd bases than the above argument suggests; this is not obvious to me, either way. -----Original Message----- From: thefatphil@yahoo.co.uk From: "Michael Kleber"
Subject: Re: [math-fun] Car Talk and prime numbers
At the time, we came across one surprising observation, which (in the way of the web) is still sitting here: http://people.brandeis.edu/~kleber/temp/deletable.html
""" Question: Why do prime bases (in red) seem to have many fewer deletable primes than composite bases? """ A much simpler, in fact trivial, question is: Why do odd bases seem to have many fewer deletable primes than even ones? Then I'd posit that the real question is commuted to: Do prime bases have significantly fewer deletable primes than composite odd bases? Phil ________________________________________________________________________ Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading spam and email virus protection.
Sorry, that should be a random (k+1)-digit prime. Franklin T. Adams-Watters -----Original Message----- From: franktaw@netscape.net Subject: Re: [math-fun] Car Talk and prime numbers Look at the question this way: when you delete a digit from a random k-digit prime in base b, what is the probability that the result is a prime? The resulting number is a k-digit number in base b, ... ________________________________________________________________________ Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading spam and email virus protection.
participants (3)
-
franktaw@netscape.net -
Michael Kleber -
Phil Carmody