A074063 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 (1) adjacent integers sum to a prime number and (2) squares of adjacent numbers sum to a prime number. Rotations and reversals are counted only once.

1, 1, 1, 1, 0, 1, 0, 0, 0, 3, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1481, 4266, 0, 0, 5624, 0

Offset: 1

Author

T. D. Noe, Aug 17 2002

Keywords

• hard
• more
• nice
• nonn

Comments

It is known that a(n) > 0 for 58 <= n <= 200. It is conjectured that a(n) > 0 for all n > 57. A greedy algorithm can be used to quickly find a solution for many n. See the link to puzzle 189 for more details. 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(58) > 2.65*10^6; a(59) > 4.45*10^6. - Alexander D. Healy, Apr 07 2025

Examples

			a(4)=1 because there is essentially one arrangement: {3,2,1,4}.
		

Links

• Carlos Rivera, Puzzle 189: Squares and primes in a row, The Prime Puzzles & Problems Connection.

Crossrefs

Cf. A073451, A073452.

Programs

Mathematica

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

Extensions

a(52)-a(57) from Alexander D. Healy, Apr 01 2025