A071984 -id:A071984 - cp's OEIS frontend

A090460 Number of essentially different permutations of the numbers 1 to n such that the sum of adjacent numbers is a square.

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, 5114909395, 9141343219, 19769529758, 44678128099, 63885400119

Offset: 15

T. D. Noe, Dec 01 2003

For n > 31, some solutions are circular; that is, the first and last numbers also sum to a square. Note that A071983 counts each circular solution n times. This sequence counts each circular solution only once. The Mathematica program uses backtracking to find all solutions, which can be printed by removing the comment symbols.

			See A071983.

Zhao Hui Du, Table of n, a(n) for n = 15..59

Cf. A071983, A071984 (number of circular solutions), A090461 (n for which there is a solution).
Cf. A078107 (n for which there is no solution).
Cf. A272259 (row n gives the smallest circular solution, for each n >= 32).

SquareQ[n_] := IntegerQ[Sqrt[n]]; try[lev_] := Module[{t, j, circular}, If[lev>n, circular=SquareQ[soln[[1]]+soln[[n]]]; If[(!circular&&soln[[1]]

a(n) = A071983(n) - (n-1)*A071984(n).

a(43)-a(45) from Donovan Johnson, Sep 14 2010
a(46)-a(47) from Jud McCranie, Aug 18 2018
a(48) from Jud McCranie, Sep 17 2018
a(49)-a(52) from Bert Dobbelaere, Dec 30 2018
a(47) corrected by Bert Dobbelaere, Jan 12 2019
a(53)-a(54) from Martin Ehrenstein, May 22 2023
a(55)-a(57) from Zhao Hui Du, Apr 26 2024

A071983 Square chains: the number of permutations (reversals not counted as different) of the numbers 1 to n such that the sum of any two consecutive numbers is a square.

Original entry on oeis.org

1, 1, 1, 0, 0, 0, 0, 0, 3, 0, 10, 12, 35, 52, 19, 20, 349, 392, 669, 4041, 17175, 12960, 14026, 11889, 29123, 39550, 219968, 553694, 2178103, 5301127, 12220138, 38838893, 68361609, 140571720, 280217025, 204853870, 738704986, 2368147377, 5511090791, 9802605881, 21164463050, 47746712739, 68092497615, 123092214818

Offset: 15

William Rex Marshall, Jun 16 2002

For n > 31, this sequence counts each circular solution (in which the first and last numbers also sum to a square) n times. Sequence A090460 counts the circular solutions only once, giving the number of essentially different solutions.

The existence of cubic chains in answered affirmatively in Puzzle 311. - T. D. Noe, Jun 16 2005

			There is only one possible square chain of minimum length, which is: (8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9) so a(15)=1.

Ruemmler, Ronald E., "Square Loops," Journal of Recreational Mathematics 14:2 (1981-82), page 141; Solution by Chris Crandell and Lance Gay, JRM 15:2 (1982-83), page 155.

Zhao Hui Du, Table of n, a(n) for n = 15..59
Carlos Rivera, Puzzle 311: Sum to a cube, The Prime Puzzles and Problems Connection.

Cf. A071984.
Cf. A090460, A090461.
Cf. A078107 (n for which there is no solution).

a(n) = A090460(n) + (n-1)*A071984(n). - Martin Ehrenstein, May 16 2023

a(43)-a(45) from Donovan Johnson, Sep 14 2010
a(46)-a(47) from Jud McCranie, Aug 18 2018
a(48) from Jud McCranie, Sep 17 2018
a(49)-a(52) from Bert Dobbelaere, Dec 30 2018
a(53)-a(54) from Martin Ehrenstein, May 16 2023
a(55)-a(56) from Zhao Hui Du, Apr 25 2024
a(57)-a(58) from Zhao Hui Du, Apr 26 2024

A090461 Numbers k for which there exists a permutation of the numbers 1 to k such that the sum of adjacent numbers is a square.

Original entry on oeis.org

15, 16, 17, 23, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89

Offset: 1

T. D. Noe, Dec 01 2003

nonn

Conjecture: sequence includes all integers k > 24. See A090460 for the number of essentially different solutions.
It is now known that 25..299 are in the sequence, see the Numberphile 2 link. - Jud McCranie, Jan 11 2018
Every 25 <= k <= 2^20 is in the sequence and (71*25^m-1)/2 is also in the sequence for every m, hence this sequence is infinite, see Mersenneforum link for the proof; we give Hamiltonian cycle for these k values if k >= 32. - Robert Gerbicz, Jan 17 2017
The conjecture has been proved: every k >= 25 is in the sequence, moreover for k >= 32 there is a Hamiltonian cycle; see Mersenneforum topic for a code and deterministic algorithm to find a sequence. - Robert Gerbicz, Jan 21 2018

			See A071983.

Brady Haran and Matt Parker, The Square-Sum Problem, Numberphile video (2018)
Brady Haran, Matt Parker, and Charlie Turner, The Square-Sum Problem (extra footage) - Numberphile 2 (2018)
HexagonVideos, Numberphile's Square-Sum Problem was solved!, YouTube video, 2023.
Mersenneforum, The Square-Sum problem

Cf. A071983, A071984 (number of circular solutions), A090460.

Cf. A078107 (k for which there is no solution).

F:= proc(n)
uses GraphTheory;
local edg, G;
edg:= select(t -> issqr(t[1]+t[2]),{seq(seq({i,j},i=1..j-1),j=1..n)}) union {seq({i,n+1},i=1..n)};
G:= Graph(n+1,edg);
IsHamiltonian(G)
end proc:
select(F, [$1..50]); # Robert Israel, Jun 05 2015

Join[{15, 16, 17, 23}, Range[25, 100]] (* Paolo Xausa, May 28 2024 *)

a(31)-a(69) from Donovan Johnson, Sep 14 2010

A112663 Smallest circular sequence of period 32 such that any two adjacent numbers sum to a square number.

Original entry on oeis.org

1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5, 31, 18, 7, 29, 20, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15, 1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5, 31, 18, 7, 29, 20, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15, 1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5, 31, 18, 7, 29, 20, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15

Offset: 0

Federico Ramondino, Dec 29 2005

nonn

The terms of this sequence are given in A071984. An algorithm for computing circular chains of squares is given in A090460. - T. D. Noe, Dec 30 2005

			1+8=9
8+28=36
28+21=49
...
26+10=36
10+15=25
15+1=16

Cf. A000217, A000290.

Cf. A272259 (has terms a(0..31) in row 32).

apply( {A112663(n)=my(r=1);foreach(digits(403079653644429064719159, 6)[1..n%32],s,r=(s+2)^2-r); r}, [0..77]) \\ M. F. Hasler, Jun 23 2025

a(n) = A272259(32, (n-1) mod 32) for all n, where "mod" is the (nonnegative) remainder operator. - M. F. Hasler, Jun 23 2025

A272259 Irregular triangle read by rows: Row n >= 32 gives the smallest square loop, i.e., lexicographically earliest circular permutation of length n such that any two adjacent numbers sum to a perfect square.

Original entry on oeis.org

1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5, 31, 18, 7, 29, 20, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15, 1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5, 20, 29, 7, 18, 31, 33, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15, 1, 3, 13, 12, 4, 32, 17, 8, 28, 21, 15, 34, 30, 19, 6, 10, 26, 23, 2, 14, 22, 27, 9, 16, 33, 31, 18, 7, 29, 20, 5, 11, 25, 24

Offset: 32

Martin Renner, Apr 23 2016

T(n) gives the smallest Hamiltonian cycle in the corresponding undirected unweighted graph with n vertices and edges satisfying the square sum condition, so this is also a solution to the Traveling Salesman Problem.
There are no circular solutions for n < 32.
T(32) = A112663(k-1), 1 <= k <= 32.
Row n has length n, and we start with row n = 32.

			Table starts with
n = 32: 1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5, 31, 18, 7, 29, 20, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15.
n = 33: 1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5, 20, 29, 7, 18, 31, 33, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15.

Martin Renner, Table of n, a(n) for n = 32..663

Cf. A071984 (number of solutions), A112663 (row 32 repeated).

with(GraphTheory):
n:=32; # Vertices from 1 to n
E:={}: # Edges
for a from 1 to n do
  for b from a+1 to n do
    if type(sqrt(a+b),integer) then E:={op(E),{a,b}}: fi:
  od:
od:
G:=Graph(E);
T||n:=TravelingSalesman(G)[2,1..n];

A272259(n)={my(N=[[c^2-a | c<-[sqrtint(a)+1..sqrtint(n+a)], c^2 != 2*a] | a<-[1..n]], used=Vec(1,n), path=Vec(1,n)); for(step=2, n, my(t = [k | k<-N[path[step-1]], k > path[step] && !used[k] ]);
  if (t && (stepM. F. Hasler, Jun 24 2025

A078107 Numbers k such that it is not possible to arrange the numbers from 1 to k in a chain with adjacent links summing to a square.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 18, 19, 20, 21, 22, 24

Offset: 1

R. K. Guy, Dec 06 2002

It seems certain, on account of the valences of the underlying graph, that necklaces exist for all larger k, but this may not yet have been proved.
The problem originated (for k = 15) with Bernardo Recamán Santos of Colombia. The problem for necklaces is due to Joe Kisenwether.
Ed Pegg Jr and W. Edwin Clark have found necklaces (and hence chains) for k = 32 onwards up to 50 and for several larger numbers.
It has been proven that there are no more terms. See A090461 for details. - Paolo Xausa, May 29 2024

			E.g., for 15, 16 or 17, use (16-)9-7-2-14-11-5-4-12-13-3-6-10-15-1-8(-17).

Cf. A071983, A071984, A090460, A090461.

A108658 Number of the essentially different permutations of the numbers 0 to n such that the sum of adjacent numbers is a square.

Original entry on oeis.org

1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 4, 4, 0, 0, 4, 5, 2, 8, 7, 47, 72, 135, 283, 158, 164, 1948, 1467, 2998, 20561, 66700, 130236, 153058, 181635, 239386, 343189, 1600832, 5001577, 16859525, 45119463, 66785667, 218923884, 393626778, 665307164, 3111228585, 2156371427

Offset: 0

Zak Seidov, T. D. Noe & Max Alekseyev, Jun 16 2005

Square chains (reversals not counted and circles counted once). There is no solution for n=2-13,18-19 (note offset=0). For n=0 and n=1 we have trivial square circles (which are also known as square loops). Square circles seem to appear for all n>30, see A108661. Cf. A090460 for 1-to-n case.

			n=14: one solution
  {8,1,0,9,7,2,14,11,5,4,12,13,3,6,10};
n=15: three solutions
  {0,9,7,2,14,11,5,4,12,13,3,6,10,15,1,8},
  {5,11,14,2,7,9,0,4,12,13,3,6,10,15,1,8},
  {8,1,0,9,7,2,14,11,5,4,12,13,3,6,10,15};
n=16: four solutions
  {0,16,9,7,2,14,11,5,4,12,13,3,6,10,15,1,8},
  {5,11,14,2,7,9,16,0,4,12,13,3,6,10,15,1,8},
  {8,1,0,16,9,7,2,14,11,5,4,12,13,3,6,10,15},
  {8,1,15,10,6,3,13,12,4,5,11,14,2,7,9,0,16}.

Cf. A071984, A090460, A108659, A108660, A108661.

SquareQ[n_]:=IntegerQ[Sqrt[n]]; try[lev_]:=Module[{t, j, circular}, If[lev>n+1, circular=SquareQ[soln[[1]]+soln[[n+1]]]; If[(!circular&&soln[[1]]

a(42)-a(50) from Bert Dobbelaere, Dec 30 2018

A064817 Maximal number of squares among the n-1 numbers p_i + p_{i+1}, 1 <= i <= n-1, where (p_1, ..., p_n) is any permutation of (1, ..., n).

Original entry on oeis.org

0, 0, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 16, 17, 18, 19, 20, 22, 22, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68

Offset: 1

N. J. A. Sloane, Oct 23 2001

a(n) < n by definition, but if we counted the sum p_n + p_1, we could get a(n) = n for 32 <= n <= 49 (see A071984). - David Wasserman, Aug 20 2002
Can be formulated as a traveling salesman problem on a complete graph with node set {0, 1, ..., n} and edge cost -1 if i + j is a square, 0 otherwise. - Rob Pratt, Nov 07 2012
a(n) = n - 1 for 25 <= n <= 500, computed by solving corresponding TSP. - Rob Pratt, Nov 07 2012

			n=8: take 2,7,8,1,3,6,4,5 to get 5 squares: 2+7, 8+1, 1+3, 3+6, 4+5; a(8) = 5.
(1,8,9,7,2,14,11,5,4,12,13,3,6,10) gives 12 squares and no permutation of (1..14) gives more, so a(14)=12.

Bernardo Recamán Santos, Challenging Brainteasers, Sterling, NY, 2000, page 71, shows a(15) = 14 using 9,7,2,14,11,5,4,12,13,3,6,10,15,1,8.

Cf. A035106, A064764, A064796, A064797, A071983, A071984.

a[n_] := Which[n == 1, 0, n > 30, n - 1, True, tour = FindShortestTour[Range[n], DistanceFunction -> Function[{i, j}, If[IntegerQ[Sqrt[i + j]], -1, 0]]] // Last; cnt = 0; Do[If[IntegerQ[Sqrt[tour[[i]] + tour[[i + 1]]]], cnt++], {i, 1, n}]; cnt]; Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 1, 69}] (* Jean-François Alcover, Nov 04 2016 *)

More terms from Vladeta Jovovic, Oct 23 2001
More terms from John W. Layman and Charles K. Layman (cklayman(AT)juno.com), Nov 07 2001
More terms from David Wasserman, Aug 20 2002
More terms from Rob Pratt, Nov 07 2012

A108661 Square loops: the number of circular permutations (reversals not counted as different) of the numbers 0 to n such that the sum of any two consecutive numbers is a square.

Original entry on oeis.org

6, 3, 3, 72, 226, 358, 309, 391, 547, 813, 3562, 10741, 36633, 94547, 120424, 393670, 676579, 1088429, 5531195, 3294327, 8335128, 27820643, 75288569, 111875702, 264015370, 465407197, 687532936, 1109951444, 3256360099

Offset: 31

Zak Seidov, T. D. Noe & Max Alekseyev Jun 16 2005

			There is no solution for n=0,...,30, (note offset=31). For n=0,1 we have the trivial square circles {0} and {0,1}, which are not included in the sequence.
There are only six possible square loops of the minimum length (n=31 case):
{1,0,4,5,31,18,7,29,20,16,9,27,22,3,13,12,24,25,11,14,2,23,26,10,6,30,19,17,8,28,21,15},
{1,0,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,31,5,11,25,24},
{1,0,4,21,28,8,17,19,30,6,3,13,12,24,25,11,5,31,18,7,29,20,16,9,27,22,14,2,23,26,10,15},
{1,15,10,26,23,2,14,22,27,9,16,20,29,7,18,31,5,11,25,0,4,21,28,8,17,19,30,6,3,13,12,24},
{1,15,21,28,8,17,19,30,6,10,26,23,2,14,11,5,31,18,7,29,20,16,9,27,22,3,13,12,4,0,25,24},
{1,15,21,28,8,17,19,30,6,10,26,23,2,14,11,25,0,4,5,31,18,7,29,20,16,9,27,22,3,13,12,24}.
In the n=32,33 (resp.) cases, there are three square loop solutions:
{1,0,4,32,17,19,30,6,3,13,12,24,25,11,5,31,18,7,29,20,16,9,27,22,14,2,23,26,10,15,21,28,8},
{1,8,28,21,4,32,17,19,30,6,3,13,12,24,25,11,5,31,18,7,29,20,16,0,9,27,22,14,2,23,26,10,15},
{1,8,28,21,15,10,26,23,2,14,22,27,9,16,20,29,7,18,31,5,11,25,0,4,32,17,19,30,6,3,13,12,24},
and
{1,0,4,32,17,19,30,6,3,13,12,24,25,11,5,20,29,7,18,31,33,16,9,27,22,14,2,23,26,10,15,21,28,8},
{1,8,28,21,4,32,17,19,30,6,3,13,12,24,25,11,5,20,29,7,18,31,33,16,0,9,27,22,14,2,23,26,10,15},
{1,8,28,21,15,10,26,23,2,14,22,27,9,16,33,31,18,7,29,20,5,11,25,0,4,32,17,19,30,6,3,13,12,24}
(resp.).

Cf. A108658 = square chains.

Cf. A071984, A090460, A108658, A108659, A108660.

a(42)-a(47) from Donovan Johnson, Sep 14 2010
a(48)-a(52) from Fausto A. C. Cariboni, Sep 21 2018
a(53)-a(59) from Bert Dobbelaere, Dec 29 2018

A115418 Define a k-th-power loop of length m>1 to be a circular permutation of the numbers 1 to m such that the sum of any two consecutive numbers is a perfect k-th-power; these numbers are the lengths of the possible k-th-power loops.

Original entry on oeis.org

2, 32, 473, 9641

Offset: 1

Roberto Tauraso, Jan 22 2006

nonn

Cf. A071984, A112663.

cp's OEIS Frontend

A090460 Number of essentially different permutations of the numbers 1 to n such that the sum of adjacent numbers is a square.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A071983 Square chains: the number of permutations (reversals not counted as different) of the numbers 1 to n such that the sum of any two consecutive numbers is a square.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A090461 Numbers k for which there exists a permutation of the numbers 1 to k such that the sum of adjacent numbers is a square.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A112663 Smallest circular sequence of period 32 such that any two adjacent numbers sum to a square number.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A272259 Irregular triangle read by rows: Row n >= 32 gives the smallest square loop, i.e., lexicographically earliest circular permutation of length n such that any two adjacent numbers sum to a perfect square.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

A078107 Numbers k such that it is not possible to arrange the numbers from 1 to k in a chain with adjacent links summing to a square.

Views

Author

Keywords

Comments

Examples

Crossrefs

A108658 Number of the essentially different permutations of the numbers 0 to n such that the sum of adjacent numbers is a square.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A064817 Maximal number of squares among the n-1 numbers p_i + p_{i+1}, 1 <= i <= n-1, where (p_1, ..., p_n) is any permutation of (1, ..., n).

Views

Author

Keywords

Comments

Examples