A070897 -id:A070897 - 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

A073364 Number of permutations p of (1,2,3,...,n) such that k+p(k) is prime for 1<=k<=n.

Original entry on oeis.org

1, 1, 1, 4, 1, 9, 4, 36, 36, 676, 400, 9216, 3600, 44100, 36100, 1223236, 583696, 14130081, 5461569, 158180929, 96275344, 5486661184, 2454013444, 179677645456, 108938283364, 5446753133584, 4551557699844, 280114147765321, 125264064932449, 9967796169000201

Offset: 1

Benoit Cloitre, Aug 23 2002

nonn

a(n)=permanent(m), where the n X n matrix m is defined by m(i,j) = 1 or 0, depending on whether i+j is prime or composite respectively. - T. D. Noe, Oct 16 2007

Jinyuan Wang, Table of n, a(n) for n = 1..50
Paul Bradley, Prime Number Sums, arXiv:1809.01012 [math.GR], 2018.
Zhi-Wei Sun, On permutations of {1, ..., n} and related topics, arXiv:1811.10503 [math.CO], 2018.

Cf. A000341, A069191, A070897, A134293, A321610, A321611.

a073364 n = length $ filter (all isprime)
                     $ map (zipWith (+) [1..n]) (permutations [1..n])
   where isprime n = a010051 n == 1  -- cf. A010051
-- Reinhard Zumkeller, Mar 19 2011

am[n_] := Permanent[Array[Boole[PrimeQ[2 #1 + 2 #2 - 1]]&, {n, n}]];
ap[n_] := Permanent[Array[Boole[PrimeQ[2 #1 + 2 #2 + 1]]&, {n, n}]];
a[n_] := If[n == 1, 1, If[EvenQ[n], am[n/2]^2, ap[(n-1)/2]^2]];
Array[a, 28] (* Jean-François Alcover, Nov 03 2018 *)

a(n)=sum(k=1,n!,n==sum(i=1,n,isprime(i+component(numtoperm(n,k),i))))

a(n)={matpermanent(matrix(n,n,i,j,isprime(i + j)))} \\ Andrew Howroyd, Nov 03 2018

a(2n) = A000341(n)^2 and a(2n+1) = A134293(n)^2. - T. D. Noe, Oct 16 2007

a(10) from Mohammed Bouayoun (bouyao(AT)wanadoo.fr), Mar 14 2004
a(11) from Rick L. Shepherd, Mar 17 2004
a(12)-a(17) from John W. Layman, Jul 21 2004
More terms from T. D. Noe, Oct 16 2007

A071058 Number of ways of pairing odd numbers in the range 1 to n with even numbers in the range n+1 to 2n such that each pair sums to a prime.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 4, 6, 10, 7, 21, 11, 40, 53, 215, 181, 773, 939, 3260, 4432, 23431, 15811, 80724, 67891, 429108, 434963, 2748239, 2718150, 21654009, 21580655, 107459138, 92370364, 638616984, 564878656, 5055810584, 4545704064, 35787453599, 36878092180

Offset: 1

T. D. Noe, May 25 2002

			a(5)=2 because there are two ways: 1+10, 3+8, 6+5 and 1+6, 3+10, 5+8.

Martin Fuller, Table of n, a(n) for n = 1..70

The product of this sequence and A071059 gives A070897.

a[n_] := a[n] = Module[{s1, s2, s3, s4, i, ik, km},
s1 = Select[Flatten[Outer[List, Range[1, n, 2], Range[2n, n+1, -2]], 1],
   PrimeQ[Total[#]]&];
s2 = SplitBy[s1, First];
km = Length[s2];
ik = Table[{i[k], 1, Length[s2[[k]]]}, {k, 1, km}];
s3 = Table[Table[s2[[k, i[k]]], {k, 1, km}], Evaluate[Sequence @@ ik]] //
   Flatten[#, km-1]&;
s4 = Select[s3, Length[Union[Flatten[#]]] == 2km&];
s4 // Length];
Table[Print[n, " ", a[n]]; a[n], {n, 1, 20}] (* Jean-François Alcover, Aug 10 2022 *)

a(n)=matpermanent(matrix((n+1)\2,(n+1)\2,i,j,isprime((i+j-2)*2+n+3-(n%2)))); \\ Martin Fuller, Sep 21 2023

a(2n) = A071059(2n).

More terms from David W. Wilson, May 27 2002

a(31)-a(36) from Donovan Johnson, Aug 12 2010

A071059 Number of ways of pairing even numbers in the range 1 to n with odd numbers in the range n+1 to 2n such that each pair sums to a prime.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 2, 6, 4, 7, 6, 11, 11, 53, 53, 181, 171, 939, 925, 4432, 4545, 15811, 15583, 67891, 68193, 434963, 388975, 2718150, 3113343, 21580655, 18425145, 92370364, 94887088, 564878656, 572364768, 4545704064, 4092294083, 36878092180, 36363930614

Offset: 1

T. D. Noe, May 25 2002

			a(6)=2 because there are two ways: 2+9, 4+7, 6+11 and 2+11, 4+9, 6+7.

Martin Fuller, Table of n, a(n) for n = 1..70

The product of this sequence and A071058 gives A070897.

f:= proc(n) local m;
  m:= floor(n/2);
 LinearAlgebra:-Permanent(Matrix(m,m,
    (i,j) -> `if`(isprime((i+j-2)*2 + n + 3 + (n mod 2)),1,0)))
end proc:
f(1):= 1:
map(f, [$1..40]); # Robert Israel, Sep 21 2023

a[n_] := a[n] = If[n == 1, 1, Module[{s1, s2, s3, s4, i, ik, km},
s1 = Select[Flatten[Outer[List, Range[2, n, 2], Range[2n-1, n+1, -2]], 1], PrimeQ[Total[#]]&];
s2 = SplitBy[s1, First];
km = Length[s2];
ik = Table[{i[k], 1, Length[s2[[k]]]}, {k, 1, km}];
s3 = Table[Table[s2[[k, i[k]]], {k, 1, km}], Evaluate[Sequence @@ ik]] // Flatten[#, km - 1]&;
s4 = Select[s3, Length[Union[Flatten[#]]] == 2km&];
s4 // Length]];
Table[Print[n, " ", a[n]]; a[n], {n, 1, 20}] (* Jean-François Alcover, Aug 10 2022 *)

a(n)=matpermanent(matrix(n\2,n\2,i,j,isprime((i+j-2)*2+n+3+(n%2)))); \\ Martin Fuller, Sep 21 2023

a(2n) = A071058(2n).

More terms from David W. Wilson, May 27 2002

a(31)-a(37) from Donovan Johnson, Aug 12 2010

A077762 Number of ways of pairing the squares of the numbers 1 to n with the squares of the numbers n+1 to 2n such that each pair sums to a prime. Because an odd square must always be added to an even square to obtain a prime, this sequence is the product of A077763 and A077764.

Original entry on oeis.org

1, 1, 0, 1, 2, 0, 1, 1, 4, 8, 0, 8, 42, 28, 140, 616, 836, 180, 1416, 2542, 10960, 96048, 242204, 367587, 923949, 1145430, 2622420, 19081728, 245846500, 2934255428, 6725485476, 7722272142, 26106311490, 114470819132, 331909473776, 330258090272, 4585951400436, 37021666628450

Offset: 1

T. D. Noe, Nov 15 2002

nonn

Apparently, for n>11, there seems always to be a pairing possible. Note that all primes have the 4k+1 form. By the 4k+1 theorem, such a prime has a unique representation as the sum of two squares.

			a(5) = 2 because there are two ways: (1,4,9,16,25) + (36,49,100,81,64) = (37,53,109,97,89) and (1,4,9,16,25) + (100,49,64,81,36) = (101,53,73,97,61).

Bert Dobbelaere, Table of n, a(n) for n = 1..50
L. E. Greenfield and S. J. Greenfield, Some Problems of Combinatorial Number Theory Related to Bertrand's Postulate, J. Integer Sequences, 1998, #98.1.2.

Cf. A000348, A070897, A077763, A077764.

lst1*lst2 (* which are defined in A077763 and A077764 *)

a(n) = permanent(m), where the n X n matrix m is defined by m(i,j) = 1 or 0, depending on whether i^2 + (j+n)^2 is prime or composite, respectively. - T. D. Noe, Feb 10 2007

More terms from Bert Dobbelaere, Sep 08 2019

A071414 Number of times 4n+r and 2n+r are both prime, with 0 < r < 2n.

Original entry on oeis.org

1, 1, 2, 1, 2, 2, 2, 1, 3, 1, 2, 4, 2, 2, 6, 2, 2, 7, 3, 4, 5, 3, 2, 6, 3, 3, 5, 4, 3, 8, 2, 5, 9, 5, 5, 6, 4, 3, 7, 5, 4, 10, 3, 5, 11, 6, 5, 9, 5, 7, 10, 5, 5, 5, 5, 6, 11, 3, 6, 15, 3, 6, 12, 4, 6, 11, 8, 4, 11, 9, 4, 10, 6, 6, 16, 6, 7, 16, 7, 8, 11, 6, 6, 15, 9, 8, 12, 8, 8, 13, 9, 5, 14, 7, 12

Offset: 1

T. D. Noe, May 29 2002

Related to the even terms of A070897. If a(n)>0 then there is a simple pairing whose sums involve just 1 (if r=1) or 2 primes. For the case n=2, which corresponds to A070897(4), the numbers 1,2,3,4 can be paired with 5,6,7,8 so that the sums are 11 and 7 (the primes obtained when r=3).

			a(3)=2 because 12+r and 6+r are both prime for only 2 values of r: 1 and 5.

For[lst={}; n=1, n<=100, n++, cnt=0; For[k=1, k<2n, k=k+2, If[PrimeQ[4n+k]&&PrimeQ[2n+k], cnt++ ]]; AppendTo[lst, cnt]]; lst

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

A073364 Number of permutations p of (1,2,3,...,n) such that k+p(k) is prime for 1<=k<=n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Formula

Extensions

A071058 Number of ways of pairing odd numbers in the range 1 to n with even numbers in the range n+1 to 2n such that each pair sums to a prime.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A071059 Number of ways of pairing even numbers in the range 1 to n with odd numbers in the range n+1 to 2n such that each pair sums to a prime.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A077762 Number of ways of pairing the squares of the numbers 1 to n with the squares of the numbers n+1 to 2n such that each pair sums to a prime. Because an odd square must always be added to an even square to obtain a prime, this sequence is the product of A077763 and A077764.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A071414 Number of times 4n+r and 2n+r are both prime, with 0 < r < 2n.

Views

Author

Keywords

Comments

Examples

Programs

Mathematica