login
A103839
Number of permutations of (1,2,3,...,n) where each of the (n-1) adjacent pairs of elements sums to a prime.
7
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,2
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 2<n<26, for even n in this range A076220(n) / a(n) < A076220(n-1) / a(n-1). - Bob Andriesse, Dec 05 2023
FORMULA
For n>1, a(n) = 2 * A051239(n).
EXAMPLE
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)
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 *)
PROG
(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
CROSSREFS
Sequence in context: A143625 A003612 A337944 * A135727 A320423 A274449
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Mar 30 2005
EXTENSIONS
More terms from Max Alekseyev, Jan 04 2008
a(25)-a(28) from Giovanni Resta, Apr 01 2014
STATUS
approved