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

A071810 Number of subsets of the first n primes whose sum is a prime.

Original entry on oeis.org

1, 3, 5, 7, 12, 20, 35, 65, 122, 237, 448, 846, 1629, 3157, 6159, 12052, 23484, 45731, 89394, 175742, 346214, 681850, 1344838, 2657654, 5253640, 10374991, 20471626, 40401929, 79871387, 158182899, 313402605, 620776215, 1228390086, 2430853648

Offset: 1

Robert G. Wilson v, Jun 06 2002

a(n+1) < 2*a(n) fails for n = 1, 332 and other larger values of n. - Don Reble, Sep 07 2006

Here is one way to compute this sequence. Compute f_n(x) = Product_{k=1..n} 1+x^prime(k) = f_{n-1}(x) * (1+x^prime(n)). Then sum the coefficients of x^p in f_n(x) for p prime. You only need to look at primes <= the sum of the first n primes. - Franklin T. Adams-Watters, Sep 07 2006

			a(4) = 7 because, besides the original 4 primes, the other 3 subsets, {2,3}, {2,5} & {2,3,5,7} also sum to a prime.

Alois P. Heinz, Table of n, a(n) for n = 1..1000 (first 100 terms from T. D. Noe)

Cf. A000341, A108018.

Cf. A010051, A000040.

import Data.List (subsequences)
a071810 = sum . map a010051' . map sum .
          tail . subsequences . flip take a000040_list
-- Reinhard Zumkeller, Dec 16 2013

Do[ Print[ Count[ PrimeQ[Plus @@@ Subsets[ Table[ Prime[i], {i, 1, n}]]], True]], {n, 1, 22}]
Table[Count[Total/@Subsets[Prime[Range[n]]],?PrimeQ],{n,20}] (* _Harvey P. Dale, Mar 03 2020 *)

More terms from Don Reble, Sep 07 2006

Edited by N. J. A. Sloane, Sep 08 2006

A070897 Number of ways of pairing numbers 1 to n with numbers n+1 to 2n such that each pair sums to a prime.

Original entry on oeis.org

1, 1, 1, 1, 2, 4, 8, 36, 40, 49, 126, 121, 440, 2809, 11395, 32761, 132183, 881721, 3015500, 19642624, 106493895, 249987721, 1257922092, 4609187881, 29262161844, 189192811369, 1068996265025, 7388339422500, 67416357342087, 465724670229025, 1979950199225010

Offset: 1

T. D. Noe, May 23 2002

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

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

Cf. A000341, A071058, A071059, A073364.

import Data.List (permutations)
a070897 n = length $ filter (all ((== 1) . a010051))
                     $ map (zipWith (+) [1..n]) (permutations [n+1..2*n])
-- Reinhard Zumkeller, Mar 19 2011, Apr 16 2011 (fixed)

<n ]& /@Select[ Range[ n+2, 3*n ], PrimeQ ], 1 ]; po=Position[ it, # ]&/@Range[ n ]; permoid=(Extract[ it, # ]-n)& /@(po /. {i_Integer, j_}->{i, 1} ); Length@Backtrack[ permoid, UnsameQ@@#&, Length[ # ]===n&, All ] ]; Noe/@Range[ 2, 16 ] (* from Wouter Meeussen *)
a[n_] := Permanent[Table[If[PrimeQ[i+j+n], 1, 0], {i, n}, {j, n}]]; Table[ an = a[n]; Print["a(", n, ") = ", an]; an, {n, 1, 16}] (* Jean-François Alcover, Feb 26 2016 *)

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

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+n is prime or composite, respectively. - T. D. Noe, Feb 10 2007

a(n) = A071058(n) * A071059(n).

More terms from Don Reble, May 26 2002

A009692 Number of partitions of {1, 2, ..., 2n} into pairs whose differences are primes.

Original entry on oeis.org

1, 0, 1, 3, 10, 40, 153, 921, 5144, 30717, 230748, 1766056, 14052445, 116580521, 897876519, 7657321097, 75743979608, 788733735080, 7569825650083, 75242386295617, 831978453306391, 9444103049405370, 120064355466770831, 1579842230380587833

Offset: 0

David W. Wilson

			a(3) = 3: {{1,6}, {2,4}, {3,5}}, {{1,4}, {2,5}, {3,6}}, {{1,3}, {2,5}, {4,6}}. - _Alois P. Heinz_, Nov 15 2016

Cf. A000341.

b:= proc(s) option remember; `if`(s={}, 1, (j-> add(`if`(i b({$1..2*n}):
seq(a(n), n=0..12);  # Alois P. Heinz, Nov 15 2016

b[s_] := b[s] = If[s == {}, 1, Function[j, Sum[If[i < j && PrimeQ[j - i], b[s ~Complement~ {i, j}], 0], {i, s}]][Max[s]]];
a[n_] := b[Range[2n]];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 18}] (* Jean-François Alcover, Mar 01 2021, after Alois P. Heinz *)

a(0), a(14)-a(18) from Alois P. Heinz, Nov 15 2016

a(19)-a(23) from Bert Dobbelaere, Feb 20 2020

A134293 Number of ways to pair up {2..2n+1} so the sum of each pair is prime.

Original entry on oeis.org

1, 1, 2, 6, 20, 60, 190, 764, 2337, 9812, 49538, 330058, 2133438, 11192143, 73469550, 462692414, 3692965270, 32635321384, 290171883863, 2572828730372, 22299380503953, 195129375058656, 1544534855847233, 13144353749969945, 128883813733449772, 1365629506139662111

Offset: 1

T. D. Noe, Oct 17 2007

nonn

This sequence complements A000341, which is also related to A073364.

			a(3)=2 because for the set {2..7} there are two ways: {{2,3},{4,7},{5,6}} and {{2,5},{3,4},{6,7}}.

Vaclav Kotesovec, Table of n, a(n) for n = 1..35

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

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

a(n) = permanent(m), where the n X n matrix m is defined by m(i,j) = 1 or 0, depending on whether 2i+2j+1 is prime or composite, respectively.

a(21)-a(26) from Andrew Howroyd, Nov 03 2018

A342136 Number of partitions of [2n] into pairs whose sums and differences are primes.

Original entry on oeis.org

1, 0, 0, 0, 1, 2, 6, 10, 22, 101, 66, 504, 2088, 3572, 14398, 49984, 108030, 191228, 1087758, 5005440, 14081453, 97492234, 160186634, 939652634, 3926077642, 4273706733, 41832174879, 214185383046, 494248121522, 6153003414039, 38125026176659, 13635112709648, 39350572537836, 511502485322923, 1069875349612147, 5075263842958032

Offset: 0

Alois P. Heinz, Mar 01 2021

nonn

			a(4) = 1: {{1,6}, {2,5}, {3,8}, {4,7}}.
a(5) = 2: {{1,6}, {2,9}, {3,10}, {4,7}, {5,8}}, {{1,6}, {2,5}, {3,8}, {4,9}, {7,10}}.

Wikipedia, Partition of a set

Cf. A000341, A009692, A342139, A342155.

b:= proc(s) option remember; `if`(s={}, 1, (j-> add(`if`(i b({$1..2*n}):
seq(a(n), n=0..15);

b[s_] := b[s] = If[s == {}, 1, With[{j = Max[s]}, Sum[If[i < j && AllTrue[{j+i, j-i}, PrimeQ], b[s ~Complement~ {i, j}], 0], {i, s}]]];
a[n_] := b[Range[2n]];
a /@ Range[0, 15] (* Jean-François Alcover, Aug 25 2021, after Alois P. Heinz *)

a(25)-a(35) from Bert Dobbelaere, Mar 06 2021

A342139 Number of partitions of [2n] into pairs whose sums or differences are primes.

Original entry on oeis.org

1, 1, 3, 8, 28, 167, 810, 4664, 38344, 207255, 2059900, 19385131, 174417011, 1922011637, 21058799803, 208257199434, 2905150193223, 38462668421772, 481607876817202, 7526871509864950

Offset: 0

Alois P. Heinz, Mar 01 2021

			a(2) = 3: {{1,4}, {2,3}}, {{1,3}, {2,4}}, {{1,2}, {3,4}}.

Wikipedia, Partition of a set

Cf. A000341, A009692, A342136, A342155.

b:= proc(s) option remember; `if`(s={}, 1, (j-> add(`if`(i b({$1..2*n}):
seq(a(n), n=0..15);

b[s_] := b[s] = If[s == {}, 1, With[{j = Max[s]}, Sum[If[i < j && AnyTrue[{j+i, j-i}, PrimeQ], b[s ~Complement~ {i, j}], 0], {i, s}]]];
a[n_] := b[Range[2n]];
a /@ Range[0, 15] (* Jean-François Alcover, Aug 25 2021, after Alois P. Heinz *)

A342155 Number of partitions of [2n] into pairs such that either their sum or their absolute difference is a prime (but not both).

Original entry on oeis.org

1, 1, 2, 3, 7, 26, 55, 282, 1520, 2685, 27005, 171474, 768123, 5936728, 43976303, 207493790, 2570789335, 21669733984, 136340261314, 1639978185920

Offset: 0

Alois P. Heinz, Mar 02 2021

			a(4) = 7:
  {{1,8}, {2,7}, {3,5}, {4,6}},
  {{1,8}, {2,7}, {3,4}, {5,6}},
  {{1,8}, {2,4}, {3,6}, {5,7}},
  {{1,8}, {2,3}, {4,6}, {5,7}},
  {{1,8}, {2,4}, {3,5}, {6,7}},
  {{1,3}, {2,4}, {5,7}, {6,8}},
  {{1,2}, {3,4}, {5,7}, {6,8}}.

Wikipedia, Partition of a set

Cf. A000040, A000341, A009692, A291564, A342136, A342139.

b:= proc(s) option remember; `if`(s={}, 1, (j-> add(`if`(i b({$1..2*n}):
seq(a(n), n=0..15);

b[s_] := b[s] = If[s == {}, 1, With[{j = Max[s]}, Sum[If[i < j && (PrimeQ[j + i] ~Xor~ PrimeQ[j - i]), b[s ~Complement~  {i, j}], 0], {i, s}]]];
a[n_] := b[Range[2n]];
a /@ Range[0, 15] (* Jean-François Alcover, Aug 25 2021, after Alois P. Heinz *)

A000348 Number of ways to pair up {1^2, 2^2, ..., (2n)^2 } so sum of each pair is prime.

Original entry on oeis.org

1, 1, 2, 4, 12, 9, 72, 160, 428, 2434, 3011, 10337, 126962, 264182, 783550, 5004266, 34340141, 176302123, 1188146567, 4457147441, 7845512385, 132253267889, 1004345333251, 3865703506342, 40719018858150, 213982561376958, 1266218151414286, 10976172953868304, 59767467676582641, 512279001476451101, 6189067229056357433

Offset: 1

S. J. Greenfield (greenfie(AT)math.rutgers.edu)

B. K. Agarwala and F. C. Auluck, Statistical mechanics and partitions into non-integral powers of integers, Proc. Camb. Phil. Soc., 47 (1951), 207-216. [Annotated scanned copy]
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. A000341.

a[n_] := Permanent[Table[Boole[PrimeQ[(2*i)^2 + (2*j - 1)^2]], {i, 1, n}, {j, 1, n}]]; Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 1, 22}] (* Jean-François Alcover, Jan 06 2016, after T. D. Noe *)

permRWNb(a)=n=matsize(a)[1];if(n==1,return(a[1,1]));sg=1;nc=0;in=vectorv(n);x=in;x=a[,n]-sum(j=1,n,a[,j])/2;p=prod(i=1,n,x[i]);for(k=1,2^(n-1)-1,sg=-sg;j=valuation(k,2)+1;z=1-2*in[j];in[j]+=z;nc+=z;x+=z*a[,j];p+=prod(i=1,n,x[i],sg));return(2*(2*(n%2)-1)*p)
for(n=1,24,a=matrix(n,n,i,j,isprime((2*i)^2+(2*j-1)^2));print1(permRWNb(a)", ")) \\ Herman Jamke (hermanjamke(AT)fastmail.fm), May 13 2007

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

a(11)-a(16) from David W. Wilson
a(17)-a(22) from T. D. Noe, Feb 10 2007
a(23)-a(24) from Herman Jamke (hermanjamke(AT)fastmail.fm), May 13 2007
More terms from Sean A. Irvine, Nov 14 2010

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

A071810 Number of subsets of the first n primes whose sum is a prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Extensions

A070897 Number of ways of pairing numbers 1 to n with numbers n+1 to 2n such that each pair sums to a prime.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

Extensions

A009692 Number of partitions of {1, 2, ..., 2n} into pairs whose differences are primes.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica

Extensions

A134293 Number of ways to pair up {2..2n+1} so the sum of each pair is prime.

Views

Author

Keywords

Comments

Examples

Links

Programs

Mathematica

PARI

Formula

Extensions

A342136 Number of partitions of [2n] into pairs whose sums and differences are primes.

Views

Author

Keywords

Examples

Links