A120065 - OEIS

%I #15 Mar 06 2023 14:24:30

%S 1,1,2,2,24,4,720,48,1440,576,3628800,192,479001600,518400,1935360,

%T 1935360,20922789888000,2073600,6402373705728000,46448640,

%U 689762304000,13168189440000,1124000727777607680000,185794560,58389648196239360000

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

%C 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 Skirtle's Den, <a href="http://skirtlesden.com/articles/pandigital-polydivisible-numbers">Pandigital Polydivisible Numbers</a>

%e 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 (PARI) a(n) = prod(i=1, n, if(n%i==0, eulerphi(i)!, 1))

%o (Python)

%o from sympy import factorial, gcd

%o from numpy import product

%o from collections import Counter

%o [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 Cf. A029940 Product phi(d); d divides n.

%Y Cf. A000010 Euler totient function phi(n).

%K nonn

%O 1,3

%A _Martin Fuller_, Jun 06 2006