A071983 - OEIS

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.

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

15,9

COMMENTS

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

Values for n <= 75 calculated by an adaptation of the method described by Pettersson. - Victor S. Miller, Apr 21 2026

REFERENCES

V. H. Pettersson, Enumerating Hamiltonian Cycles. Electron. J. Combin. 21 (2014), no. 4, Paper 4.7, 15 pp.

Ronald E. Ruemmler, "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.

LINKS

Victor S. Miller, Table of n, a(n) for n = 15..75 (terms n=15..59 from Zhao Hui Du)

R. Gerbicz, Proof that there is a square chain for all n > 31

Carlos Rivera, Puzzle 311: Sum to a cube, The Prime Puzzles and Problems Connection.

FORMULA

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

EXAMPLE

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.

CROSSREFS

Cf. A071984.

Cf. A090460, A090461.

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