login
A120065
Number of permutations on 1..n where gcd(s_i,n) = gcd(i,n). Also Product_{d divides n} phi(d)!.
1
1, 1, 2, 2, 24, 4, 720, 48, 1440, 576, 3628800, 192, 479001600, 518400, 1935360, 1935360, 20922789888000, 2073600, 6402373705728000, 46448640, 689762304000, 13168189440000, 1124000727777607680000, 185794560, 58389648196239360000
OFFSET
1,3
COMMENTS
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
EXAMPLE
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.
PROG
(PARI) a(n) = prod(i=1, n, if(n%i==0, eulerphi(i)!, 1))
(Python)
from sympy import factorial, gcd
from numpy import product
from collections import Counter
[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
CROSSREFS
Cf. A029940 Product phi(d); d divides n.
Cf. A000010 Euler totient function phi(n).
Sequence in context: A122962 A048648 A229334 * A250033 A224479 A279311
KEYWORD
nonn
AUTHOR
Martin Fuller, Jun 06 2006
STATUS
approved