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.
...
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.
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?