cp's OEIS Frontend

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

%I A103839 #30 Dec 31 2023 00:57:20
%S A103839 1,2,2,8,4,16,24,60,140,1328,2144,17536,23296,74216,191544,2119632,
%T A103839 4094976,24223424,45604056,241559918,675603568,8723487720,22850057800,
%U A103839 285146572432,859834538938,8276479696196,32343039694056,429691823372130
%N A103839 Number of permutations of (1,2,3,...,n) where each of the (n-1) adjacent pairs of elements sums to a prime.
%C 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 add up to a prime. - _Bob Andriesse_, Oct 04 2020
%C A103839 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
%F A103839 For n>1, a(n) = 2 * A051239(n).
%e A103839 For n = 5, we have the 4 permutations and the sums of adjacent elements:
%e A103839 1,4,3,2,5 (1+4=5, 4+3=7, 3+2=5, 2+5=7)
%e A103839 3,4,1,2,5 (3+4=7, 4+1=5, 1+2=3, 2+5=7)
%e A103839 5,2,1,4,3 (5+2=7, 2+1=3, 1+4=5, 4+3=7)
%e A103839 5,2,3,4,1 (5+2=7, 2+3=5, 3+4=7, 4+1=5)
%t A103839 A103839[n_] := Count[Map[lpf, Permutations[Range[n]]], 0]
%t A103839 lpf[x_] := Length[Select[asf[x], ! PrimeQ[#] &]];
%t A103839 asf[x_] := Module[{i}, Table[x[[i]] + x[[i + 1]], {i, Length[x] - 1}]];
%t A103839 Table[A103839[n], {n, 1, 9}] (* _Robert Price_, Oct 25 2018 *)
%o A103839 (PARI) okperm(perm) = {for (k=1, #perm -1, if (! isprime(perm[k]+perm[k+1]), return (0));); return (1);}
%o A103839 a(n) = {nbok = 0; for (j=1, n!, perm = numtoperm(n, j); if (okperm(perm), nbok++);); return (nbok);} \\ _Michel Marcus_, Apr 08 2013
%Y A103839 Cf. A051239, A051252.
%K A103839 nonn
%O A103839 1,2
%A A103839 _N. J. A. Sloane_, Mar 30 2005
%E A103839 More terms from _Max Alekseyev_, Jan 04 2008
%E A103839 a(25)-a(28) from _Giovanni Resta_, Apr 01 2014