|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
LINKS
|
|
|
FORMULA
|
|
|
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}]];
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|