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

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

Author

Martin Fuller, Jun 06 2006

Keywords

• nonn

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

Examples

			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.
		

Links

• Skirtle's Den, Pandigital Polydivisible Numbers

Crossrefs

Cf. A029940 Product phi(d); d divides n.

Cf. A000010 Euler totient function phi(n).

Programs

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