Problems & Puzzles: Puzzles

Puzzle 683 Rubin's puzzle P.M.A. Hakeem solved the following Frank Rubin's puzzle: "Prove that for every N>1 the integers from 1 to N can be arranged in an order such that the sum of any two consecutive numbers is a prime. For example: 9,8,3,4,1,2,5,6,7,10" I have been able to set an efficient algorithm to construct that kind of solutions, but not properly a proof as the asked by Rubin Q. Can you send the asked proof?

---

Contributions came from W. Edwin Clark and Emmanuel Vantieghem

***

Clark wrote:

As others will have noted this problem is raised in Sloane's http://oeis.org/A051237.
There  it is even conjectured that one can begin with 1 and end with n. Apparently
it is true if one assumes the truth of some old conjectures. It is related to several
other sequences.

I don't have a proof, but instead offer the following variation. This also seems
familiar, but I have not been able to find it by Googling.

 I ask if one can put the numbers from 1 to n in a sequence a[1], a[2],...,a[n] 
such that for i from 1 to n-1: a[i]+a[i+1] is prime and a[n]+a[1] is also prime. 
Alternatively put, Let G[n] be graph with vertices {1,2,...,n} and edges those pairs {i,j} 
such that i+j is prime. The question becomes: is G[n] Hamiltonian? It is easy to
see that this can only happen if  n is even. In this case all the values I have
tried seem to work: Here are Hamiltonian cycles that Maple found for  a few  
small values of n even and n > 2: 

4: [1, 2, 3, 4, 1] 
6: [1, 4, 3, 2, 5, 6, 1] 
8: [1, 2, 3, 8, 5, 6, 7, 4, 1] 
10: [1, 2, 3, 4, 7, 6, 5, 8, 9, 10, 1] 
12: [1, 2, 3, 4, 7, 6, 5, 12, 11, 8, 9, 10, 1] 
14: [1, 2, 3, 4, 7, 6, 13, 10, 9, 14, 5, 8, 11, 12, 1] 
16: [1, 2, 3, 4, 7, 6, 5, 12, 11, 8, 9, 14, 15, 16, 13, 10, 1] 
18: [1, 2, 3, 4, 7, 6, 5, 8, 9, 10, 13, 16, 15, 14, 17, 12, 11, 18, 1] 
20: [1, 2, 3, 4, 7, 6, 5, 8, 9, 10, 13, 16, 15, 14, 17, 20, 11, 12, 19, 18, 1]

Maple verifies the Hamiltonicity of G[n] for even n up to 100.

PS. If PMA Hakeem does have a proof for Puzzle 683 then it should be published. I would like to see it.

***

Emmanuel wrote:

It was not difficult to find a program to construct an asked solution. 

But, to prove that it will work for all  N  seems not possible to me.  Maybe, when Frank Rubin publishes the proof of Hakeem's result, I will have to confess my ignorance.  But in the meantime, I have my doubt.

***