cp's OEIS Frontend

A359951 Number of permutations of [n] such that the GCD of the cycle lengths is a prime.

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