A051252 -id:A051252 - cp's OEIS frontend

A073452 a(n) is the number of essentially different ways in which the integers 1,2,3,...,n can be arranged in a sequence such that all pairs of adjacent integers sum to a prime number. Rotations and reversals are counted only once.

1, 1, 1, 1, 2, 3, 12, 16, 70, 232, 1072, 3136, 11648, 18388, 95772, 452136, 2047488, 5565488, 22802028, 60841609, 337801784, 2116714332, 11425028900, 69023494710, 429917269469

Offset: 1

T. D. Noe, Aug 02 2002

Note that when the first and last numbers of an arrangement sum to a prime, then there are n rotations that are treated as one arrangement. The case n=6 exhibits rotational solutions: {1,4,3,2,5,6}, which is actually a prime circle. See A051252 for more details about prime circles.

The Mathematica program uses a backtracking algorithm to count the arrangements. To print the unique arrangements, remove the comments from around the print statement. It seems that a greedy algorithm can be used to quickly find a solution for any n.

			a(5)=2 because there are two essential different arrangements: {1,4,3,2,5} and {3,4,1,2,5}.

Carlos Rivera, Conjecture 20. The first N natural numbers listed in an order such that the sum of each two adjacent of them is a prime number, and the Rivera's Algorithm, The Prime Puzzles & Problems Connection.
Carlos Rivera, Puzzle 189. Squares and primes in a row, The Prime Puzzles & Problems Connection.

Cf. A073451, A051252.

nMax=12; $RecursionLimit=500; try[lev_] := Module[{t, j, circular}, If[lev>n, circular=PrimeQ[soln[[1]]+soln[[n]]]; If[(!circular&&soln[[1]]

a(21)-a(25) from Martin Ehrenstein, Jul 19 2023

A228860 Number of permutations i_1,...,i_n of 1,...,n with i_1 = 1 and i_n = n, and with the n adjacent sums i_1+i_2, i_2+i_3, ..., i_{n-1}+i_n, i_n+i_1 all coprime to n.

Original entry on oeis.org

1, 1, 0, 1, 2, 1, 40, 36, 144, 78, 126336, 176, 14035200, 69480, 779436, 25401600, 465334732800, 1700352, 127064889262080, 1888106496, 1479065243520, 1774752094080, 18353630943019008000, 144127475712, 116009818818379776000, 30959322906758400, 373881853408444416000

Offset: 1

Zhi-Wei Sun, Sep 05 2013

Conjecture: a(n) > 0 except for n = 3.
If n is a power of two, then a(n) > 0 since the identical permutation 1,2,3,...,n meets the requirement. For any prime p > 3, we have a(p) > 0 since the permutation 1,...,(p-1)/2, (p+3)/2,(p+1)/2,(p+5)/2,...,p meets our purpose.
Let G(n) be the undirected simple graph with vertices 1,...,n which has an edge connecting two distinct vertices i and j if and only if i + j is relatively prime to n. Then, for any n > 2, the number a(n) is just the number of those Hamiltonian cycles in G(n) on which the vertices 1 and n are adjacent.
Let m be any integer relatively prime to n, and let i_k be the smallest positive residue of k*m modulo n. Then i_1, i_2, ..., i_n is a permutation of 1, ..., n with the n adjacent differences i_1-i_2, i_2-i_3, ..., i_{n-1}-i_n, i_n-i_1 all coprime to n.
On Sep 06 2013, the author's two former PhD students Hui-Qin Cao (from Nanjing Audit Univ.) and Hao Pan (from Nanjing Univ.) proved the conjecture fully.

			a(4) = 1 due to the permutation 1,2,3,4.
a(5) = 2 due to the permutations 1,2,4,3,5 and 1,3,4,2,5.
a(6) = 1 due to the permutation 1,4,3,2,5,6.
a(7) > 0 due to the permutation 1,2,3,5,4,6,7.
a(8) > 0 due to the permutation 1,2,3,4,5,6,7,8.
a(9) > 0 due to the permutation 1,3,2,5,8,6,4,7,9.
a(10) > 0 due to the permutation 1,2,5,4,7,6,3,8,9,10.
a(11) > 0 due to the permutation 1,2,3,4,5,7,6,8,9,10,11.
a(12) > 0 due to the permutation 1,4,9,2,5,8,3,10,7,6,11,12.

Cf. A051252, A185645, A228626, A228728, A228762, A228766.

(*A program to compute the required permutations for n = 9.*)
V[i_]:=Part[Permutations[{2,3,4,5,6,7,8}],i]
m=0
Do[Do[If[GCD[If[j==0,1,Part[V[i],j]]+If[j<7,Part[V[i],j+1],9],9]>1,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]," ",9];Label[aa];Continue,{i,1,7!}]

a(12)-a(27) from Max Alekseyev, Sep 13 2013

A072184 Complement of A072676.

Original entry on oeis.org

17, 23, 32, 38, 44, 47, 59, 62, 65, 71, 77, 80, 86, 92, 101, 104, 107, 110, 122, 128, 137, 143, 146, 149, 152, 161, 164, 167, 170, 176, 179, 182, 185, 188, 191, 194, 197, 200, 203, 206, 212, 218, 224, 227, 233, 236, 239, 242, 245, 248, 251, 254, 257, 263, 266, 269, 272, 275, 278, 287, 290

Offset: 1

T. D. Noe, Jul 01 2002

nonn

Eric Weisstein's World of Mathematics, Prime Circle.

Cf. A051252, A072676.

Offset corrected and entry revised by Sean A. Irvine, Sep 08 2024

A072676 Numbers k for which the prime circle problem has a solution composed of disjoint subsets: the arrangement of numbers 1 through 2k around a circle is such that the sum of each pair of adjacent numbers is prime, the odd numbers are in order and the even numbers are in groups of decreasing sequences.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22, 24, 25, 26, 27, 28, 29, 30, 31, 33, 34, 35, 36, 37, 39, 40, 41, 42, 43, 45, 46, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 60, 61, 63, 64, 66, 67, 68, 69, 70, 72, 73, 74, 75, 76, 78, 79, 81, 82, 83, 84

Offset: 1

T. D. Noe, Jul 01 2002

This is a generalization of A072618. The integer k is in this sequence if either (a) 4k-1 and 2k+1 are prime, or (b) 2k+2i-1, 2k+2i+1 and 2i+1 are prime for some 0 < i < k. The Mathematica program computes a prime circle for such k. It is very easy to show that there are prime circles for large k, such as 10^10.

			k=10 is a term because one solution is {1, 2, 3, 8, 5, 6, 7, 4, 9, 20, 11, 18, 13, 16, 15, 14, 17, 12, 19, 10} and the even numbers are in three decreasing sequences {2}, {8, 6, 4} and {20, 18, 16, 14, 12, 10}. Note that this solution contains {1, 2} and {1, 2, 3, 8, 5, 6, 7, 4}, which are solutions for k=1 and k=4.

Eric Weisstein's World of Mathematics, Prime Circle.

Cf. A051252, A072616, A072617, A072618, A072184.

n=10; lst={}; i=0; found=False; While[i0, i=0; found=False; While[i

A132163 Triangle read by rows. For row n, start with 1 but from the second term onwards always choose the largest positive integer between 1 and n inclusive that i) has not already appeared in the row ii) gives a prime when added to the previous term. Stop if no such integer can be found.

Original entry on oeis.org

1, 1, 2, 1, 2, 3, 1, 4, 3, 2, 1, 4, 3, 2, 5, 1, 6, 5, 2, 3, 4, 1, 6, 7, 4, 3, 2, 5, 1, 6, 7, 4, 3, 8, 5, 2, 1, 6, 7, 4, 9, 8, 5, 2, 3, 1, 10, 9, 8, 5, 6, 7, 4, 3, 2, 1, 10, 9, 8, 11, 6, 7, 4, 3, 2, 5, 1, 12, 11, 8, 9, 10, 7, 6, 5, 2, 3, 4

Offset: 1

Paul Boddington, Nov 04 2007

The following statements are conjectural: 1) The n-th row is always a permutation of 1,...,n. 2) For the even rows, the last term is one less than a prime (so the row gives a solution to the prime circle problem - see A051252). 3) There exists a (unique) sequence b(2), b(3),... with the property that for every n > 1 there is a positive integer N such that every even row of the triangle from the 2N-th onwards ends b(n), ..., b(3), b(2) and every odd row from the (2N - 1)-th onwards ends b(n)+(-1)^n, ..., b(3)-1, b(2)+1. (If the sequence b(n) exists it is probably A132075 without the initial term 1.)

Reinhard Zumkeller, Rows n = 1..150 of triangle, flattened

This sequence is a variation on A088643.

import Data.List (delete)
a132163_tabl = map a132163_row [1..]
a132163 n k = a132163_row n !! (k-1)
a132163_row n = 1 : f 1 [n, n-1 .. 2] where
   f u vs = g vs where
     g []                            = []
     g (x:xs) | a010051 (x + u) == 1 = x : f x (delete x vs)
              | otherwise            = g xs
-- Reinhard Zumkeller, Jan 05 2013

t[, 1] = 1; t[n, k_] := t[n, k] = For[ j = n, j > 1, j--, If[ PrimeQ[ t[n, k-1] + j] && FreeQ[ Table[ t[n, m], {m, 1, k-1}], j], Return[j] ] ]; Table[ t[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Apr 02 2013 *)

A191374 Number of ways (up to rotations and reflections) of arranging numbers 1 through 2n around a circle such that the sum of each pair of adjacent numbers is composite.

Original entry on oeis.org

0, 0, 1, 44, 912, 61952, 8160260, 888954284, 180955852060, 50317255621843, 12251146829850324, 4243527581615332664, 1602629887788636447221, 622433536382831426225696, 344515231090957672408413959

Offset: 1

Bennett Gardiner, Jun 01 2011

One of the obvious analogs of sequence A051252, which has the sums being prime. Presumably it is an open problem as to whether a(n) > 0 always for this problem as well.

The Guy reference deals with each adjacent pair summing to a prime. - T. D. Noe, Jun 08 2011

			a(3) = 1, the arrangement is 1,3,6,2,4,5.

R. K. Guy, Unsolved Problems in Number Theory, section C1.

Cf. A051252.

function D=primecirc(n)
tic
a = 2:2*n;
A=perms(a);
for i =1:factorial(2*n-1)
B(i,:)=[1 A(i,:)];
end
for k=1:size(B,2)-1
    F(:,k) = B(:,k)+B(:,k+1);
end
if k>1
F(:,k+1)=B(:,end)+B(:,1);
end
l=1;
for i=1:factorial(2*n-1)
if ~isprime(F(i,:)) == ones(1,length(B(1,:)))
C(l,:)=B(i,:);
l=l+1;
end
end
if ~exist('C')
    D=0;
    return
end
if size(C,1)==1
D=1;
else
D=size(C,1)/2;
end
toc

Bisection of A182540: a(n) = A182540(2*n). - Max Alekseyev, Aug 18 2013

a(8)-a(15) from Max Alekseyev, Aug 19 2013

A072129 Number of distinct ways of arranging the squares {1,4,9,...,(2n)^2} in a circle so that the sum of each two adjacent entries is a prime.

Original entry on oeis.org

1, 0, 0, 0, 6, 0, 96, 272, 1408, 61622, 33736, 356606, 86520774, 192570133, 1560696233

Offset: 1

Santi Spadaro, Jun 25 2002

			a(5)=6 because there are 6 essentially different ways: {1, 4, 9, 64, 49, 100, 81, 16, 25, 36}, {1, 4, 49, 64, 9, 100, 81, 16, 25, 36}, {1, 16, 81, 100, 9, 4, 49, 64, 25, 36}, {1, 16, 81, 100, 9, 64, 49, 4, 25, 36}, {1, 16, 81, 100, 49, 4, 9, 64, 25, 36} and {1, 16, 81, 100, 49, 64, 9, 4, 25, 36}

Cf. A051252, A073451.

$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]]^2+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&&PrimeQ[i^2+j^2], AppendTo[s[[i]], j]]]]; soln=Table[0, {2n}]; soln[[1]]=1; cnt=0; try[2]; AppendTo[lst, cnt]]; lst

Corrected and extended by T. D. Noe, Jul 03 2002

a(13) corrected and a(14)-a(15) from Sean A. Irvine, Sep 03 2024

A134292 Triangle in which row n is the lexicographically earliest solution to the prime circle problem for 2n.

Original entry on oeis.org

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

Offset: 1

T. D. Noe, Oct 16 2007

In the prime circle problem we seek to arrange the numbers 1 to 2n around a circle so that the sum of each pair of adjacent numbers is prime. To display the solution, we unroll the circle starting at 1.

			Triangle begins:
1, 2;
1, 2, 3, 4;
1, 4, 3, 2, 5, 6;
1, 2, 3, 8, 5, 6, 7, 4;
...

R. K. Guy, Unsolved Problems Number Theory, Section C1.

T. D. Noe, Rows n=1..50 of triangle, flattened
Eric Weisstein's World of Mathematics, Prime Circle

Cf. A051252 (number of solutions for each n), A051237 (prime pyramid).

A182540 Number of ways of arranging the numbers 1 through n on a circle so that no sum of two adjacent numbers is prime, up to rotations and reflections.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 6, 44, 208, 912, 8016, 61952, 671248, 8160620, 87412258, 888954284, 12156253488, 180955852060, 2907927356451, 50317255621843, 802326797235038, 12251146829850324, 233309934271940028, 4243527581615332664, 79533825261873435894, 1602629887788636447221, 30450585799991840921483, 622433536382831426225696, 14891218890120375419560713, 344515231090957672408413959

Offset: 1

Jens Voß, May 04 2012

nonn

			If n < 6, then in every arrangement of the numbers 1 through n on a circle, there are two adjacent numbers adding up to a prime. For n = 6, the only arrangement without a prime sum is (1, 3, 6, 2, 4, 5).

Cf. A051252, A073452, A191374

a(15)-a(17) from Alois P. Heinz, May 04 2012
a(18) from R. H. Hardin, May 07 2012
a(19)-a(30) from Max Alekseyev, Aug 19 2013

A073467 a(n) is the number of essentially different ways in which the integers 1,2,3,...,2n can be arranged in a circle such that (1) all pairs of adjacent integers sum to a prime number and (2) all pairs of integers opposite each other on the circle sum to a prime.

Original entry on oeis.org

1, 0, 0, 0, 4, 0, 8, 0, 556, 0, 16156, 0, 4545745, 0, 1697587998, 0

Offset: 1

T. D. Noe, Aug 02 2002

Note that a(n) = 0 for all even n because opposite numbers sum to an even number. The Mathematica program uses a backtracking algorithm to count the arrangements. To print the unique arrangements, remove the comments from around the print statement.

			a(5)=4 because there are four essential different arrangements: {1,2,3,4,7,6,5,8,9,10}, {1,2,3,10,7,6,5,8,9,4}, {1,2,9,4,7,6,5,8,3,10} and {1,2,9,10,7,6,5,8,3,4}.

Carlos Rivera, Puzzle 176: Primes in a Circle

Cf. A051252.

maxN=9; $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]]], If[lev<=n||MemberQ[s[[soln[[lev-n]]]], s[[t]][[j]]], soln[[lev]]=s[[t]][[j]]; try[lev+1]; soln[[lev]]=0]]]]]; For[lst={}; n=1, n<=maxN, 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]]]]; Delete[s[[1]], -1]; (* these will all be duplicates *) soln=Table[0, {2n}]; soln[[1]]=1; cnt=0; try[2]; AppendTo[lst, cnt]]; lst

a(14)-a(16) from Bert Dobbelaere, Jun 24 2019

cp's OEIS Frontend

A073452 a(n) is the number of essentially different ways in which the integers 1,2,3,...,n can be arranged in a sequence such that all pairs of adjacent integers sum to a prime number. Rotations and reversals are counted only once.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A228860 Number of permutations i_1,...,i_n of 1,...,n with i_1 = 1 and i_n = n, and with the n adjacent sums i_1+i_2, i_2+i_3, ..., i_{n-1}+i_n, i_n+i_1 all coprime to n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A072184 Complement of A072676.

Views

Author

Keywords

Links

Crossrefs

Extensions

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A132163 Triangle read by rows. For row n, start with 1 but from the second term onwards always choose the largest positive integer between 1 and n inclusive that i) has not already appeared in the row ii) gives a prime when added to the previous term. Stop if no such integer can be found.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

A191374 Number of ways (up to rotations and reflections) of arranging numbers 1 through 2n around a circle such that the sum of each pair of adjacent numbers is composite.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

MATLAB

Formula

Extensions

A072129 Number of distinct ways of arranging the squares {1,4,9,...,(2n)^2} in a circle so that the sum of each two adjacent entries is a prime.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Extensions

A134292 Triangle in which row n is the lexicographically earliest solution to the prime circle problem for 2n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A182540 Number of ways of arranging the numbers 1 through n on a circle so that no sum of two adjacent numbers is prime, up to rotations and reflections.

Views