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

Author

T. D. Noe, Aug 02 2002

Keywords

• hard
• more
• nice
• nonn

Comments

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.

Examples

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

Links

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

Crossrefs

Cf. A073451, A051252.

Programs

Mathematica

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

Extensions

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