Problems & Puzzles: Puzzles
Puzzle 36.- Sequences of descriptive primes
Lets 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,
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:
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
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 -
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:
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:
111334101910341311 , 3123141110111911101314111321 ,
Walter Schneider has found (23/9/01) one more sequence of length 6 below 10^10:
Two day later he added:
So, we have already a new record!... Congratulations Walter