Search: a000341 -id:a000341
|
| |
|
|
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.
|
|
+10
26
|
|
|
|
1, 1, 1, 2, 48, 512, 1440, 40512, 385072, 3154650, 106906168, 3197817022, 82924866213, 4025168862425, 127854811616691
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
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
|
|
|
REFERENCES
|
R. K. Guy, Unsolved Problems in Number Theory, second edition, Springer, 1994. See section C1.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
One arrangement for 2n=6 is 1,4,3,2,5,6 and this is essentially unique, so a(3)=1.
|
|
|
MATHEMATICA
|
$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 *)
|
|
|
PROG
|
(C++) listed in the link (S. Sykora)
|
|
|
CROSSREFS
|
Cf. A000341, A070897, A072616, A072617, A072618, A072676, A072184, A103839, A227050, A228917, A242527, A242528.
|
|
|
KEYWORD
|
nonn,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A073364
|
|
Number of permutations p of (1,2,3,...,n) such that k+p(k) is prime for 1<=k<=n.
|
|
+10
12
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
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
|
|
|
LINKS
|
|
|
|
FORMULA
|
|
|
|
MATHEMATICA
|
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]];
|
|
|
PROG
|
(PARI) a(n)=sum(k=1, n!, n==sum(i=1, n, isprime(i+component(numtoperm(n, k), i))))
(PARI) a(n)={matpermanent(matrix(n, n, i, j, isprime(i + j)))} \\ Andrew Howroyd, Nov 03 2018
(Haskell)
a073364 n = length $ filter (all isprime)
$ map (zipWith (+) [1..n]) (permutations [1..n])
where isprime n = a010051 n == 1 -- cf. A010051
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
a(10) from Mohammed Bouayoun (bouyao(AT)wanadoo.fr), Mar 14 2004
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A070897
|
|
Number of ways of pairing numbers 1 to n with numbers n+1 to 2n such that each pair sums to a prime.
|
|
+10
7
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,5
|
|
|
LINKS
|
|
|
|
FORMULA
|
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
|
|
|
EXAMPLE
|
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.
|
|
|
MATHEMATICA
|
<<Combinatorica`; listQpart2[ n_ ] := {n-#, #}&/@Range[ Floor[ (n-1)/2 ] ]; Noe[ n_Integer ] := Module[ {it, permoid, po}, it=Union@Flatten[ Cases[ listQpart2[ # ], q_/; Max[ q ]<=2*n&&Max[ q ]>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 *)
|
|
|
PROG
|
(Haskell)
import Data.List (permutations)
a070897 n = length $ filter (all ((== 1) . a010051))
$ map (zipWith (+) [1..n]) (permutations [n+1..2*n])
(PARI) 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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nice,nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A071810
|
|
Number of subsets of the first n primes whose sum is a prime.
|
|
+10
7
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
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
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
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.
|
|
|
MATHEMATICA
|
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 *)
|
|
|
PROG
|
(Haskell)
import Data.List (subsequences)
a071810 = sum . map a010051' . map sum .
tail . subsequences . flip take a000040_list
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A009692
|
|
Number of partitions of {1, 2, ..., 2n} into pairs whose differences are primes.
|
|
+10
4
|
|
|
|
1, 0, 1, 3, 10, 40, 153, 921, 5144, 30717, 230748, 1766056, 14052445, 116580521, 897876519, 7657321097, 75743979608, 788733735080, 7569825650083, 75242386295617, 831978453306391, 9444103049405370, 120064355466770831, 1579842230380587833
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
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
|
|
|
MAPLE
|
b:= proc(s) option remember; `if`(s={}, 1, (j-> add(`if`(i<j
and isprime(j-i), b(s minus {i, j}), 0), i=s))(max(s)))
end:
a:= n-> b({$1..2*n}):
|
|
|
MATHEMATICA
|
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]];
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,hard
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A134293
|
|
Number of ways to pair up {2..2n+1} so the sum of each pair is prime.
|
|
+10
2
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
|
|
|
LINKS
|
|
|
|
FORMULA
|
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.
|
|
|
EXAMPLE
|
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}}.
|
|
|
MATHEMATICA
|
a[n_] := Permanent[Array[Boole[PrimeQ[2 #1 + 2 #2 + 1]]&, {n, n}]];
|
|
|
PROG
|
(PARI) a(n)={matpermanent(matrix(n, n, i, j, isprime(2*i + 2*j + 1)))} \\ Andrew Howroyd, Nov 03 2018
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A342136
|
|
Number of partitions of [2n] into pairs whose sums and differences are primes.
|
|
+10
2
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,6
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
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}}.
|
|
|
MAPLE
|
b:= proc(s) option remember; `if`(s={}, 1, (j-> add(`if`(i<j and
andmap(isprime, [j+i, j-i]), b(s minus {i, j}), 0), i=s))(max(s)))
end:
a:= n-> b({$1..2*n}):
seq(a(n), n=0..15);
|
|
|
MATHEMATICA
|
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]];
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A342139
|
|
Number of partitions of [2n] into pairs whose sums or differences are primes.
|
|
+10
2
|
|
|
|
1, 1, 3, 8, 28, 167, 810, 4664, 38344, 207255, 2059900, 19385131, 174417011, 1922011637, 21058799803, 208257199434, 2905150193223, 38462668421772, 481607876817202, 7526871509864950
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
a(2) = 3: {{1,4}, {2,3}}, {{1,3}, {2,4}}, {{1,2}, {3,4}}.
|
|
|
MAPLE
|
b:= proc(s) option remember; `if`(s={}, 1, (j-> add(`if`(i<j and
ormap(isprime, [j+i, j-i]), b(s minus {i, j}), 0), i=s))(max(s)))
end:
a:= n-> b({$1..2*n}):
seq(a(n), n=0..15);
|
|
|
MATHEMATICA
|
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]];
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,more
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A342155
|
|
Number of partitions of [2n] into pairs such that either their sum or their absolute difference is a prime (but not both).
|
|
+10
2
|
|
|
|
1, 1, 2, 3, 7, 26, 55, 282, 1520, 2685, 27005, 171474, 768123, 5936728, 43976303, 207493790, 2570789335, 21669733984, 136340261314, 1639978185920
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
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}}.
|
|
|
MAPLE
|
b:= proc(s) option remember; `if`(s={}, 1, (j-> add(`if`(i<j and
(isprime(j+i) xor isprime(j-i)), b(s minus {i, j}), 0), i=s))(max(s)))
end:
a:= n-> b({$1..2*n}):
seq(a(n), n=0..15);
|
|
|
MATHEMATICA
|
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]];
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,more
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A000348
|
|
Number of ways to pair up {1^2, 2^2, ..., (2n)^2 } so sum of each pair is prime.
|
|
+10
1
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
LINKS
|
|
|
|
FORMULA
|
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
|
|
|
MATHEMATICA
|
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 *)
|
|
|
PROG
|
(PARI) 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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,nice
|
|
|
AUTHOR
|
S. J. Greenfield (greenfie(AT)math.rutgers.edu)
|
|
|
EXTENSIONS
|
a(23)-a(24) from Herman Jamke (hermanjamke(AT)fastmail.fm), May 13 2007
|
|
|
STATUS
|
approved
|
| |
|
Search completed in 0.027 seconds
|
