A367704 Number of permutations of [n] where each pair of adjacent elements differs by a prime.

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

Links

Table of n, a(n) for n=0..26.

Bob Andriesse, Combined graph of this sequence, A076220 and A103839 for a(4) to a(25)

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

Cf. A076220, A103839.

Sequence in context: A103290 A131068 A324172 * A034555 A084154 A265836

Adjacent sequences: A367701 A367702 A367703 * A367705 A367706 A367707

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