Problems & Puzzles: Puzzles

Puzzle 36.-  Sequences of “descriptive primes”

Let’s define the sequence of descriptive terms the following way: starting from an arbitrary one, each next term describes the previous terms according to the rules stipulated in A005150… For example, the term after 1211 is obtained by saying "One 1, one 2, two 1's", which gives 111221.”

From now on, we are going to ask only for sequences of descriptive primes:

a) All the six (6) terms of the following three (3) sequences are primes, and obtained from its respective first prime term, according the rule described above:

233, 1223, 112213, 21221113, 1211223113, 11122122132113. (CBRF, 22/1/99)

120777781, 111210471811,  311211101417111821, 13211231101114111731181211,
111312211213211031143117132118111221,
31131122211211131221101321141321171113122118312211
(CBRF 23/1/99)

402266411, 141022261421, 11141110321611141211, 31143110131211163114111221, 132114132110111311123116132114312211, 1113122114111312211031133112132116111312211413112221 (CBRF, 24/1/99)

These three (3) are the only 6 terms sequences with a starting prime less than 10^9 (CBRF, 24/1/99)

b) G.L. Honaker, Jr. discovered (15/1/99) a sequence of this type starting with the pal-prime 373 and composed by 4 terms:

373 (palprime), 131713, 111311171113, 311331173113

This find was a by-product of his sequences A036978 and A036979. See also the Patrick De Geest's page about Palindromic Primes

Now, my questions are: Can you find:

a)     a larger sequence of (>6) primes?

b)     Another sequence of 6 terms

c)     Another sequence of 4 terms, starting with a palprime?

p.s. If you think that this kind of sequences is of null mathematical interest, please see also: http://www.mathsoft.com/asolve/constant/cnwy/cnwy.html

Solution

Mike Keith has made some calculations about the relative probability to find chains of this type of different length. Here is his e-mail (23/1/99):

"G.L., Carlos -

I am intrigued by your chains of descriptive primes, though I probably don't have time to do any number crunching.. However, I did do some theoretical thinking about it.  I used the prime number theorem, and Conway's theorem which says that self-descriptive sequences grow (in terms of the number of digits) proportional to 1.3^n to calculate how many self-descriptive sequences one should have to examine (of length N) in order to find one that is all primes.  This assumes starting from a prime number (so the probability of N=1 is 1).  Here are the answers:

2       10.60   0.082000        12
3       13.79   0.063077        193
4       17.92   0.048521        3985
5       23.30   0.037323        106761
6       30.29   0.028710        3718550
7       39.37   0.022085        168375288
8       51.19   0.016988        9911205393
9       66.54   0.013068        758434278834
10      86.50   0.010052        75448877533454
11      112.46  0.007733        9757329361156934
12      146.19  0.005948        1640410343889412900

Note that I had to make an assumption about how many digits the FIRST prime in the chain is.  I assumed about 8.  The first number in each line above is N, the next is the number of digits in the last prime in the chain, the next is the probability of the last number being prime, and the last column is the reciprocal of the probability of the whole chain being prime - in other words, the number of chains you should have to examine, on
average, to find one that's all primes.

Note that N=7 is about 45 times harder than N=6.  That's not so bad! - if Carlos finds 45 chains of length 6, he should find one of length 7. Well, that is assuming my calculations here are correct!"

***

At 29/01/99 Keith has made " a more careful calculation of the probability of finding self-descriptive prime chains of various lengths "

"This calculation takes into account the number of digits in the starting number of the chain (rather than always assuming a "middle-of-the-road" value of 8, which I think is what I used last time).

As before, this uses Conway's theorem that the number of digits in the nth member of a self-descriptive sequence is proportional to n^1.3, and uses the (1/ln x) estimate for the probability of a number being prime.  I double this probability in every element of the chain after the first one, because if the chain starts with a prime we know the remaining numbers cannot be even.

This predicts that there should be 2 chains up to 10^9, whereas you have found 3 - pretty good agreement.  The 6-element chain that starts with 233 is VERY remarkable - we should not expect to find one until around 10^9.

It also predicts the first length-7 chain will occur around 10^11, and the first length-8 chain (which I can barely imagine ever finding!) around 10^13.  But, of course, we may be lucky and find one earlier."

***

Mike Keith (4/2/99) has found other 3 chains of 6 terms. The initial terms are:

4) 1171465511
5) 1623379207
6) 1955771683

***

Keith has defined the following concept: T/F, where T is the total number of digits in all primes in the chain and F is the number of digits in the first prime in the chain. He describe this number as "a measure of how much information is contained in the first prime", and observes that T/F(1623379207) = 214/10 = 21.4 is the largest value calculated, considering the 6 chains of 6 terms obtained up today.

***

Tiziano Mosconi found (10/9/01) four examples of sequences starting with a palprime, each of 4 members large.

121393121 , 111211131913111211 , 3112311311191113311221, 13211213211331193123212211

304989403 , 131014191819141013 , 111311101114111911181119111411101113, 311331103114311931183119311431103113

15826662851 , 111518123612181511 , 311511181112131611121118111521, 13211531183112111311163112311831151211

36652925663 , 132615121912152613 , 111312161115111211191112111512161113 , 31131112111631153112311931123115111211163113

***

BTW, I would like to pose one additional question: exist odd numbers (not ending in "5" ) such that they produce sequences of exclusively composite numbers?

***

One day later Tiziano also found an example of palprimes starting a sequence of 5 members:

1344409044431  , 111334101910341311  ,   3123141110111911101314111321  ,
1311121311143110311931101113111431131211  ,
111331121113311413211013211913211031133114132113111221

***

Walter Schneider has found (23/9/01) one more sequence of length 6 below 10^10:

I have done an exhaustive search up to 10^10 and found one more sequence of length 6 starting at 5 558 223 787. This means that there are exactly 7 sequences of length 6 with a starting prime less than 10^10 and no sequence of length 7 (or more).

In the next days I will try to extend the search to 10^11. I will inform you if new results are available.

the search for descriptive primes of length 6 or more has just arrived at starting number 22*10^9. The results are:

* In total there are 19 sequences of length 6 and

* One sequence of length 7 starting at 19.972.667.609 (found today at 25.09.2001)

For details and a complete list look here.

So, we have already a new record!... Congratulations Walter

***

 Records   |  Conjectures  |  Problems  |  Puzzles