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

A072617 Number of essentially different ways of arranging numbers 1 through 2n around a circle so that the sum of each pair of adjacent numbers is prime, with the odd and even numbers in order in opposite directions.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 0, 0, 2, 1, 1, 2, 0, 0, 1, 1, 1, 3, 0, 0, 1, 0, 0, 2, 1, 1, 2, 0, 0, 2, 1, 1, 1, 0, 0, 3, 0, 0, 1, 0, 0, 3, 0, 0, 3, 1, 1, 1, 1, 1, 3, 0, 0, 0, 0, 0, 5, 0, 0, 3, 0, 0, 4, 1, 1, 4, 0, 0, 2, 1, 1, 2, 0, 0, 2, 0, 0, 4, 0, 0, 5, 0, 0, 4, 1, 1, 5, 0, 0, 3, 1, 1, 2, 1, 1, 4, 0

Offset: 1

T. D. Noe, Jun 25 2002

A very restricted form of the prime circle problem whose sequence is A051252. Finding these solutions is very fast because there are only n possible solutions to try. See A072616 for the case where only the odd numbers or only the even numbers are in order. Note that a(2)=1 because the two solutions are essentially the same. Solutions can be printed by removing comments from the Mathematica program.

There is a provable solution for n when either (a) 2n+1 and 2n+3 are prime, (b) 2k+1, 2k+3, 2k+2n+1 and 2k+2n+3 are prime for some 0 < k < n-1, or (c) 2n-1, 2n+1 and 4n-1 are primes. Part (a) is due to Mike Hennebry. Note that cases (a) and (b) involve 3 sets of twin primes. For n > 3, due to the form of twin primes, it can be shown that (a) implies not (b) and not (c).

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

T. D. Noe, Table of n, a(n) for n=1..1000
Eric Weisstein's World of Mathematics, Prime Circle.

Cf. A051252, A072616, A072618.

For[lst={}; n=1, n<=100, n++, oddTable=Append[Table[2i-1, {i, n}], 1]; evenTable=Table[2n+2-2i, {i, n}]; evenTable=Join[evenTable, evenTable]; For[cnt=0; i=1, i<=n, i++, j=0; allPrime=True; While[j

A072618 Numbers n for which the prime circle problem has a simple solution: the arrangement of numbers 1 through 2n around a circle is such that the sum of each pair of adjacent numbers is prime and the odd and even numbers are in order in opposite directions.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 13, 14, 15, 18, 19, 20, 21, 24, 27, 28, 29, 30, 33, 34, 35, 36, 39, 42, 45, 48, 49, 50, 51, 52, 53, 54, 60, 63, 66, 67, 68, 69, 72, 73, 74, 75, 78, 81, 84, 87, 88, 89, 90, 93, 94, 95, 96, 97, 98, 99, 102, 105, 108, 111, 112, 113, 114, 117, 118

Offset: 1

T. D. Noe, Jun 25 2002

A very restricted form of the prime circle problem whose sequence is A051252. This sequence lists the n for which A072617(n) is positive. See A072616 for the case where only the odd numbers or only the even numbers are in order.

			n=6 is on the list because the simple solution is {1, 10, 3, 8, 5, 6, 7, 4, 9, 2, 11, 12}.

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Prime Circle.

Cf. A051252, A072616, A072617.

Cf. A010051.

import Data.List (transpose)
a072618 n = a072618_list !! (n-1)
a072618_list = filter f [1 ..] where
   f x = any (all ((== 1) . a010051' . fromIntegral)) $
         map cs [concat $ transpose [[2*x, 2*x-2 .. 2] , us] |
                 us <- map (uncurry (++) . (uncurry $ flip (,))
                            . flip splitAt [1, 3 .. 2 * x]) [1 .. x]]
   cs zs = (head zs + last zs) : zipWith (+) zs (tail zs)
-- Reinhard Zumkeller, Mar 17 2013

For[lst={}; n=1, n<=100, n++, oddTable=Append[Table[2i-1, {i, n}], 1]; evenTable=Table[2n+2-2i, {i, n}]; evenTable=Join[evenTable, evenTable]; For[cnt=0; i=1, i<=n, i++, j=0; allPrime=True; While[j0, AppendTo[lst, n]]]; lst

More terms from Robert G. Wilson v, Jun 28 2002

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

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

A072617 Number of essentially different ways of arranging numbers 1 through 2n around a circle so that the sum of each pair of adjacent numbers is prime, with the odd and even numbers in order in opposite directions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A072618 Numbers n for which the prime circle problem has a simple solution: the arrangement of numbers 1 through 2n around a circle is such that the sum of each pair of adjacent numbers is prime and the odd and even numbers are in order in opposite directions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Extensions

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica