# [seqfan] Re: An interesting problem

Brendan McKay Brendan.McKay at anu.edu.au
Mon Jul 3 04:04:16 CEST 2023

I mean "a hamiltonian path from 1 to n".  B/

On 3/7/2023 12:02 pm, Brendan McKay via SeqFan wrote:
> I have both 2108 and 7288.
>
> I take the graph on [1..n] as defined by Allan, then I add two edges
> 1--0--n and apply a heuristic hamiltonian cycle finder.  Since 0
> has degree 2, the cycle must use the two artificial edges and
> removing them gives a hamiltonian cycle from 1 to n.
>
> I'll see if I can take it to larger sizes.
>
> Brendan.
>
> On 3/7/2023 3:57 am, Allan Wechsler wrote:
>> There is a very similar dynamic displayed in the sequences https:/
>> oeis.org/A128280 and https:/oeis.org/A055265.
>>
>> If you think of the integers [1..n] as vertices of a graph, where two
>> vertices are connected by an edge if the sum of the corresponding
>> integers
>> is prime, then this problem is to find a Hamiltonian path from 1 to n.
>>
>> I suspect that it will be easy to find a solution for 2108 by making
>> a few
>> small edits to the solution for 2107, and similarly for 7288.
>>
>> On Sun, Jul 2, 2023 at 12:47 PM Yifan Xie <xieyifan4013 at 163.com> wrote:
>>
>>> Hi,
>>> I recently discovered a problem:
>>> For an integer n>=2, there exists a sequence {a(n)} consisting of 1,
>>> 2, 3,
>>> ... , n that for all 1<=i<=n, the sum of a(i) and a(i+1) is a prime.
>>> Do all integers n>=2 satisfy the above condition?
>>> The easiest algorithm to find a possible sequence is that all terms are
>>> the largest possible ones. For example, for n=5, the sequence starts
>>> with
>>> 5, since 5+4 and 5+3 are not primes, the next term is 2. Similarly, thw
>>> whole sequence is {5, 2, 3, 4, 1}.
>>> I tested this algorithm for n<=10^4 and found that only 2108 and 7288
>>> failed.
>>> Can anyone help?
>>>
>>>
>>> Cheers,
>>> Yifan Xie (xieyifan4013 at 163.com)
>>>
>>> --
>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>
>> --
>> Seqfan Mailing list - http://list.seqfan.eu/
>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/