A073451 Number of essentially different ways in which the squares 1,4,9,...,n^2 can be arranged in a sequence such that all pairs of adjacent squares sum to a prime number. Rotations and reversals are counted only once.

1, 1, 1, 1, 2, 4, 0, 12, 6, 66, 156, 44, 312, 1484, 2672, 6680, 19080, 45024, 168496, 2033271, 724543, 2776536, 24598062, 26849699, 345160845, 4478968678, 5094833662, 14184530127, 29116554754, 125878922175

Offset

1,5

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=10 exhibits the first of these rotational solutions: {1,4,9,64,49,100,81,16,25,36}. The Mathematica program uses a backtracking algorithm to count the arrangements. To print the unique arrangements, remove the comments from around the print statement.

Links

Table of n, a(n) for n=1..30.

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

Example

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

Mathematica

nMax=12; $RecursionLimit=500; try[lev_] := Module[{t, j, circular}, If[lev>n, circular=PrimeQ[soln[[1]]^2+soln[[n]]^2]; If[(!circular&&soln[[1]]<soln[[n]])||(circular&&soln[[1]]==1&&soln[[2]]<=soln[[n]]), (*Print[soln^2]; *)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={1}; n=2, n<=nMax, n++, s=Table[{}, {n}]; For[i=1, i<=n, i++, For[j=1, j<=n, j++, If[i!=j&&PrimeQ[i^2+j^2], AppendTo[s[[i]], j]]]]; soln=Table[0, {n}]; For[cnt=0; i=1, i<=n, i++, soln[[1]]=i; try[2]]; AppendTo[lst, cnt]]; lst

Crossrefs

Cf. A072129, A073452.

Sequence in context: A066529 A052080 A261754 * A078022 A203850 A106603

Adjacent sequences: A073448 A073449 A073450 * A073452 A073453 A073454

Keyword

hard,more,nice,nonn

Author

T. D. Noe, Aug 02 2002

Extensions

a(24)-a(30) from Martin Ehrenstein, Jul 19 2023

Status

approved