cp's OEIS Frontend

A120065 Number of permutations on 1..n where gcd(s_i,n) = gcd(i,n). Also Product_{d divides n} phi(d)!.

%I A120065 #15 Mar 06 2023 14:24:30
%S A120065 1,1,2,2,24,4,720,48,1440,576,3628800,192,479001600,518400,1935360,
%T A120065 1935360,20922789888000,2073600,6402373705728000,46448640,
%U A120065 689762304000,13168189440000,1124000727777607680000,185794560,58389648196239360000
%N A120065 Number of permutations on 1..n where gcd(s_i,n) = gcd(i,n). Also Product_{d divides n} phi(d)!.
%C A120065 The values of this sequence also represents the size of the search space for  pandigital polydivisible numbers, PPN, in some even base n. PPN in some base b are defined as numbers that contain all the nonzero digits 1..b without repetition, arranged such that the first k digits are divisible by k for the entire length of the number, e.g., in base 10: 381654729 or in base 14: 9C3A5476B812D. It can be shown that for a base, b, the i-th digit, d, is limited to values such that gcd(i,b)=gcd(d,b). Thus the search space for some base is the factorial applied to the counts of numbers that share a gcd in that base. - _Nicholas Stefan Georgescu_, Mar 06 2023
%H A120065 Skirtle's Den, <a href="http://skirtlesden.com/articles/pandigital-polydivisible-numbers">Pandigital Polydivisible Numbers</a>
%e A120065 a(8) = 48 = 4! * 2! * 1! * 1! because we can permute [1,3,5,7] in 4! ways, [2,6] in 2! ways and 4 and 8 are fixed.
%o A120065 (PARI) a(n) = prod(i=1, n, if(n%i==0, eulerphi(i)!, 1))
%o A120065 (Python)
%o A120065 from sympy import factorial, gcd
%o A120065 from numpy import product
%o A120065 from collections import Counter
%o A120065 [int(product(list(map(factorial,Counter([gcd(i,n) for i in range(1,n)]).values())))) for n in range(1,20)] # _Nicholas Stefan Georgescu_, Mar 06 2023
%Y A120065 Cf. A029940 Product phi(d); d divides n.
%Y A120065 Cf. A000010 Euler totient function phi(n).
%K A120065 nonn
%O A120065 1,3
%A A120065 _Martin Fuller_, Jun 06 2006