A103839 Number of permutations of (1,2,3,...,n) where each of the (n-1) adjacent pairs of elements sums to a prime.

1, 2, 2, 8, 4, 16, 24, 60, 140, 1328, 2144, 17536, 23296, 74216, 191544, 2119632, 4094976, 24223424, 45604056, 241559918, 675603568, 8723487720, 22850057800, 285146572432, 859834538938, 8276479696196, 32343039694056, 429691823372130

Offset: 1

Author

N. J. A. Sloane, Mar 30 2005

Keywords

• nonn

Comments

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

Examples

			For n = 5, we have the 4 permutations and the sums of adjacent elements:
1,4,3,2,5 (1+4=5, 4+3=7, 3+2=5, 2+5=7)
3,4,1,2,5 (3+4=7, 4+1=5, 1+2=3, 2+5=7)
5,2,1,4,3 (5+2=7, 2+1=3, 1+4=5, 4+3=7)
5,2,3,4,1 (5+2=7, 2+3=5, 3+4=7, 4+1=5)
		

Crossrefs

Cf. A051239, A051252.

Programs

Mathematica

A103839[n_] := Count[Map[lpf, Permutations[Range[n]]], 0]
lpf[x_] := Length[Select[asf[x], ! PrimeQ[#] &]];
asf[x_] := Module[{i}, Table[x[[i]] + x[[i + 1]], {i, Length[x] - 1}]];
Table[A103839[n], {n, 1, 9}] (* Robert Price, Oct 25 2018 *)

PARI

okperm(perm) = {for (k=1, #perm -1, if (! isprime(perm[k]+perm[k+1]), return (0));); return (1);}
a(n) = {nbok = 0; for (j=1, n!, perm = numtoperm(n, j); if (okperm(perm), nbok++);); return (nbok);} \\ Michel Marcus, Apr 08 2013

Formula

For n>1, a(n) = 2 * A051239(n).

Extensions

More terms from Max Alekseyev, Jan 04 2008

a(25)-a(28) from Giovanni Resta, Apr 01 2014