A103839 -id:A103839 - cp's OEIS frontend

A051252 Number of essentially different ways of arranging numbers 1 through 2n around a circle so that sum of each pair of adjacent numbers is prime.

1, 1, 1, 2, 48, 512, 1440, 40512, 385072, 3154650, 106906168, 3197817022, 82924866213, 4025168862425, 127854811616691

Offset: 1

Jud McCranie reports that he was able to find a solution for each n <= 225 (2n <= 450) in just a few seconds. - Jul 05 2002
Is there a proof that this can always be done?
The Mathematica program for this sequence uses backtracking to find all solutions for a given n. To verify that at least one solution exists for a given n, the backtracking function be made to stop when the first solution is found. Solutions have been found for n <= 48. - T. D. Noe, Jun 19 2002
This sequence is from the prime circle problem. There is no known proof that a(n) > 0 for all n. However, for many n (see A072618 and A072676), we can prove that a(n) > 0. Also, the sequence A072616 seems to imply that there are always solutions in which the odd (or even) numbers are in order around the circle. - T. D. Noe, Jul 01 2002
Prime circles can apparently be generated for any n using the Mathematica programs given in A072676 and A072184. - T. D. Noe, Jul 08 2002
The following seems to always produce a solution: Work around the circle starting with 1 but after that always choosing the largest remaining number that fits. For example, if n = 4 this gives 1, 6, 7, 4, 3, 8, 5, 2. See A088643 for a sequence on a related idea. - Paul Boddington, Oct 30 2007
See A228917 for a similar conjecture on twin primes. - Zhi-Wei Sun, Sep 08 2013
See A242527 for a similar problem on the set of numbers {0 through (n-1)}. - Stanislav Sykora, May 30 2014
James Tilley and Stan Wagon report that all terms up to n = 10^6 are nonzero. Charles R Greathouse IV, Feb 05 2016

			One arrangement for 2n=6 is 1,4,3,2,5,6 and this is essentially unique, so a(3)=1.

R. K. Guy, Unsolved Problems in Number Theory, second edition, Springer, 1994. See section C1.

S. Sykora, On Neighbor-Property Cycles, Stan's Library, Volume V, 2014.
Eric Weisstein's World of Mathematics, Prime Circle.

Cf. A000341, A070897, A072616, A072617, A072618, A072676, A072184, A103839, A227050, A228917, A242527, A242528.

$RecursionLimit=500; try[lev_] := Module[{t, j}, If[lev>2n, (*then make sure the sum of the first and last is prime*) If[PrimeQ[soln[[1]]+soln[[2n]]]&&soln[[2]]<=soln[[2n]], (*Print[soln]; *) cnt++ ], (*else append another number to the soln list*) t=soln[[lev-1]]; For[j=1, j<=Length[s[[t]]], j++, If[ !MemberQ[soln, s[[t]][[j]]], soln[[lev]]=s[[t]][[j]]; try[lev+1]; soln[[lev]]=0]]]]; For[lst={}; n=1, n<=7, n++, s=Table[{}, {2n}]; For[i=1, i<=2n, i++, For[j=1, j<=2n, j++, If[i!=j&&PrimeQ[i+j], AppendTo[s[[i]], j]]]]; soln=Table[0, {2n}]; soln[[1]]=1; cnt=0; try[2]; AppendTo[lst, cnt]]; lst (* T. D. Noe *)

a(14)-a(15) from Max Alekseyev, Sep 19 2013

A051239 Number of ways to arrange integers 1 through n so that the sum of each adjacent pair is prime, not counting reversals.

Original entry on oeis.org

1, 1, 1, 4, 2, 8, 12, 30, 70, 664, 1072, 8768, 11648, 37108, 95772, 1059816, 2047488, 12111712, 22802028, 120779959, 337801784, 4361743860, 11425028900, 142573286216, 429917269469, 4138239848098, 16171519847028, 214845911686065

Offset: 1

Jud McCranie

Similar to A036440, but not requiring 1 to be first and n to be last.

			a(5)=2 since 1,4,3,2,5 and 3,4,1,2,5 have the property that the sum of each adjacent pair is prime.

Cf. A036440, A051237.

For n>1, a(n) = A103839(n)/2.

More terms from Max Alekseyev, Jan 04 2008

a(25)-a(28) from Giovanni Resta, Apr 01 2014

A064821 Number of ways of writing the numbers 1 .. n in a sequence so that the sum of any two adjacent numbers is a prime; reversing the sequence does not count as different.

Original entry on oeis.org

0, 1, 1, 4, 2, 8, 12, 30, 70, 664, 1072, 8768, 11648, 37108, 95772, 1059816, 2047488, 12111712, 22802028, 120779959, 337801784, 4361743860, 11425028900, 142573286216, 429917269469, 4138239848098, 16171519847028, 214845911686065

Offset: 1

N. J. A. Sloane, Oct 23 2001

If the sequence is d_1 d_2 ... d_n then the n-1 sums d_i + d_{i+1} are required to be primes.
I conjecture a(n) > 0 for all n.
Variant of A051239 with respect to a(1). - R. J. Mathar, Oct 02 2008

			For n = 4 there are 4 sequences: 1234, 1432, 3214, 3412.

Cf. A064821, A103839.

More terms from Jud McCranie, Oct 24 2001
a(22)-a(24) from Donovan Johnson, Aug 27 2010
a(25)-a(28) from Giovanni Resta, Jun 05 2020

A367704 Number of permutations of [n] where each pair of adjacent elements differs by a prime.

Original entry on oeis.org

1, 1, 0, 0, 2, 10, 32, 96, 448, 1968, 7320, 21516, 118938, 662742, 4556360, 26950038, 155388246, 756995286, 5730299976, 38809702892, 337875402936, 2593543573702, 20560179519176, 138677553274430, 1337517942958934, 11083936316867572, 94288296012340842

Offset: 0

Bob Andriesse, Nov 27 2023

nonn

This sequence was inspired by A103839 and the PARI program is a modified version of the one in A103839.
The number of Hamiltonian paths in a graph of which the nodes represent the numbers (1,2,3,...,n) and the edges connect each pair of nodes that differ by a prime.
A076220, A103839 and this sequence are closely related, but their combined graph in the link shows an interesting difference, notably between this sequence and the two others. - Bob Andriesse, Dec 03 2023

			a(4) = 2: 2413, 3142.
a(5) = 10: 13524, 14253, 24135, 25314, 31425, 35241, 41352, 42531, 52413, 53142.

Bob Andriesse, Combined graph of this sequence, A076220 and A103839 for a(4) to a(25)

Cf. A076220, A103839.

okperm(perm) = {for (k=1, #perm -1, if (! isprime(abs(perm[k]-perm[k+1])),  return (0));  ); return (1); }
a(n) = {nbok = 0; for (j=1, n!, perm = numtoperm(n, j); if (okperm(perm), nbok++); ); return (nbok); }

a(14)-a(22) from Alois P. Heinz, Nov 27 2023

a(23)-a(26) from Martin Ehrenstein, Dec 03 2023

A368958 Number of permutations of [n] where each pair of adjacent elements is coprime and does not differ by a prime.

Original entry on oeis.org

1, 1, 2, 2, 2, 10, 4, 28, 6, 42, 40, 348, 42, 1060, 226, 998, 886, 21660, 690, 57696, 4344, 26660, 22404, 1091902, 12142, 1770008

Offset: 0

Bob Andriesse, Jan 10 2024

The number of Hamiltonian paths in a graph of which the nodes represent the numbers (1,2,3,...,n) and the edges connect each pair of nodes that are coprime and do not differ by a prime.

			a(5) = 10: 15432, 21543, 23451, 32154, 34512, 43215, 45123, 51234, 54321, 12345.
a(6) = 4: 432156, 651234, 654321, 123456.

Bob Andriesse, Combined graph of this sequence, A076220, A103839 and A367704 for a(4) to a(25).

Cf. A076220, A103839, A367704.

a[n_] := a[n] = Module[{b = 0, ps}, ps = Permutations[Range[n]]; Do[If[Module[{d}, AllTrue[Partition[pe, 2, 1], (d = Abs[#[[2]] - #[[1]]]; ! PrimeQ[d] && CoprimeQ[#[[1]], #[[2]]]) &]], b++], {pe, ps}]; b];
Table[a[n], {n, 0, 8}] (* Robert P. P. McKone, Jan 12 2024 *)

okperm(perm) = {for(k=1, #perm-1, if((isprime(abs(perm[k]-perm[k+1]))), return(0)); if(!(gcd(perm[k], perm[k+1])==1), return(0));); return(1);}
a(n) = {my(nbok = 0); for (j=1, n!, perm = numtoperm(n,j); if(okperm(perm), nbok++);); return(nbok); }

from math import gcd
from sympy import isprime
def A368958(n):
    if n<=1 : return 1
    clist = tuple({j for j in range(1,n+1) if j!=i and gcd(i,j)==1 and not isprime(abs(i-j))} for i in range(1,n+1))
    def f(p,q):
        if (l:=len(p))==n-1: yield len(clist[q]-p)
        for d in clist[q]-p if l else set(range(1,n+1))-p:
            yield from f(p|{d},d-1)
    return sum(f(set(),0)) # Chai Wah Wu, Jan 19 2024

a(14)-a(25) from Alois P. Heinz, Jan 11 2024

A369330 Number of permutations of (1, 2, ..., n) in which any two adjacent elements differ by a power of 2.

Original entry on oeis.org

1, 1, 2, 6, 12, 48, 140, 338, 926, 4390, 15990, 52766, 187688, 557768, 1772354, 5865806, 18707354, 102862912, 456146172, 1833942698, 7914142056, 30247599368, 120022505534, 492976337746, 1992746442918, 7203060422116, 27454886930170, 106007544478780, 398728610528654

Offset: 0

Pontus von Brömssen, Jan 20 2024

nonn

The number of (directed) Hamiltonian paths in the graph with vertex set {1, 2, ..., n} and edges between vertices that differ by a power of 2.

Cf. A076220, A103839, A242519, A367704, A368958.

a(22) from Alois P. Heinz, Jan 20 2024
a(23) from Andrew Howroyd, Jan 20 2024
a(24)-a(28) from Martin Ehrenstein, Mar 02 2024

cp's OEIS Frontend

A051252 Number of essentially different ways of arranging numbers 1 through 2n around a circle so that sum of each pair of adjacent numbers is prime.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Extensions

A051239 Number of ways to arrange integers 1 through n so that the sum of each adjacent pair is prime, not counting reversals.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A064821 Number of ways of writing the numbers 1 .. n in a sequence so that the sum of any two adjacent numbers is a prime; reversing the sequence does not count as different.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A367704 Number of permutations of [n] where each pair of adjacent elements differs by a prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A368958 Number of permutations of [n] where each pair of adjacent elements is coprime and does not differ by a prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions

A369330 Number of permutations of (1, 2, ..., n) in which any two adjacent elements differ by a power of 2.

Views

Author

Keywords

Comments

Crossrefs

Extensions