289. Palprimes inside the infinite primes concatenated

Problems & Puzzles: Puzzles

Puzzle 289. Palprimes inside the infinite primes concatenated

Here you are asked to find palprimes inside of the infinite string S of the primes orderly concatenated:

S = 2.3.5.7.11.13.17.19.23.29. ...

The first and the second palprime (shown in red) found in S are "11" and "131", as you can see below:

S = 2.3.5.7.11.13.17.19.23.29. ...

Here is a list of the smallest palprime found of certain length (L) that I have found this last week:

L of the palprime	Palprimes in S
2	3.5.7.11.13
3	5.7.11.13.17
5	71.73.79.83.89.
7	6329.6337.6343.6353.6359.
9	33119.33149.33151.33161.33179.
11	46619.46633.46639.46643.46649.
13	233279.233293.233297.233323.233327.
15	1488343.1488371.1488379.1488413.1488419.
17	3333307.3333311.3333313.3333331.3333373
25	104540057.104540063.104540113.104540131.104540141.
27	162826091.162826109.162826117.162826171.162826199.
?
?
?

As a matter of fact the palprime for L=27 was previously (Dec. 2003) found by DW who made a similar search but looking just for palindromes not for palprimes. It was his search that inspired my own search.

The complete list of the DW palindromes found by DW is in one of the plates of the always interesting site of Patrick De Geest, World of Numbers. BTW the largest palindrome that DW has found is one of L=34:

234843233.234843239.234843277.234843293.234843299

Questions:

1. Can you get the next three entries for the Table above?

As you can see all the palprimes of the Table above are formed using digits of at the most four (4) consecutive primes.

2. Can you get a palprime that uses digits of five (5) or more consecutive primes?

The absolute solver of this puzzle is Giovanni Resta who did a splendid work with a deep search for solving the Question 1 of this puzzle. Q2, remains for the future.

On the other hand, Faride Firoozbakht interesting contribution explains how to find large palprimes using two consecutive primes of certain type.

Giovanni Resta wrote (5/11/04):

The search was performed until the prime 6,797,450,882,947 and I found these new solutions: (the palprime is between ())

29 = 1(1516151139 11516151193 11516151)211
31 = (13610163179 13610163197 136101631)99
33 = 3694149620(3 36941496313 36941496331 3694149633)7
37 = (1033454330113 1033454330131 10334543301)37
39 = 107366637007(9 1073666370113 1073666370131 107366637019)3
41 = 15102420150(97 1510242015137 1510242015173 1510242015179)

I did not find any solution, maximal or not, spanning 5 prime numbers (search ended at 3,219,142,271,783)

Just for curiosity, asking only for palindromes and not for palprimes, I got these two solutions which beat the cited with 34 digits and span 5 primes.
51 = (1666661119 11666661137 11666661173 11666661191 11666661)203
53 = (46735376419 46735376437 46735376473 46735376491 467353764)97 (search ended at 2,182,644,045,683)

On my request he explains his technique:

As usual, I used the primegen library by D. J. Bernstein ( http://cr.yp.to/primegen.html ) to generate the prime numbers. It is amazingly fast, in particular for the generation of primes below 2^32, but can reach 10^13 or more, I think. I use language C under Linux with 64 bit (long long int) integers together with the gnu GMP library for computations with multiprecision numbers and also for primality testing.

I can use half a dozen of quite old and sometimes underused Linux workstations, whose computational powers differ. Say a couple of 800 MHz Pentium III, a couple of Athlon 1400+ and a Pentium 4 at 2.4GHz. I used the Pentium 4 for this puzzle...
<http://cr.yp.to/djb.html> This problem was solved with a very naive approach.
I simply generated the prime numbers in long chunks, say one million of digits each (and partially slightly overlapping).

I wrote them down as in a long string, adding a bit (64 in decimal) to the first character of each prime, in order to be able to recover easily the sequence in case of success.

Then I checked for the presence of palindromes of a given min length, disregarding that signaling bit. The partial overlapping was needed to avoid border effects when I pass from one chunk to the next one.

***

Faride wrote:

We can get many large palprimes that uses digits of only two consecutive primes so this case is trivial.

For example :

p=1(404).1223334444555556666667777777666666555554444333221

next-prime(p)=p+1820

p1=1(70).1223334444555556666667777777666666555554444333221.1
(70) (189-digit)

p2=1(83).1223334444555556666667777777666666555554444333221.1
(83) (215-digit)

Or :

q=1(487).333 (490-digit) next-prime(q)=1(487).633

q1=1(34).333.1(34) (71-digit)
q2=1(71).333.1(71) (145-digit)
q3=1(166).333.1(166) (335-digit)

All primes are rigorous primes (certified by primo).

We can also find many large such probable primes.

As you know the case that we use digits of more than two consecutive primes is not easy.

A trivial example with length 23 :

r = R(19) = 1(19) r`=next-prime(r)=r+60
r.r`=1(19).1(17).71=1(23).1(13).71 = R(23).1(13).71

so R(23) is in the concatenation of r & r`.) r.r`= R(23).111111111111117

***

J. K. Andersen solved Q2, using a very clever approach. Enjoy it:

Question 2.

I have found palprimes (61 & 105 digits) using digits of 5 and 6 consecutive primes.

5 primes:

108767(976780119 108767976780137 108767976780173 108767976780191 1087679)76780289

6 primes:

19605310868013506908(9 196053108680135069119 196053108680135069137 196053108680135069173 196053108680135069191 19605310868013506919)7

The GMP library was used for prp'ing. Marcel Martin's Primo proved all primes.
I don't know whether they are minimal. The search was targeted at certain digit patterns.

Finding 5 primes.
Let M run through palindromes with an odd number of digits.
Search M so these four numbers are consecutive primes:
M19 M37 M73 M91
(19 M37 M73 M91) is a palindrome.
The next prime will also (almost always) start with the digits of M.
This gives potential palprimes on the form (A19 M37 M73 M91 B), where A is any number of digits taken from the end of M and B=reverse(A) is the same number of digits from the start of M.

My program found 28 solutions in the first minute. The first was for M = 1087679767801, with 7 digits in A and B:
108767(976780119 108767976780137 108767976780173 108767976780191 1087679)76780289

Finding 6 primes.
Let M be palindromic and find 5 consecutive primes:
M19 M37 M73 M91 M9x, where x is 3, 7 or 9.
If the prime before M19 ends with 9 then there is a palindrome
(9 M19 M37 M73 M91 M9)
If the prime ends with x9 then there is a 2nd palindrome
(x9 M19 M37 M73 M91 M9x)

This search was harder. The first solution palprime is 105 digits for M = 1960531086801350691, without the extra x chance:
19605310868013506908(9 196053108680135069119 196053108680135069137 196053108680135069173 196053108680135069191 19605310868013506919)7

By the way, this solution also has palprimes spanning 2 and 3 primes with the same center.

What about 7 primes?
I found potential patterns extending from the pattern for 6 primes.
Let M be palindromic again with first/last digit m. Search for (palprime):
C(mx9 M19 M37 M73 M91 M9x m)
Here Cmx9 (any digit sequence C allowed) is the required form of the prime before M19. This turns out to be a serious computational challenge.
x is 3, 7 or 9. This makes x9 larger than 19, but Cmx9 must be smaller than M19. The last digit of M is m, so C must be smaller than (M excluding the ending m).
This means Cmx9 and M19 must differ on the 4th digit (or more) from the right. Then their difference becomes above 900. Finding two consecutive primes with such a large difference probably requires reasonably large numbers. However large numbers makes it computationally harder to find all the required primes.

The palindromic center sequence with all primes starting with M (M19 M37 M73 M91 M) is limited to this length for the above pattern because primes end in 1,3,7,9. We can get a longer potential sequence by fixing the last digit to some x.
An easier pattern for 7 primes seems to be (with possible variations):
(M27x M36x M45x M54x M63x M72x M)
There are additional palprime chances spanning 7 primes by removing the outermost digits. The total prime gaps in this pattern is only 450, compared to more than 900 earlier. The pattern has gaps of 360 for palindromes spanning 6 primes, so the earlier used pattern was much better when only 6 primes was targeted.
The new pattern can be extended to more than 7 primes. I don't think the old can.

I guess there are infinitely many solutions with 7 primes for both patterns. It still looks hard and I have not searched for them. Maybe somebody can succeed or find a better pattern?

***

Records | Conjectures | Problems | Puzzles