[seqfan] Re: An interesting problem

[Max Alekseyev]

A possible generalization is going in 2D. Here are 6x6 and 8x8 squares
filled with numbers 1 to 6^2 and 1 to 8^2 respectively such that the sum of
numbers in any two adjacent cells (sharing a side) is prime. Furthermore,
this property holds cyclically, ie. these squares can be considered on a
torus.

|35|18|13|24|29|02|
|36|01|16|07|30|17|
|25|22|21|10|31|12|
|34|09|20|03|28|19|
|33|08|23|14|15|04|
|26|11|06|05|32|27|

|08|45|22|15|58|09|14|05|
|33|28|61|52|01|10|57|26|
|46|25|36|31|16|07|04|63|
|13|06|11|12|55|34|39|40|
|30|17|56|41|42|37|64|43|
|59|20|27|02|29|60|19|24|
|54|47|32|21|50|53|48|49|
|35|62|51|38|03|44|23|18|

Regards,
Max


On Tue, Jul 4, 2023 at 5:31 AM Brendan McKay via SeqFan <
seqfan at list.seqfan.eu> wrote:

> 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/
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>