Problems & Puzzles: Puzzles

Puzzle 677 primes in a row such that... II Bernardo Recaman Santos and Carlos Rivera, as a result of a short & swift email interchange, composed the following puzzle: Q1. Find the smallest prime P such that it is possible to arrange all the primes,  2, 3, 5, 7, 11, 13, ..., P, in a row such that the sum of any two adjacent primes is always a perfect square.   Q2. Redo Q1, but forming a circle.

---

Contribution came from W. Edwin Clark & Emmanuel Vantieghem.

***

Edwin wrote:

I like Puzzle 677 since I can formulate it as a graph theory question,
namely, form the graph G[n] with vertices 2,3,...,prime(n) and edges
consisting of prime pairs {p,q} where p + q is a perfect square. 

Q1 asks: Is there an n such that G[n] has a Hamiltonian path.
Q2 asks: Is there an n such that G[n] has a Hamiltonian cycle.

For either of these to be true G[n] would have to be connected.

Unless I have made a mistake somewhere I have shown that G[n] is
not even connected for n up to 7000. My program is still running.

I just wonder if you have a solution?  Perhaps I (or Maple) is mistaken
somewhere.

Since the question simply says "find" is it possible that  Q1  and Q2 are impossible?

***

Emmanuel wrote:

About puzzle 677, Q1.  The smallest prime that can give a solution is  P =238373 = p(21093).

For that value of  n  every prime  p <= 238373  has at least two possible 'neighbours' except  188029  and  210391  that have only one.  This means that, if there exist a solution, it should have the form  188029 - 97127 - . . . - 135353 - 210391.

I tried several possibilities, but I could not get a solution.

I tried in vain to obtain a solution for  P = 409271 = p(34552) in which case there is only one prime (399199) with only one neighbour (and all the others have at least two).

I searched for the smallest  n  such that every prime in the range 2, 3, 5, 7, ..., p(n) has at least two neighbours and I found  n = 38031.  So, if Q2 has a solution it must be one with  n >= 38031.  And it seems an extremely difficult job to find indeed a cycle.

 

I think that there are solutions to both Q1  and  Q2, but they will be extremely difficult to find them.

***