Problems & Puzzles: Puzzles

Puzzle 718 A follow up to Puzzle 700 W. Edwin Clark sent the following puzzle Call a list (p[1],p[2],...,p[n]) of primes p[i] permutable if the concatenations of all of the n! permutations of the primes in the list are distinct primes. It is easy to find permutable list of primes for n = 2 and n = 3. For example, for n = 2 we have the permutable lists: [3, 7] since 37 and 73 are distinct primes and  [523, 541] since 523541 and 541523 are distinct primes. For n = 3 we have the permutable lists:   [7, 11, 43], since 71143, 74311, 11743, 11437, 43711, 43117 are distinct primes and [443, 463, 509], since  443463509, 443509463, 463443509, 463509443, 509443463, 509463443 are distinct primes. Q1 Do there exists permutable lists of primes of length n > 3? Q2 If not Q1 then find for length n > 3 the largest possible number of distinct primes among the n! different concatenations of a lists of n primes possibly not all distinct.

---

Contributions came from Emmanuel Vantieghem and W. Edwin Clark

***

Emmanuel wrote:

Maybe I'm wrong, but at first sight  puzzle 718  is the same as puzzle 688...
 

Admitting the primes eventually to be equal is not really changing the problem since we never get  n!  different concatenations as soon two (or more) of the primes are the same.

Nevertheless, actually I'm trying to find four different primes  p, q, r, s  such that the 24 concatenations all have smallest prime divisor > 1000.  Even this 'simplification' is interesting!

***

Clark wrote:

I could not find a 4-tuple of distinct primes such that the 4! permutations all give primes.

However, I did find that if one looks at k-tuples of the form [p,p,...,p,q]
then, in all cases I  tried, for each p there is at least one q such that all k permutations 
qpp...p, pqp..p, ...,  pp...pq give primes. And there seem to be many such q for each p
 

and each k. 

So I conjecture that for each p there are infinitely many q such that all k permutations of 
[p,p,...,p,q] give primes.
 

For each of the following k-tuples all k permutations give primes.

[3, 7]
[3, 3, 7]
[3, 3, 3, 787]
[3, 3, 3, 3, 86423]
[3, 3, 3, 3, 3, 1067497]
[7, 19]
[7, 7, 17]
[7, 7, 7, 97]
[7, 7, 7, 7, 61]
[7, 7, 7, 7, 7, 1003907]
[11, 23]
[11, 11, 577]
[11, 11, 11, 163]
[11, 11, 11, 11, 9803]
[11, 11, 11, 11, 11, 13731901]
[13, 19]
[13, 13, 3719]
[13, 13, 13, 22133]
[13, 13, 13, 13, 70237]
[13, 13, 13, 13, 13, 374483]
[17, 83]
[17, 17, 19]
[17, 17, 17, 71]
[17, 17, 17, 17, 28817]
[17, 17, 17, 17, 17, 12765061]

***