[seqfan] Re: An interesting problem

[Brendan McKay]

Some highly relevant material about this problem is here:
https://mathoverflow.net/questions/241569

Note that the question asks for a path, while most of the answers
concern a cycle (where the first and last elements must also add
to a prime).

This doesn't matter. For a cycle note that n must be even; in that case
just cut any edge if you only want a path.  If n is odd, add n+1 to the
mix, find a cycle, then delete n+1 to get a path.

If I understand it, Johan Wästlund's answer on that page proves it
up to 10^13.

A051252 and A228917 are mentioned and relevant.

A version which I haven't seen anywhere is whether you can find a
path with specified endpoints.  I'll spell it out:  For n >= 2,
and distinct a,b in {1..n}, is there a permutation of 1..n that starts
with a, ends with b, and consecutive elements sum to a prime?
There are trivial parity constraints (exercise for the reader):
    If n is odd, a and b are both odd.
    If n is even, a and b have opposite parity.

For tiny n there are some cases that can't be done.
These are impossible:  n=5, {a,b}={1,3} and n=6, {a,b}={1,2}.

For 7 <= n <= 750, all cases work if they meet the parity constraints.
It seems reasonable to conjecture that this continues forever.

Here are solutions for n=7 and all {a,b}:

  1 4 7 6 5 2 3
  1 2 3 4 7 6 5
  1 4 3 2 5 6 7
  3 2 1 4 7 6 5
  3 4 1 2 5 6 7
  5 2 3 4 1 6 7

I checked that  {a,b}={1,n} works for 2 <= n <= 33,000.
I also checked that {a,b}={1,2} works for even 8 <= n <= 20,000 .

Brendan.

On 2/7/2023 10:44 pm, Yifan Xie 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/