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.  

  1. Find other couples like this one.
  2. Find larger SID-primes than SID(5,689).



(*) See the sequence A006510


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




Records   |  Conjectures  |  Problems  |  Puzzles