[seqfan] Re: square loop

[Giovanni Resta]

This is already present as https://oeis.org/A071984  (half the values).

Giovanni

On 10/13/19 11:44 AM, Brendan McKay wrote:
> 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/
> 
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>