%I #17 Dec 13 2023 11:35:30
%S 0,0,1,2,3,24,145,720,4725,22400,602721,3628800,67692625,479001600,
%T 12924021825,103953833984,2116670180625,20922789888000,
%U 959231402754625,6402373705728000,257071215652932681,3242340687872000000,142597230222616430625,1124000727777607680000
%N Number of permutations of [n] such that the GCD of the cycle lengths is a prime.
%H Alois P. Heinz, <a href="/A359951/b359951.txt">Table of n, a(n) for n = 0..451</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation">Permutation</a>
%F a(n) = Sum_{prime p <= n} A346085(n,p).
%F a(p) = (p-1)! for prime p.
%e a(2) = 1: (12).
%e a(3) = 2: (123), (132).
%e a(4) = 3: (12)(34), (13)(24), (14)(23).
%e a(5) = 24: (12345), (12354), (12435), (12453), (12534), (12543), (13245), (13254), (13425), (13452), (13524), (13542), (14235), (14253), (14325), (14352), (14523), (14532), (15234), (15243), (15324), (15342), (15423), (15432).
%p b:= proc(n, g) option remember; `if`(n=0, `if`(isprime(g), 1, 0),
%p add(b(n-j, igcd(j, g))*(n-1)!/(n-j)!, j=1..n))
%p end:
%p a:= n-> b(n, 0):
%p seq(a(n), n=0..23);
%t b[n_, g_] := b[n, g] = If[n == 0, If[PrimeQ[g], 1, 0], Sum[b[n - j, GCD[j, g]]*(n - 1)!/(n - j)!, {j, 1, n}]];
%t a[n_] := b[n, 0];
%t Table[a[n], {n, 0, 23}] (* _Jean-François Alcover_, Dec 13 2023, after _Alois P. Heinz_ *)
%Y Cf. A000040, A000142, A005225, A079128, A214003, A346085, A346086.
%K nonn
%O 0,4
%A _Alois P. Heinz_, Jan 19 2023
|