Primes in a Line

Question

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?

Answer 1

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

Answer 2

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)