[seqfan] Re: An interesting problem
Brendan McKay
Brendan.McKay at anu.edu.au
Tue Jul 4 11:30:29 CEST 2023
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/
More information about the SeqFan
mailing list