cp's OEIS Frontend

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

For the same pair-property P but the set {1 through n}, see A051252. Using for pair-property the difference, rather than the sum, one obtains A228626.

The number of Hamiltonian paths in a graph of which the nodes represent the numbers (1,2,3,...,n) and the edges connect each pair of nodes that add up to a prime. - Bob Andriesse, Oct 04 2020

While A076220(n) > a(n) for 2A076220(n) / a(n) < A076220(n-1) / a(n-1). - Bob Andriesse, Dec 05 2023

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.

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

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

For each n = 2,3,... construct an undirected simple graph T(n) with vertices 0,1,...,n which has an edge connecting two distinct vertices i and j if and only if 6*(i+j)-1 and 6*(i+j)+1 are twin primes. Then a(n) is just the number of Hamiltonian cycles contained in T(n). Thus a(n) > 0 if and only if T(n) is a Hamilton graph.

Zhi-Wei Sun also made the following similar conjectures for odd primes, Sophie Germain primes, cousin primes and sexy primes:

(1) For any integer n > 0, there is a permutation i_0, i_1, ..., i_n of 0, 1, ..., n such that i_0+i_1, i_1+i_2, ..., i_{n-1}+i_n, i_n+i_0 are integers of the form (p-1)/2, where p is an odd prime. Also, we may replace the above (p-1)/2 by (p+1)/4 or (p-1)/6; when n > 4 we may substitute (p-1)/4 for (p-1)/2.

(2) For any integer n > 2, there is a permutation i_0, i_1, ..., i_n of 0, 1,..., n such that i_0+i_1, i_1+i_2, ..., i_{n-1}+i_n, i_n+i_0 are integers of the form (p+1)/6, where p is a Sophie Germain prime.

(3) For any integer n > 3, there is a permutation i_0, i_1, ..., i_n of 0, 1,..., n such that i_0+i_1, i_1+i_2, ..., i_{n-1}+i_n, i_n+i_0 are among those integers k with 6*k+1 and 6*k+5 both prime.

(4) For any integer n > 4, there is a permutation i_0, i_1, ..., i_n of 0, 1,..., n such that i_0+i_1, i_1+i_2, ..., i_{n-1}+i_n, i_n+i_0 are among those integers k with 2*k-3 and 2*k+3 both prime.

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

Note that if i-j = (p-1)/2 and i+j = (q-1)/2 for some odd primes p and q then 4*i+2 is the sum of the two primes p and q. So the conjecture is related to Goldbach's conjecture.

Zhi-Wei Sun also made the following similar conjecture: For any integer n > 5, there exists a circular permutation i_0, i_1, ..., i_n of 0, 1, ..., n such that all the 2*n+2 numbers 2*|i_k-i_{k+1}|+1 and 2*(i_k+i_{k+1})-1 (k = 0,...,n) (with i_{n+1} = i_0) are primes.

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 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.

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).

See a similar problem, but for the set of numbers {0 through (n-1)}. - Stanislav Sykora, May 30 2014

Conjecture: a(n) > 0 except for n = 2, 4.

A restricted form of the prime circle problem whose sequence is A051252. Note that a(2)=1 because the two solutions are essentially the same. The number of solutions is the same for odd or even numbers in order because a solution having the odd numbers in order can be converted to a solution having even numbers in order by subtracting 1 from even numbers and adding 1 to odd numbers. For example, {1, 2, 3, 8, 5, 6, 7, 4, 9, 10} becomes {2, 1, 4, 7, 6, 5, 8, 3, 10, 9}. Is the number of solutions always positive? See A072617 for some simple solutions to the prime circle problem.