[seqfan] Re: square loop

[Brendan McKay]

Counts of hamiltonian cycles from n=32 to n=47:

2,2,22,114,62,40,50,100,128,928,2124,8674,20182,43862,139246,231826

Someone needs to check.

Brendan.

On 13/10/19 6:53 pm, Robert Gerbicz wrote:
> 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/
>>
> --
> Seqfan Mailing list - http://list.seqfan.eu/