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(k1)=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 kelement
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:
For k=4 the smallest prime is 11.3.17.7 and
11.7.13.3 is the second solution.
For k=5 the smallest solution is 13.31.3.97.7 .
For k=6 the smallest solution is 11.7.37.53.3.13
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 Deriveprogram:
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 14digit numbers starting with
11.
***
