[seqfan] Re: square loop
Robert Gerbicz
robert.gerbicz at gmail.com
Sun Oct 13 09:53:09 CEST 2019
Not remembered, but the sequence is already in http://oeis.org/A090461 .
Counting the number of sequences is much harder, basically you need to find
the number of Hamiltonian path/cycle in a graph, which is hard. Probably
while the count is "small" you can directly count it with an easy
backtracking method.
<hv at crypt.org> ezt írta (időpont: 2019. okt. 12., Szo, 22:01):
> After a recent puzzle in New Scientist.
>
> The integers 1 .. 32 can be arranged in a loop such that each consecutive
> pair sums to a square:
> 32 4 21 28 8 1 15 19 26 23 2 14 22 27 9 16
> 20 29 7 18 31 5 11 25 24 12 13 3 6 30 19 17
>
> My trial code to test for this finds n = 32 is the smallest for which this
> is possible, and finds solutions for each of 32 to 44; however the code
> is becoming unusably slow as n increases.
>
> My suspicion is that it is possible precisely for n >= 32, can someone
> prove this, or at least show an upper bound for an n for which the loop
> is not possible?
>
> If we require only a sequence rather than a loop, the first solution
> occurs with n = 15:
> 8 1 15 10 6 3 13 12 4 5 11 14 2 7 9
> .. and it appears there are solutions for n in { 15, 16, 17, 23 } and
> all n >= 25 (tested up to n = 47).
>
> I would guess that the two examples might be of interest in the OEIS, but
> the sets of values of n for which loops or sequences are (or are not)
> possible would not be suitable as OEIS sequences.
>
> Hugo
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>
More information about the SeqFan
mailing list