[seqfan] Re: An interesting problem
Brendan McKay
Brendan.McKay at anu.edu.au
Mon Jul 3 04:02:32 CEST 2023
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/
More information about the SeqFan
mailing list