Problems & Puzzles:
Puzzles
Puzzle 91.-
Primes
with the Smoothest
Increasing Digits
(SID primes)
Here
are some examples of the SID primes:
...,
23, 67, 89, 4567, 78901, 678901, 23456789,
45678901, 9012345678901, 789012345678901, … (*)
For
simplicity I will describe these numbers as SID(d,
L) where d is its initial digit and L is its length [obviously we need not
to declare the final digit because it is calculable by (d+L-1) mod 10].
Hence,
789012345678901
= SID(7,15) and its ending digit is
(7+15-1) mod 10 =1
The
largest SID-prime that I have
calculated is SID(5, 689)
But
also happens that SID(7,5) =
78901
is the first SID-prime such that 10987,
its reversible number, is a prime too.
- Find
other couples like this one.
- Find
larger SID-primes
than
SID(5,689).
______
Notes
(*)
See the sequence A006510
Solution
Chris Nash wrote (26/04/2000):
"I set up PrimeForm to do this search,... So far, the only
new SID prime I have found is SID(8,7066)=8901......0123...(Of
course this is only known to be probable prime at this point). They are
indeed very rare...How rare are they? Well a random n-digit number is
prime with probability about 1/2.302n. For each number of digits we test
9 numbers (there are 9 possible values of the first digit). So we expect
9/2.302 * log(D) SID primes of D digits or less.
This means we would expect:
9 SID primes between 1 and 10 digits (there are actually 8)
9 between 10 and 100 digits (I think I found 8 here)
9 between 100 and 1000 digits (here I found 15?)
9 between 1000 and 10000 digits. I have only tested 4000-8000 digits,
but so far only found one!"
An later, himself wrote again:
" I've just calculated the expected number of reversible SID
primes, and it makes me expect there aren't any more. Last time I
mentioned that the probability a random n digit number is prime is about
1/2.302n - 2.302 is log(10). So the probability two ndependently random
n digit numbers are both prime is 1/(2.302n)^2.
So at first we might expect to find sum(1/n^2).9/(2.302^2)
reversible SID primes. sum(1/n^2) is pi^2/6. But a number and its
reverse are not independent. If one is not divisible by 3, neither is
the other. Similarly for the factor 11, and other primes that depend on
digit patterns. So I multiplied this result by (3/2).(11/10). And the
answer I got was just under 5.
Since you have already found one, and there are four others (2, 3,
5, and 7 are 'trivial') I think that all the reversible ones you can
expect to find have already been found - I don't expect there to be any
more!"
***
|
