|
| |
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
LINKS
|
|
|
|
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).
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
