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

A242528 Number of cyclic arrangements of {0,1,...,n-1} such that both the difference and the sum of any two neighbors are prime.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 4, 18, 13, 62, 8, 133, 225, 209, 32, 2644, 4462, 61341, 113986, 750294, 176301, 7575912, 3575686, 7705362, 36777080, 108638048, 97295807

Offset: 1

Stanislav Sykora, May 30 2014

a(n)=NPC(n;S;P) is the count of all neighbor-property cycles for a specific set S of n elements and a specific pair-property P. For more details, see the link and A242519.

In this case the set is S={0 through n-1}. For the same pair-property P but the set S={1 through n}, see A227050.

			For n=12 (the first n for which a(n)>0) there are two such cycles:
C_1={0, 5, 2, 9, 4, 1, 6, 11, 8, 3, 10, 7},
C_2={0, 7, 10, 3, 8, 5, 2, 9, 4, 1, 6, 11}.

S. Sykora, On Neighbor-Property Cycles, Stan's Library, Volume V, 2014.

Cf. A227050, A242519, A242520, A242521, A242522, A242523, A242524, A242525, A242526, A242527, A242529, A242530, A242531, A242532, A242533, A242534.

A242528[n_] :=
Count[Map[lpf, Map[j0f, Permutations[Range[n - 1]]]], 0]/2;
j0f[x_] := Join[{0}, x, {0}];
lpf[x_] := Length[
   Join[Select[asf[x], ! PrimeQ[#] &],
    Select[Differences[x], ! PrimeQ[#] &]]];
asf[x_] := Module[{i}, Table[x[[i]] + x[[i + 1]], {i, Length[x] - 1}]];
Table[A242528[n], {n, 1, 8}]
(* OR, a less simple, but more efficient implementation. *)
A242528[n_, perm_, remain_] := Module[{opt, lr, i, new},
   If[remain == {},
     If[PrimeQ[First[perm] - Last[perm]] &&
       PrimeQ[First[perm] + Last[perm]], ct++];
     Return[ct],
     opt = remain; lr = Length[remain];
     For[i = 1, i <= lr, i++,
      new = First[opt]; opt = Rest[opt];
      If[! (PrimeQ[Last[perm] - new] && PrimeQ[Last[perm] + new]),
       Continue[]];
      A242528[n, Join[perm, {new}],
       Complement[Range[n - 1], perm, {new}]];
      ];
     Return[ct];
     ];
   ];
Table[ct = 0; A242528[n, {0}, Range[n - 1]]/2, {n, 1, 18}]
(* Robert Price, Oct 22 2018 *)

a(29)-a(33) from Fausto A. C. Cariboni, May 20 2017

A086825 Number of knots (prime or composite) with n crossings.

Original entry on oeis.org

1, 0, 0, 1, 1, 2, 5, 8, 26

Offset: 0

Steven Finch, Aug 07 2003

For n = 0, we have the trivial knot (the unknot), which is neither a prime knot nor a composite knot. - Daniel Forgues, Feb 12 2016

			a(7)=8 since we have 7 prime knots and one composite knot (the connected sum 3_1#4_1 of the trefoil knot 3_1 and the figure eight knot 4_1). Note that 3_1*#4_1=3_1#4_1, where * denotes mirror image because 4_1 is achiral.
a(8)=26 since we have 21 prime knots and five composites (3_1#5_1, 3_1#5_2, 3_1*#5_1, 3_1*#5_2, and 4_1#4_1).

S. R. Finch, Knots, links and tangles, August 8, 2003. [Cached copy, with permission of the author]
Eric Weisstein's World of Mathematics, Knot
Eric Weisstein's World of Mathematics, Unknot
Index entries for sequences related to knots

Cf. A002863 (prime knots), A227050, A086826.

A283314 gives the partial sums.

a(8) corrected by Kyle Miller, Oct 14 2020

A228626 Number of Hamiltonian cycles in the undirected simple graph G_n with vertices 1,...,n which has an edge connecting vertices i and j if and only if |i-j| is prime.

Original entry on oeis.org

0, 0, 0, 0, 1, 2, 4, 16, 60, 186, 433, 2215, 11788, 76539, 414240, 2202215, 9655287, 69748712, 444195809, 3703859949, 26688275292, 201673532931, 1265944917365, 11801735916539, 92511897525830, 753795624276096, 5237677221537738, 41074291450736424, 280906738160126067

Offset: 1

Zhi-Wei Sun, Aug 28 2013

Conjecture: a(n) > 0 for all n > 4. In other words, for each n = 5,6,... there is a permutation i_1,...,i_n of 1,...,n such that |i_1-i_2|, |i_2-i_3|, ..., |i_{n-1}-i_n| and |i_n-i_1| are all prime.
Note that this conjecture is different from the prime circle problem in A051252 though they look similar.
On August 30 2013, Yong-Gao Chen (from Nanjing Normal University) confirmed the conjecture for n > 12 as follows: If n = 2*k then G_n contains a Hamiltonian cycle (1,3,5,2,7,9,...,2k-5,2k-3,2k,2k-2,2k-4,2k-1,2k-6,2k-8,...,6,4);
if n = 2*k + 1 then G_n contains a Hamiltonian cycle
  (1,3,5,2,7,9,...,2k-5,2k,2k-3,2k-1,2k+1,2k-2,2k-4,...,6,4).
We have got Chen's approval to include his proof here.

			a(5) = 1 since G_5 contains the unique Hamiltonian cycle (1,4,2,5,3).
a(6) = 2 since G_6 contains exactly two Hamiltonian cycles: (1,3,5,2,4,6) and (1,4,2,5,3,6).
a(7) = 4 since G_7 contains exactly four Hamiltonian cycles: (1,3,5,2,7,4,6), (1,3,5,7,2,4,6), (1,4,2,7,5,3,6) and (1,4,7,2,5,3,6).
a(8) = 16 since G_8 contains exactly 16 Hamiltonian cycles: (1,3,5,2,7,4,6,8), (1,3,5,7,2,4,6,8), (1,3,6,4,2,7,5,8), (1,3,6,4,7,2,5,8), (1,3,6,8,5,2,7,4), (1,3,6,8,5,7,2,4), (1,3,8,5,2,7,4,6), (1,3,8,5,7,2,4,6), (1,4,2,7,5,3,6,8), (1,4,2,7,5,3,8,6), (1,4,2,7,5,8,3,6), (1,4,7,2,5,3,6,8), (1,4,7,2,5,3,8,6), (1,4,7,2,5,8,3,6), (1,6,4,2,7,5,3,8), (1,6,4,7,2,5,3,8).
a(9) > 0 since (1,3,5,7,9,2,4,6,8) is a Hamiltonian cycle in G_9.
a(10) > 0 since (1,3,5,2,4,6,9,7,10,8) is a Hamiltonian cycle in G_{10}.
a(11) > 0 since (1,3,5,10,8,11,9,2,7,4,6) is a Hamiltonian cycle in G_{11}.
a(12) > 0 since (1,3,8,10,5,2,7,4,6,11,9,12) is a Hamiltonian cycle in G_{12}.

Hong-Bin Chen, Hung-Lin Fu, Jun-Yi Guo, Beyond Hamiltonicity of Prime Difference Graphs, arXiv:2003.00729 [math.CO], 2020.
S. Sykora, On Neighbor-Property Cycles, Stan's Library, Volume V, 2014. See Table II.
Index entries for sequences related to graphs, Hamiltonian

Cf. A000040, A051239, A051252, A185645, A227050, A242527, A242528.

Table[Length[FindHamiltonianCycle[Graph[Flatten[Table[If[PrimeQ[Abs[i - j]], i \[UndirectedEdge] j, {}], {i, 1, n}, {j, i + 1, n}]]], Infinity]], {n, 1, 15}] (* Robert Price, Apr 04 2019 *)

a(9)-a(17) from Alois P. Heinz, Aug 28 2013
a(18)-a(19) from Stanislav Sykora, May 30 2014
a(20)-a(29) from Max Alekseyev, Jul 04 2014

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

A242528 Number of cyclic arrangements of {0,1,...,n-1} such that both the difference and the sum of any two neighbors are prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A086825 Number of knots (prime or composite) with n crossings.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A228626 Number of Hamiltonian cycles in the undirected simple graph G_n with vertices 1,...,n which has an edge connecting vertices i and j if and only if |i-j| is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions