Given the first n natural numbers (1,2,3,...,n). We arrange a permutation of these numbers into a circle, such that the sum of any two adjacent numbers is prime. I have proven that there is at least one solution for n=4; n=6; n=8; n=10; I have tried but found no solutions for n=3; n=5; n=7; n=9. My Question: Is it true that there is always a solution for any n = even, but no solution for n = odd??. Here are my two solutions for n=10: (1,2,5,6,7,10,9,8,3,4); and (1,4,3,8,5,2,9,10,7,6). Notice that each of the previous two permutations represent a Hamiltonian cycle (a closed circuit) through the ten vertices (1,2,3,...,10)
Asked
Active
Viewed 79 times
3
-
3For odd $n$ it is impossible to alternate parity, so ... – lulu Jan 18 '18 at 04:58
-
Well, of course..! Thank you very much.. This proves there is no solution for odd (n). One question remains: is there always a solution for even (n) ? – ous Alam Jan 19 '18 at 02:42
1 Answers
0
I have manually determined a solution to the problem for n=60; The Hamiltonian cycle goes through all 60 vertices and is closed. Due to lack of place, I had to fold the cycle a few times. Note: this is one solution of many.
ous Alam
- 31