Problems & Puzzles: Puzzles

Puzzle 226. Rolling Primes

Jeff Heleen sent the following nice puzzle "for the 5th anniversary of your website"

Let P(k), a prime, be a concatenation of an arrangement of k primes q(1), q(2), q(3),...q(k) such that when the individual primes q(k) are rolled successively from back to front the whole P(k) remains a prime.

Ex, if k=4 then:

P(4)=q(1)q(2)q(3)q(4)--> q(4)q(1)q(2)q(3)--> q(3)q(4)q(1)q(2)--> q(2)q(3)q(4)q(1)--> prime. 

Ex. P(4)=11.7.13.3 --> 3.11.7.13 --> 13.3.11.7 --> 7.13.3.11 --> prime.

The smallest examples of this for k=2 through 4 are:

k      P(k) (smallest)
2     3.7
3     3.7.67
4     11.7.13.3
5
6
7
8

(The dots in the P(k) are just for distinguishing individual primes for viewing.)

Questions: 

Q1. Can you fill out the rest of the table?
Q2. Is there any upper limit for k beyond which solutions are impossible?
Q3. Is there a general method for finding these solutions?

Solution:

Contributions came from Adam Stinchcombe and Johann Wiesenbauer. Both claimed that a) it was not formally ruled that the primes used should to be distinct b) the 'minimal' concept of the asked solutions is a kind of ambiguous. Let's see what they produced.

By her way Faride Firoozbakht found that the solution provided by Jeff for k=4 is not the smallest. She also found different solutions than the sent by Adam and Johann. See below.

Stinchcombe wrote:

{3,7,11,13,5443} produces the smallest example with k=5... And now, for k=6, I have {3, 7, 11, 13, 17, 253427}...I have failed to find a set for k=7 of the form {3,7,11,13,17,19,p} for p<25599131 [Faride Firoozbakht found that for p = 49365049, k=7]

Later he added:

After I realized that the qk were not described as distinct I found data of the form q1=q2=q3=...=q(k-1)=3 with qk given by

k qk
3 7
4 787
5 86423
6 1067497
7 920687
8 no qk<16650217

Wiesenbauer wrote:

I just had a look at your Puzzle 226, which was a little bit ambiguous this time for two reasons.

Firstly, you didn't explicitly exclude the case where two or more of the primes q(1), q(2),...,q(k) coincide, but I concluded from your examples that this is tacitly assumed. (Otherwise 3.3.7 is a smaller solution for k=3.)

Secondly, you didn't say what "smallest" example means here. After all, we are talking about k-element vectors rather than numbers and each example can be represented in k different ways due to the "rolling property".

Having said this I'd like to give what is my solution of Q1 for the cases k=5 and k=6:

k=5: 3.7.13.37.43
k=6: 3.13.11.7.37.53

As for Q2 and Q3, I can only guess that the answer is no, but I have no proof.

***

Faride Firoozbakht wrote:

As you can see he improved the 'minimal' solutions found by Jeff for k=4 and the 'minimal' solution found by Johann for k=5.

***

I anyone is interested in getting  more solutions I will rule out that the solutions must use distinct primes and that the minimal concept for each k is defined by the minimal prime of the k primes produced for the rolling procedure.

***

Johan Wiesenbauer wrote (August 5,03) more news and corrections to the previous results. He also got the smallest solutions for k=7 & k=8:

As for puzzle 226 I have rewritten my program form scratch due to your new precise minimal conditions and there were quite a few surprises when I tested all the cases up to k=8. What follows is the complete list of all minimal solutions along with the computation times of my Derive-program:

k=2: 3.7 (0.01s)
k=3: 3.7.67 (0.04s)
k=4: 11.3.17.7 (0.11s)
k=5: 11.31.3.37.7 (1.78s)
k=6: 11.71.7.3.29.97 (124.3s)
k=7: 11.13.67.3.31.7.37 (408.3s)
k=8: 11.3.7.67.47.23.53.97 (20h 35 min)

As you can see the solution of Faride Firoozbakht for k=5 is slightly wrong, because the fourth prime should be 37 and not 97. (In fact, her number 11313977 is divisible by 31, hence this is likely to be a simple misprint!)

The real surprise is the case k=6, where our former solution 11.7.37.53.3.13 is only number three (!) after 11.71.7.3.29.97 and 11.7.29.79.3.37 !

The case k=7 was very easy due to the special form of the minimal solution (starting with 11.13 and containing 3 and 7) as opposed to the case k=8, where my program rigorously proved that there are no other "rolling primes" among all 14-digit numbers starting with 11.

***