A051252 -id:A051252 - cp's OEIS frontend

A125712 Number of permutations of 1..2n in which the sum of every two adjacent elements is a prime number, including the sum of first and last elements.

2, 8, 12, 32, 960, 12288, 40320, 1296384, 13862592, 126186000, 4703871392, 153495217056, 4312093043076, 225409456295800, 7671288697001460

Offset: 1

DoZerg (daidodo(AT)gmail.com), Feb 01 2007

For 2n=4 we have a(2) = 8. One of the permutations is 1 4 3 2. Let's check: 1 + 4 = 5 is a prime number; 4 + 3 = 7 is a prime number; 3 + 2 = 5 is a prime number; 2 + 1 = 3 is a prime number; so we say it's a legal permutation.
a(n) = 4*n*A051252(n), n>1. - Vladeta Jovovic, Feb 02 2007
As explicitly checked for 2<=n<=9, a(n)=4*n*A051252(n). This is twice the length of the permutation multiplied by A051252(n), where the factor 4n counts the permutations generated by any of the 2n cyclic shifts or any of the 2n cyclic shifts followed by reversal. The exception is for n=1, where reversal and shift yield the same image of the permutation. - R. J. Mathar, Nov 02 2007

			a(2) = 8 because we can generate 8 different permutations:
1 2 3 4
1 4 3 2
2 1 4 3
2 3 4 1
3 2 1 4
3 4 1 2
4 1 2 3
4 3 2 1
in which the sum of every two adjacent elements is a prime number, including the sum of first and last elements.

a(8) and a(9) from R. J. Mathar, Nov 02 2007

a(10)-a(15) (using A051252) from Alois P. Heinz, Nov 03 2024

A132178 Triangle read by rows: T(n,m) is the number of cyclic permutations of [n] in which m of successive numbers add to a prime. 0<=m<=n, read by rows n>=0.

Original entry on oeis.org

0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 2, 0, 1, 0, 2, 4, 4, 2, 0, 1, 6, 19, 16, 15, 2, 1, 6, 36, 84, 108, 90, 24, 12, 0, 44, 230, 542, 722, 602, 266, 98, 14, 2, 208, 1284, 3478, 5272, 5202, 3004, 1378, 264, 70, 0, 912, 6856, 21784, 39496, 46816, 35680, 20824, 6616, 2224, 184, 48

Offset: 0

R. J. Mathar, Nov 04 2007

The last entry of the (2n)th row is A051252(n). Row sums are apparently in A001710(n-1).

			The triangle starts
n|
0| 0
1| 0 1
2| 0 0 1
3| 0 0 1 0
4| 0 0 2 0 1
5| 0 2 4 4 2 0
6| 1 6 19 16 15 2 1
7| 6 36 84 108 90 24 12 0
8| 44 230 542 722 602 266 98 14 2
9| 208 1284 3478 5272 5202 3004 1378 264 70 0
10| 912 6856 21784 39496 46816 35680 20824 6616 2224 184 48
11| 8016 58232 188160 358080 449424 380592 237888 95280 32880 4776 1072 0
12| 61952 465472 1597312 3298432 4563264 4406592 3152064 1578816 641088 151936 38336 2624 512

A191798 Number of essentially different ways of arranging numbers 1 through 2*n around a circle so that the sums of each pair of adjacent numbers are neither all prime nor all composite.

Original entry on oeis.org

0, 2, 58, 2474, 180480, 19895936, 3105348340, 652948189204, 177662757810868, 60772232945639507, 25533219938917963508, 12921764841857675170314, 7754002391777621430686566

Offset: 1

Bennett Gardiner, Jun 16 2011

Finding a pattern, recurrence relation or explicit formula for this sequence would allow us to find terms in A191374 using terms from A051252, or vice versa.

			a(2) = 2 since the arrangements 1,3,2,4 and 1,3,4,2 both satisfy the condition.

Cf. A051252, A191374.

For n>1, a(n) = (2*n-1)!/2 - A051252(n) - A191374(n).

a(7) corrected, a(8)-a(13) added by Max Alekseyev, Aug 19 2013

A229232 Number of undirected circular permutations pi(1), ..., pi(n) of 1, ..., n with the n numbers pi(1)pi(2)-1, pi(2)pi(3)-1, ..., pi(n-1)pi(n)-1, pi(n)pi(1)-1 all prime.

Original entry on oeis.org

0, 0, 0, 1, 0, 2, 1, 2, 2, 8, 2, 241, 0, 693, 376, 7687, 1082, 127563, 25113, 1353842, 559649

Offset: 1

Zhi-Wei Sun, Sep 16 2013

Conjecture: a(n) > 0 for all n > 5 with n not equal to 13.
Zhi-Wei Sun also made the following conjectures:
(1) For any integer n > 1, there is a permutation pi(1), ..., pi(n) of 1, ..., n such that the n numbers 2*pi(1)*pi(2)-1, ..., 2*pi(n-1)*pi(n)-1, 2*pi(n)*pi(1)-1 are all prime. Also, for any positive integer n not equal to 4, there is a permutation pi(1), ..., pi(n) of 1, ..., n such that the n numbers 2*pi(1)*pi(2)+1, ..., 2*pi(n-1)*pi(n)+1, 2*pi(n)*pi(1)+1 are all prime.
(2) Let F be a finite field with q > 7 elements. Then, there is a circular permutation a_1,...,a_{q-1} of the q-1 nonzero elements of F such that all the q-1 elements a_1*a_2-1, a_2*a_3-1, ..., a_{q-2}*a_{q-1}-1, a_{q-1}*a_1-1 are primitive elements of the field F (i.e., generators of the multiplicative group F\{0}). Also, there is a circular permutation b_1,...,b_{q-1} of the q-1 nonzero elements of F such that all the q-1 elements b_1*b_2+1, b_2*b_3+1, ..., b_{q-2}*b_{q-1}+1, b_{q-1}*b_1+1 are primitive elements of the field F.

			a(4) = 1 due to the circular permutation (1,3,2,4).
a(6) = 2 due to the circular permutations
   (1,3,2,4,5,6) and (1,3,2,6,5,4).
a(7) = 1 due to the circular permutation (1,3,2,7,6,5,4).
a(8) = 2 due to the circular permutations
   (1,3,2,7,6,5,4,8) and (1,4,5,6,7,2,3,8).
a(9) = 2 due to the circular permutations
   (1,3,4,5,6,7,2,9,8) and (1,3,8,9,2,7,6,5,4).
a(10) = 8 due to the circular permutations
   (1,3,4,5,6,7,2,9,10,8), (1,3,4,5,6,7,2,10,9,8),
   (1,3,8,9,10,2,7,6,5,4), (1,3,8,10,9,2,7,6,5,4),
   (1,3,10,8,9,2,7,6,5,4), (1,3,10,9,2,7,6,5,4,8),
   (1,4,5,6,7,2,3,10,9,8), (1,4,5,6,7,2,9,10,3,8).
a(13) = 0 since 8 is the unique j among 1, ..., 12 with 13*j-1 prime.

Zhi-Wei Sun, Some new problems in additive combinatorics, preprint, arXiv:1309.1679 [math.NT], 2013-2014.

Cf. A051252, A227456, A228917, A228956, A229082.

(* A program to compute required circular permutations for n = 8. To get "undirected" circular permutations, we should identify a circular permutation with the one of the opposite direction; for example, (1,8,4,5,6,7,2,3) is identical to (1,3,2,7,6,5,4,8) if we ignore direction. Thus, a(8) is half of the number of circular permutations yielded by this program. *)
V[i_]:=V[i]=Part[Permutations[{2,3,4,5,6,7,8}],i]
f[i_,j_]:=f[i,j]=PrimeQ[i*j-1]
m=0
Do[Do[If[f[If[j==0,1,Part[V[i],j]],If[j<7,Part[V[i],j+1],1]]==False,Goto[aa]],{j,0,7}];
m=m+1;Print[m,":"," ",1," ",Part[V[i],1]," ",Part[V[i],2]," ",Part[V[i],3]," ",Part[V[i],4]," ",Part[V[i],5]," ",Part[V[i],6]," ",Part[V[i],7]];Label[aa];Continue,{i,1,7!}]

a(11)-a(21) from Pontus von Brömssen, Jan 08 2025

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

Original entry on oeis.org

0, 0, 0, 4, 7, 71, 2555, 24897, 970556

Offset: 1

Michel Lagneau, Mar 25 2015

Conjecture: a(n) > 0 for all n > 3.

This implies the semiprime conjecture, and it is similar to the prime circle problem mentioned in A051252.

			Four arrangements for 2n = 8 are:
{1,3,6,8,7,2,4,5},
{1,3,7,2,8,6,4,5},
{1,5,4,2,7,3,6,8},
{1,5,4,6,3,7,2,8}, so a(4) = 4;
Seven arrangements for 2n = 10 are:
{1,3,6,8,7,2,4,10,5,9},
{1,3,6,9,5,10,4,2,7,8},
{1,3,7,2,4,10,5,9,6,8},
{1,3,7,2,8,6,4,10,5,9},
{1,5,10,4,2,8,7,3,6,9},
{1,8,2,7,3,6,4,10,5,9},
{1,8,6,3,7,2,4,10,5,9}, so a(5) = 7;

Cf. A051252.

$RecursionLimit=500; try[lev_] := Module[{t, j}, If[lev>2n, (*then make sure the sum of the first and last is semiprime*) If[Plus@@Last/@FactorInteger [soln[[1]]+soln[[2n]]]==2&&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&& Plus@@Last/@FactorInteger [i+j]==2, AppendTo[s[[i]], j]]]]; soln=Table[0, {2n}]; soln[[1]]=1; cnt=0; try[2]; AppendTo[lst, cnt]]; lst

A294184 a(n) is the number of ways to arrange numbers from 1 to 2*n in a row, starting with 1, such that the sum of every two adjacent numbers is prime, but also considering the ends as adjacent.

Original entry on oeis.org

1, 2, 2, 4, 96, 1024, 2880, 81024, 770144, 6309300, 213812336, 6395634044, 165849732426, 8050337724850, 255709623233382

Offset: 1

Michel Marcus, Feb 11 2018

When the size of the row is odd, it is impossible to find such an arrangement, so that sequence is only defined for even-sized rows.

			a(1) = 1, because of [1, 2].
a(2) = 2, because of [1, 2, 3, 4] and [1, 4, 3, 2].
a(3) = 2, because of [1, 4, 3, 2, 5, 6] and [1, 6, 5, 2, 3, 4].

Situ Zhengmei, Prime ring, Chinese Math Blog.

Cf. A036440, A051252, A051239, A242527, A242528.

a(n) = 2*A051252(n), for n > 1. - Giovanni Resta, Feb 25 2020

a(9)-a(11) from Jackson Bahm, Feb 25 2020

a(12)-(15) from Giovanni Resta, using A051252, Feb 25 2020

cp's OEIS Frontend

A125712 Number of permutations of 1..2n in which the sum of every two adjacent elements is a prime number, including the sum of first and last elements.

Views

Author

Keywords

Comments

Examples

Extensions

A132178 Triangle read by rows: T(n,m) is the number of cyclic permutations of [n] in which m of successive numbers add to a prime. 0<=m<=n, read by rows n>=0.

Views

Author

Keywords

Comments

Examples

A191798 Number of essentially different ways of arranging numbers 1 through 2*n around a circle so that the sums of each pair of adjacent numbers are neither all prime nor all composite.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A229232 Number of undirected circular permutations pi(1), ..., pi(n) of 1, ..., n with the n numbers pi(1)*pi(2)-1, pi(2)*pi(3)-1, ..., pi(n-1)*pi(n)-1, pi(n)*pi(1)-1 all prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A294184 a(n) is the number of ways to arrange numbers from 1 to 2*n in a row, starting with 1, such that the sum of every two adjacent numbers is prime, but also considering the ends as adjacent.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A229232 Number of undirected circular permutations pi(1), ..., pi(n) of 1, ..., n with the n numbers pi(1)pi(2)-1, pi(2)pi(3)-1, ..., pi(n-1)pi(n)-1, pi(n)pi(1)-1 all prime.