The task in the problems
Adjacent Square Sum is:
Arrange the numbers 1 to 15 inclusively in a straight line in such a way that any two adjacent numbers add up to a perfect square.
Suppose we are instead asked to arrange 1 to n instead.
(1) Show that this is not possible if 1<n<15.
(2) Show that there are solutions for n=16 and n=17.
(3) Find the next value of n>17 for which there is a solution.
This program
clc, clearvars
global src s n
for n=2:32
src=[1:n];
s=[];
addon(1);
end
function addon(wh)
global src s n
for i=1:n
if src(i)>0
if wh==1
good=true;
else
sq=s(wh-1)+i;
sr=round(sqrt(sq));
if sr*sr==sq
good=true;
else
good=false;
end
end
if good
s(wh)=i;
src(i)=0;
if wh==n && s(1)<s(end)
fprintf('%2d ',n)
fprintf('%2d ',s)
fprintf('\n')
else
addon(wh+1)
end
src(i)=i;
end
end
end
end
uses recursion (calls itself) to build all the valid lists by trying each successive valid number that hasn't been used yet, for the next position. Each one it finds that works it then goes through the same procedure until all n have a value. It then backtracks to find the next valid value in the position before, etc.
It finds that the first n that works is 15 and shows the solutions for 15, 16, 17, 23, 25, ... 32. After skipping 24, it resumes with n = 25, with 10 non-trivial solutions, and the number of solutions seems to balloon after that. OEIS A090461 assures us that every n >= 25 is in the sequence of values of n, and A090460 shows us the ballooning, as the number of essentially different sequences is, starting with the one for 15: 1, 1, 1, 0, 0, 0, 0, 0, 3, 0, 10, 12, 35, 52, 19, 20, 349, 361, 637, 3678, 15237, 11875, 13306, 10964, 27223, 37054, 201408, 510152, 1995949, 4867214, 11255174, 35705858, 63029611, 129860749, 258247089, 190294696, 686125836, 2195910738, ... .
n sequence
15 8 1 15 10 6 3 13 12 4 5 11 14 2 7 9
16 8 1 15 10 6 3 13 12 4 5 11 14 2 7 9 16
17 16 9 7 2 14 11 5 4 12 13 3 6 10 15 1 8 17
23 2 23 13 12 4 21 15 10 6 19 17 8 1 3 22 14 11 5 20 16 9 7 18
23 9 16 20 5 11 14 22 3 1 8 17 19 6 10 15 21 4 12 13 23 2 7 18
23 18 7 9 16 20 5 11 14 2 23 13 12 4 21 15 10 6 19 17 8 1 3 22
25 2 23 13 12 24 25 11 14 22 3 1 8 17 19 6 10 15 21 4 5 20 16 9 7 18
25 3 22 14 2 23 13 12 4 21 15 10 6 19 17 8 1 24 25 11 5 20 16 9 7 18
25 4 21 15 10 6 19 17 8 1 3 22 14 2 23 13 12 24 25 11 5 20 16 9 7 18
25 8 17 19 6 10 15 21 4 12 13 23 2 14 22 3 1 24 25 11 5 20 16 9 7 18
25 9 16 20 5 4 21 15 10 6 19 17 8 1 3 22 14 11 25 24 12 13 23 2 7 18
25 10 15 21 4 12 13 23 2 14 22 3 6 19 17 8 1 24 25 11 5 20 16 9 7 18
25 11 25 24 12 13 23 2 14 22 3 1 8 17 19 6 10 15 21 4 5 20 16 9 7 18
25 13 23 2 14 22 3 1 8 17 19 6 10 15 21 4 12 24 25 11 5 20 16 9 7 18
25 18 7 9 16 20 5 11 25 24 1 8 17 19 6 10 15 21 4 12 13 3 22 14 2 23
25 18 7 9 16 20 5 11 25 24 12 4 21 15 10 6 19 17 8 1 3 13 23 2 14 22
Then the numbers of solutions start to balloon:
26 2 14 22 3 13 23 26 10 6 19 17 8 1 15 21 4 12 24 25 11 5 20 16 9 7 18
26 4 21 15 1 8 17 19 6 10 26 23 2 14 22 3 13 12 24 25 11 5 20 16 9 7 18
26 8 17 19 6 10 26 23 2 14 22 3 13 12 4 21 15 1 24 25 11 5 20 16 9 7 18
26 9 16 20 5 11 25 24 12 4 21 15 1 8 17 19 6 10 26 23 13 3 22 14 2 7 18
26 11 25 24 12 13 3 22 14 2 23 26 10 6 19 17 8 1 15 21 4 5 20 16 9 7 18
26 13 3 22 14 2 23 26 10 6 19 17 8 1 15 21 4 12 24 25 11 5 20 16 9 7 18
26 13 12 4 21 15 10 26 23 2 14 22 3 6 19 17 8 1 24 25 11 5 20 16 9 7 18
26 15 21 4 12 13 3 22 14 2 23 26 10 6 19 17 8 1 24 25 11 5 20 16 9 7 18
26 18 7 9 16 20 5 4 21 15 1 8 17 19 6 10 26 23 2 14 11 25 24 12 13 3 22
26 18 7 9 16 20 5 11 25 24 1 8 17 19 6 3 13 12 4 21 15 10 26 23 2 14 22
26 18 7 9 16 20 5 11 25 24 1 8 17 19 6 3 22 14 2 23 13 12 4 21 15 10 26
26 18 7 9 16 20 5 11 25 24 1 8 17 19 6 10 15 21 4 12 13 3 22 14 2 23 26
27 1 8 17 19 6 3 13 12 24 25 11 14 22 27 9 16 20 5 4 21 15 10 26 23 2 7 18
27 1 8 17 19 6 3 13 23 26 10 15 21 4 12 24 25 11 5 20 16 9 27 22 14 2 7 18
27 1 8 17 19 6 3 22 27 9 16 20 5 4 21 15 10 26 23 13 12 24 25 11 14 2 7 18
27 3 13 12 24 25 11 14 22 27 9 16 20 5 4 21 15 1 8 17 19 6 10 26 23 2 7 18
27 3 13 23 26 10 6 19 17 8 1 15 21 4 12 24 25 11 5 20 16 9 27 22 14 2 7 18
27 3 22 27 9 16 20 5 4 21 15 1 8 17 19 6 10 26 23 13 12 24 25 11 14 2 7 18
27 5 20 16 9 27 22 3 13 23 26 10 6 19 17 8 1 15 21 4 12 24 25 11 14 2 7 18
27 5 20 16 9 27 22 14 11 25 24 1 8 17 19 6 3 13 12 4 21 15 10 26 23 2 7 18
27 6 19 17 8 1 3 13 12 24 25 11 14 22 27 9 16 20 5 4 21 15 10 26 23 2 7 18
27 6 19 17 8 1 3 13 23 26 10 15 21 4 12 24 25 11 5 20 16 9 27 22 14 2 7 18
27 6 19 17 8 1 3 22 27 9 16 20 5 4 21 15 10 26 23 13 12 24 25 11 14 2 7 18
27 8 17 19 6 10 26 23 13 3 1 15 21 4 12 24 25 11 5 20 16 9 27 22 14 2 7 18
27 10 26 23 13 3 6 19 17 8 1 15 21 4 12 24 25 11 5 20 16 9 27 22 14 2 7 18
27 12 4 21 15 10 26 23 13 3 6 19 17 8 1 24 25 11 5 20 16 9 27 22 14 2 7 18
27 12 13 3 6 19 17 8 1 24 25 11 14 22 27 9 16 20 5 4 21 15 10 26 23 2 7 18
27 12 13 23 26 10 15 21 4 5 20 16 9 27 22 3 6 19 17 8 1 24 25 11 14 2 7 18
27 14 11 25 24 12 13 3 22 27 9 16 20 5 4 21 15 1 8 17 19 6 10 26 23 2 7 18
27 14 22 27 9 16 20 5 11 25 24 1 8 17 19 6 3 13 12 4 21 15 10 26 23 2 7 18
27 15 21 4 5 20 16 9 27 22 3 1 8 17 19 6 10 26 23 13 12 24 25 11 14 2 7 18
27 15 21 4 5 20 16 9 27 22 14 11 25 24 12 13 3 1 8 17 19 6 10 26 23 2 7 18
27 16 20 5 4 21 15 1 8 17 19 6 10 26 23 2 14 11 25 24 12 13 3 22 27 9 7 18
27 16 20 5 11 25 24 1 8 17 19 6 3 13 12 4 21 15 10 26 23 2 14 22 27 9 7 18
27 18 7 2 14 11 5 20 16 9 27 22 3 13 23 26 10 6 19 17 8 1 15 21 4 12 24 25
27 18 7 2 14 11 25 24 1 8 17 19 6 3 22 27 9 16 20 5 4 12 13 23 26 10 15 21
27 18 7 2 14 11 25 24 12 4 5 20 16 9 27 22 3 13 23 26 10 6 19 17 8 1 15 21
27 18 7 2 14 11 25 24 12 13 3 22 27 9 16 20 5 4 21 15 1 8 17 19 6 10 26 23
27 18 7 2 14 11 25 24 12 13 23 26 10 6 3 22 27 9 16 20 5 4 21 15 1 8 17 19
27 18 7 2 14 11 25 24 12 13 23 26 10 15 1 8 17 19 6 3 22 27 9 16 20 5 4 21
27 18 7 2 14 22 3 13 23 26 10 6 19 17 8 1 15 21 4 12 24 25 11 5 20 16 9 27
27 18 7 2 14 22 27 9 16 20 5 11 25 24 1 8 17 19 6 3 13 12 4 21 15 10 26 23
27 18 7 2 14 22 27 9 16 20 5 11 25 24 12 4 21 15 10 6 19 17 8 1 3 13 23 26
27 18 7 2 23 26 10 6 3 13 12 24 25 11 14 22 27 9 16 20 5 4 21 15 1 8 17 19
27 18 7 2 23 26 10 15 1 8 17 19 6 3 13 12 24 25 11 14 22 27 9 16 20 5 4 21
27 18 7 9 16 20 5 4 21 15 1 8 17 19 6 10 26 23 2 14 11 25 24 12 13 3 22 27
27 18 7 9 16 20 5 11 25 24 1 8 17 19 6 3 13 12 4 21 15 10 26 23 2 14 22 27
28 1 15 10 26 23 13 3 6 19 17 8 28 21 4 12 24 25 11 5 20 16 9 27 22 14 2 7 18
28 1 15 21 28 8 17 19 6 10 26 23 13 3 22 27 9 16 20 5 4 12 24 25 11 14 2 7 18
28 1 24 25 11 14 22 27 9 16 20 5 4 12 13 3 6 19 17 8 28 21 15 10 26 23 2 7 18
28 3 6 19 17 8 28 21 4 12 13 23 26 10 15 1 24 25 11 5 20 16 9 27 22 14 2 7 18
28 3 13 12 4 5 20 16 9 27 22 14 11 25 24 1 15 21 28 8 17 19 6 10 26 23 2 7 18
28 3 22 27 9 16 20 5 4 12 13 23 26 10 6 19 17 8 28 21 15 1 24 25 11 14 2 7 18
28 4 5 20 16 9 27 22 3 1 15 21 28 8 17 19 6 10 26 23 13 12 24 25 11 14 2 7 18
28 4 5 20 16 9 27 22 14 11 25 24 12 13 3 1 15 21 28 8 17 19 6 10 26 23 2 7 18
28 4 12 13 23 26 10 15 21 28 8 17 19 6 3 1 24 25 11 5 20 16 9 27 22 14 2 7 18
28 4 21 28 8 17 19 6 3 1 15 10 26 23 13 12 24 25 11 5 20 16 9 27 22 14 2 7 18
28 5 20 16 9 27 22 3 6 19 17 8 28 21 4 12 13 23 26 10 15 1 24 25 11 14 2 7 18
28 6 19 17 8 28 21 4 5 20 16 9 27 22 3 1 15 10 26 23 13 12 24 25 11 14 2 7 18
28 6 19 17 8 28 21 4 5 20 16 9 27 22 14 11 25 24 12 13 3 1 15 10 26 23 2 7 18
28 6 19 17 8 28 21 15 10 26 23 13 12 4 5 20 16 9 27 22 3 1 24 25 11 14 2 7 18
28 10 26 23 13 12 4 5 20 16 9 27 22 3 6 19 17 8 28 21 15 1 24 25 11 14 2 7 18
28 11 25 24 1 3 6 19 17 8 28 21 15 10 26 23 13 12 4 5 20 16 9 27 22 14 2 7 18
28 11 25 24 12 13 23 26 10 15 1 3 6 19 17 8 28 21 4 5 20 16 9 27 22 14 2 7 18
28 12 4 5 20 16 9 27 22 3 13 23 26 10 6 19 17 8 28 21 15 1 24 25 11 14 2 7 18
28 12 4 21 28 8 17 19 6 3 13 23 26 10 15 1 24 25 11 5 20 16 9 27 22 14 2 7 18
28 12 13 3 6 19 17 8 28 21 4 5 20 16 9 27 22 14 11 25 24 1 15 10 26 23 2 7 18
28 13 12 4 5 20 16 9 27 22 14 11 25 24 1 3 6 19 17 8 28 21 15 10 26 23 2 7 18
28 13 12 24 25 11 14 22 27 9 16 20 5 4 21 28 8 17 19 6 3 1 15 10 26 23 2 7 18
28 13 23 26 10 6 19 17 8 28 21 15 1 3 22 27 9 16 20 5 4 12 24 25 11 14 2 7 18
28 13 23 26 10 15 1 3 6 19 17 8 28 21 4 12 24 25 11 5 20 16 9 27 22 14 2 7 18
28 15 1 3 13 12 24 25 11 14 22 27 9 16 20 5 4 21 28 8 17 19 6 10 26 23 2 7 18
28 15 1 3 13 23 26 10 6 19 17 8 28 21 4 12 24 25 11 5 20 16 9 27 22 14 2 7 18
28 15 1 3 22 27 9 16 20 5 4 21 28 8 17 19 6 10 26 23 13 12 24 25 11 14 2 7 18
28 15 10 26 23 13 12 4 21 28 8 17 19 6 3 1 24 25 11 5 20 16 9 27 22 14 2 7 18
28 15 21 28 8 17 19 6 10 26 23 13 12 4 5 20 16 9 27 22 3 1 24 25 11 14 2 7 18
28 17 19 6 3 13 12 4 5 20 16 9 27 22 14 11 25 24 1 8 28 21 15 10 26 23 2 7 18
28 17 19 6 3 13 12 24 25 11 14 22 27 9 16 20 5 4 21 28 8 1 15 10 26 23 2 7 18
28 17 19 6 3 13 23 26 10 15 1 8 28 21 4 12 24 25 11 5 20 16 9 27 22 14 2 7 18
28 17 19 6 3 22 27 9 16 20 5 4 12 13 23 26 10 15 21 28 8 1 24 25 11 14 2 7 18
28 17 19 6 3 22 27 9 16 20 5 4 21 28 8 1 15 10 26 23 13 12 24 25 11 14 2 7 18
28 18 7 2 14 11 5 20 16 9 27 22 3 6 19 17 8 28 21 4 12 13 23 26 10 15 1 24 25
28 18 7 2 14 11 25 24 1 3 6 19 17 8 28 21 15 10 26 23 13 12 4 5 20 16 9 27 22
28 18 7 2 14 11 25 24 1 8 17 19 6 3 22 27 9 16 20 5 4 12 13 23 26 10 15 21 28
28 18 7 2 14 11 25 24 1 15 10 26 23 13 12 4 5 20 16 9 27 22 3 6 19 17 8 28 21
28 18 7 2 14 11 25 24 12 4 5 20 16 9 27 22 3 13 23 26 10 6 19 17 8 1 15 21 28
28 18 7 2 14 11 25 24 12 13 23 26 10 15 1 3 6 19 17 8 28 21 4 5 20 16 9 27 22
28 18 7 2 14 11 25 24 12 13 23 26 10 15 1 8 17 19 6 3 22 27 9 16 20 5 4 21 28
28 18 7 2 14 22 3 6 19 17 8 28 21 4 12 13 23 26 10 15 1 24 25 11 5 20 16 9 27
28 18 7 2 14 22 27 9 16 20 5 11 25 24 12 4 21 15 1 3 13 23 26 10 6 19 17 8 28
28 18 7 2 14 22 27 9 16 20 5 11 25 24 12 4 21 28 8 17 19 6 10 15 1 3 13 23 26
28 18 7 2 23 13 12 4 5 20 16 9 27 22 14 11 25 24 1 3 6 19 17 8 28 21 15 10 26
28 18 7 2 23 13 12 24 25 11 14 22 27 9 16 20 5 4 21 28 8 17 19 6 3 1 15 10 26
28 18 7 2 23 26 10 6 3 13 12 4 5 20 16 9 27 22 14 11 25 24 1 15 21 28 8 17 19
28 18 7 2 23 26 10 6 19 17 8 28 21 15 1 3 13 12 4 5 20 16 9 27 22 14 11 25 24
28 18 7 2 23 26 10 6 19 17 8 28 21 15 1 24 25 11 14 22 3 13 12 4 5 20 16 9 27
28 18 7 2 23 26 10 15 1 8 17 19 6 3 13 12 24 25 11 14 22 27 9 16 20 5 4 21 28
28 18 7 2 23 26 10 15 1 24 12 13 3 6 19 17 8 28 21 4 5 20 16 9 27 22 14 11 25
28 18 7 2 23 26 10 15 1 24 25 11 14 22 27 9 16 20 5 4 12 13 3 6 19 17 8 28 21
29 1 24 25 11 5 4 12 13 3 6 19 17 8 28 21 15 10 26 23 2 14 22 27 9 16 20 29 7 18
29 3 13 12 4 5 11 25 24 1 15 21 28 8 17 19 6 10 26 23 2 14 22 27 9 16 20 29 7 18
29 4 5 11 25 24 12 13 3 1 15 21 28 8 17 19 6 10 26 23 2 14 22 27 9 16 20 29 7 18
29 6 19 17 8 28 21 4 5 11 25 24 12 13 3 1 15 10 26 23 2 14 22 27 9 16 20 29 7 18
29 12 13 3 6 19 17 8 28 21 4 5 11 25 24 1 15 10 26 23 2 14 22 27 9 16 20 29 7 18
29 13 12 4 5 11 25 24 1 3 6 19 17 8 28 21 15 10 26 23 2 14 22 27 9 16 20 29 7 18
29 13 12 24 25 11 5 4 21 28 8 17 19 6 3 1 15 10 26 23 2 14 22 27 9 16 20 29 7 18
29 14 2 23 26 10 6 19 17 8 28 21 15 1 24 25 11 5 4 12 13 3 22 27 9 16 20 29 7 18
29 15 1 3 13 12 24 25 11 5 4 21 28 8 17 19 6 10 26 23 2 14 22 27 9 16 20 29 7 18
29 17 19 6 3 13 12 4 5 11 25 24 1 8 28 21 15 10 26 23 2 14 22 27 9 16 20 29 7 18
29 17 19 6 3 13 12 24 25 11 5 4 21 28 8 1 15 10 26 23 2 14 22 27 9 16 20 29 7 18
29 18 7 29 20 16 9 27 22 3 13 12 4 5 11 14 2 23 26 10 6 19 17 8 28 21 15 1 24 25
29 18 7 29 20 16 9 27 22 14 2 23 13 12 4 5 11 25 24 1 3 6 19 17 8 28 21 15 10 26
29 18 7 29 20 16 9 27 22 14 2 23 13 12 24 25 11 5 4 21 28 8 17 19 6 3 1 15 10 26
29 18 7 29 20 16 9 27 22 14 2 23 26 10 6 3 13 12 4 5 11 25 24 1 15 21 28 8 17 19
29 18 7 29 20 16 9 27 22 14 2 23 26 10 6 19 17 8 28 21 15 1 3 13 12 4 5 11 25 24
29 18 7 29 20 16 9 27 22 14 2 23 26 10 15 1 8 17 19 6 3 13 12 24 25 11 5 4 21 28
29 18 7 29 20 16 9 27 22 14 2 23 26 10 15 1 24 12 13 3 6 19 17 8 28 21 4 5 11 25
29 18 7 29 20 16 9 27 22 14 2 23 26 10 15 1 24 25 11 5 4 12 13 3 6 19 17 8 28 21
30 1 24 25 11 5 4 12 13 3 6 30 19 17 8 28 21 15 10 26 23 2 14 22 27 9 16 20 29 7 18
30 3 13 12 4 5 11 25 24 1 15 21 28 8 17 19 30 6 10 26 23 2 14 22 27 9 16 20 29 7 18
30 4 5 11 25 24 12 13 3 1 15 21 28 8 17 19 30 6 10 26 23 2 14 22 27 9 16 20 29 7 18
30 6 30 19 17 8 28 21 4 5 11 25 24 12 13 3 1 15 10 26 23 2 14 22 27 9 16 20 29 7 18
30 12 13 3 6 30 19 17 8 28 21 4 5 11 25 24 1 15 10 26 23 2 14 22 27 9 16 20 29 7 18
30 13 12 4 5 11 25 24 1 3 6 30 19 17 8 28 21 15 10 26 23 2 14 22 27 9 16 20 29 7 18
30 13 12 24 25 11 5 4 21 28 8 17 19 30 6 3 1 15 10 26 23 2 14 22 27 9 16 20 29 7 18
30 14 2 23 26 10 6 30 19 17 8 28 21 15 1 24 25 11 5 4 12 13 3 22 27 9 16 20 29 7 18
30 15 1 3 13 12 24 25 11 5 4 21 28 8 17 19 30 6 10 26 23 2 14 22 27 9 16 20 29 7 18
30 17 19 30 6 3 13 12 4 5 11 25 24 1 8 28 21 15 10 26 23 2 14 22 27 9 16 20 29 7 18
30 17 19 30 6 3 13 12 24 25 11 5 4 21 28 8 1 15 10 26 23 2 14 22 27 9 16 20 29 7 18
30 18 7 29 20 16 9 27 22 3 13 12 4 5 11 14 2 23 26 10 6 30 19 17 8 28 21 15 1 24 25
30 18 7 29 20 16 9 27 22 14 2 23 13 12 4 5 11 25 24 1 3 6 30 19 17 8 28 21 15 10 26
30 18 7 29 20 16 9 27 22 14 2 23 13 12 24 25 11 5 4 21 28 8 17 19 30 6 3 1 15 10 26
30 18 7 29 20 16 9 27 22 14 2 23 26 10 6 3 13 12 4 5 11 25 24 1 15 21 28 8 17 19 30
30 18 7 29 20 16 9 27 22 14 2 23 26 10 6 30 19 17 8 28 21 15 1 3 13 12 4 5 11 25 24
30 18 7 29 20 16 9 27 22 14 2 23 26 10 15 1 3 13 12 24 25 11 5 4 21 28 8 17 19 6 30
30 18 7 29 20 16 9 27 22 14 2 23 26 10 15 1 8 17 19 30 6 3 13 12 24 25 11 5 4 21 28
30 18 7 29 20 16 9 27 22 14 2 23 26 10 15 1 24 12 13 3 6 30 19 17 8 28 21 4 5 11 25
30 18 7 29 20 16 9 27 22 14 2 23 26 10 15 1 24 25 11 5 4 12 13 3 6 30 19 17 8 28 21
Then 349 solutions are shown for n=31 and 361 for n=32.
The reverse of each solution is of course also a solution, but only the solutions where the first number is lower than the last number are shown, for brevity's sake.
So part (3) has the answer 23.
|
|
Posted by Charlie
on 2021-07-15 12:07:01 |
computer solution (spoiler)
