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

Offset

1,10

Comments

The first 51 terms are given. a(n) > 0 for n=52, 53, and 56, and a(n) = 0 for n=54, 55, and 57. 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.

Links

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

Carlos Rivera, Puzzle 189: Squares and primes in a row

Example

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

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]]<soln[[n]])||(circular&&soln[[1]]==1&&soln[[2]]<=soln[[n]]), (*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={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]&&PrimeQ[i+j], 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. A073451, A073452.

Sequence in context: A361579 A066746 A278105 * A338211 A115717 A339632

Adjacent sequences: A074060 A074061 A074062 * A074064 A074065 A074066

Keyword

hard,more,nice,nonn

Author

T. D. Noe, Aug 17 2002

Status

approved