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?

Improve this question
$\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, 2020 at 18:26

2 Answers 2

Reset to default
6
$\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

Improve this answer
$\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, 2020 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, 2020 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, 2020 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)

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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