6
$\begingroup$

Place the first 20 primes (2 to 71) in a line so that the sum or difference (or both) of any two primes that find themselves next to each other is always a perfect square.

For which other values of N besides 20 is it possible to accomplish this using the first N primes?

$\endgroup$
1
  • 1
    $\begingroup$ I have removed the no-computers tag because second part most likely requires some computer aid. $\endgroup$ – Bernardo Recamán Santos May 14 '20 at 18:26
7
$\begingroup$

For other values of N:

Solutions exist for all N up to 32 except 3, 4, 12 and 14. Solutions are likely to exist for greater N.

Number of solutions (including full and partial reversals):

N=2: 2 solutions
N=3: 0 solutions
N=4: 0 solutions
N=5: 8 solutions
N=6: 4 solutions
N=7: 4 solutions
N=8: 8 solutions
N=9: 64 solutions
N=10: 44 solutions
N=11: 44 solutions
N=12: 0 solutions
N=13: 6 solutions
N=14: 0 solutions
N=15: 38 solutions
N=16: 1200 solutions
N=17: 8458 solutions
N=18: 866 solutions
N=19: 706 solutions
N=20: 6266 solutions
N=21: 5880 solutions
N=22: 7850 solutions
N=23: 602516 solutions
N=24: over one million solutions
N=25: over one million solutions
The large increase in the number of solutions occurs when 61 is no longer forced to one end.

First solution found in each case:

N=2: 2 3
N=3: no solution
N=4: no solution
N=5: 2 3 7 11 5
N=6: 5 11 2 7 3 13
N=7: 5 11 2 7 3 13 17
N=8: 5 11 2 7 3 13 17 19
N=9: 2 3 13 17 19 23 7 11 5
N=10: 3 2 23 19 17 13 29 7 11 5
N=11: 3 2 23 19 17 13 29 7 11 5 31
N=12: no solution
N=13: 31 5 11 2 3 7 29 13 17 19 23 41 37
N=14: no solution
N=15: 3 2 11 5 31 47 43 7 29 13 17 19 23 41 37
N=16: 2 3 7 29 13 17 19 23 41 37 53 11 5 31 47 43
N=17: 2 3 7 11 5 31 47 43 59 41 37 53 17 19 23 13 29
N=18: 2 11 5 31 47 17 53 37 41 59 43 7 29 13 23 19 3 61
N=19: 2 7 29 13 17 19 23 41 37 53 11 5 59 43 47 31 67 3 61
N=20: 2 7 11 5 31 47 43 59 41 37 53 17 19 23 13 29 71 67 3 61
N=21: 2 7 11 53 17 19 23 13 29 71 73 37 41 5 59 43 47 31 67 3 61
N=22: 2 79 43 7 11 5 41 59 23 19 17 13 29 71 73 37 53 47 31 67 3 61
N=23: 2 3 7 29 13 17 19 23 41 37 73 71 67 31 47 53 11 5 59 43 79 83 61
N=24: 2 3 7 11 5 31 67 71 29 13 17 19 23 59 41 37 73 89 53 47 43 79 83 61
N=25: 2 3 7 11 5 31 47 97 61 83 67 71 29 13 23 19 17 53 89 73 37 41 59 43 79
N=26: 2 3 7 11 5 31 47 53 89 73 37 41 59 23 19 17 13 29 71 67 83 61 97 101 43 79
N=27: 2 3 7 11 5 31 47 17 19 23 13 29 71 67 103 41 59 43 79 83 61 97 101 37 53 89 73
N=28: 2 3 7 11 5 31 47 53 17 13 29 71 67 103 41 59 23 19 83 61 97 101 37 73 89 107 43 79
N=29: 2 3 7 11 5 31 47 53 17 19 23 13 29 71 67 103 41 59 43 79 83 61 97 101 37 107 89 73 109
N=30: 2 3 7 11 5 31 47 17 19 23 41 59 43 79 83 61 97 101 37 53 89 73 109 113 13 29 71 67 103 107
N=31: 2 3 7 11 5 31 47 53 37 101 97 61 83 79 43 107 89 73 109 113 13 29 71 67 103 41 59 23 19 17 127
N=32: 2 3 7 11 5 31 47 17 19 23 41 59 43 79 83 61 97 101 37 53 89 73 109 113 13 29 71 107 103 67 131 127

$\endgroup$
3
  • $\begingroup$ Great results! I wonder whether requiring that all adjacent terms add up to a square still produces such vast number of solutions. Likewise if the requirement is that difference of adjacent terms is a square. $\endgroup$ – Bernardo Recamán Santos May 15 '20 at 0:03
  • 1
    $\begingroup$ @Bernardo Without allowing both, there are no solutions aside from {2, 3}. Also, I found a solution for N=33. Simply insert 137 between 101 and 37 in the solution shown for N=32. The search space is just too great for my program to get there in reasonable time. $\endgroup$ – Daniel Mathias May 15 '20 at 0:19
  • $\begingroup$ Before you move far onto something else. And of all those many solutions, how many are hamiltonian circuits, i.e.,ends meet? Reason for asking is I am looking for a nice puzzle with a unique solution. $\endgroup$ – Bernardo Recamán Santos May 15 '20 at 1:39
7
$\begingroup$

I think this works:

11 53 37 41 23 19 17 13 29 7 71 67 31 5 59 43 47 2 3 61

And thus the pattern of sums and differences is:

S64, D16, D4, S64, D4, S36, D4, D16, S36, D64, D4, D36, S36, S64, D16, D4, S49, D1, S64

Basically it just

Took a lot of brute forcing on my end — seeing which numbers were able to be connected to which, and noting to the best of my knowledge that 61 had to go on the end and had to be attached to 3. With the exception of working with 2, all squares had to be even squares. And I started by trying to fit as many D4s together as possible and then adjusting/flipping where needed.

The other N for which this occurs, of course, is

N = 2 (ie. 2 3)

$\endgroup$
2
  • 1
    $\begingroup$ Are these the only values of N for which it works? $\endgroup$ – hexomino May 14 '20 at 18:08
  • $\begingroup$ Any other solutions for 20 primes besides the above? $\endgroup$ – Bernardo Recamán Santos May 14 '20 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.