login
A367704
Number of permutations of [n] where each pair of adjacent elements differs by a prime.
3
1, 1, 0, 0, 2, 10, 32, 96, 448, 1968, 7320, 21516, 118938, 662742, 4556360, 26950038, 155388246, 756995286, 5730299976, 38809702892, 337875402936, 2593543573702, 20560179519176, 138677553274430, 1337517942958934, 11083936316867572, 94288296012340842
OFFSET
0,5
COMMENTS
This sequence was inspired by A103839 and the PARI program is a modified version of the one in A103839.
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 differ by a prime.
A076220, A103839 and this sequence are closely related, but their combined graph in the link shows an interesting difference, notably between this sequence and the two others. - Bob Andriesse, Dec 03 2023
EXAMPLE
a(4) = 2: 2413, 3142.
a(5) = 10: 13524, 14253, 24135, 25314, 31425, 35241, 41352, 42531, 52413, 53142.
PROG
(PARI) okperm(perm) = {for (k=1, #perm -1, if (! isprime(abs(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); }
CROSSREFS
Sequence in context: A103290 A131068 A324172 * A034555 A084154 A265836
KEYWORD
nonn
AUTHOR
Bob Andriesse, Nov 27 2023
EXTENSIONS
a(14)-a(22) from Alois P. Heinz, Nov 27 2023
a(23)-a(26) from Martin Ehrenstein, Dec 03 2023
STATUS
approved