OFFSET
1,4
COMMENTS
a(n) = 1 iff n = 1 or is prime. For composite n, n and a(n) always have the same prime factors (but not necessarily the same multiplicity).
It appears that a(n) is usually larger for even n. The smallest odd n such that a(n) > a(n+1) is 45; the smallest odd n such that a(n) > a(n-1) is 63; the smallest odd n such that a(n) > a(n+1) and a(n) > a(n-1) is 315.
FORMULA
a(n) = Product_{p<=n-1} gcd(n, p-1)*p^(v(p, n)) if n odd or n = 2, 4; 2*Product_{p<=n-1} gcd(n, p-1)*p^(v(p, n)) if n even >= 6, where the product is taken over the primes and v(p, n) is the p-adic valuation of n.
EXAMPLE
The solutions to x^4 == 1 (mod 4!) is x == 1, 5, 7, 11, 13, 17, 19, 23 (mod 24), so a(4) = 8.
Note that the multiplicative group of integers modulo 6! = 720 is isomorphic to C_2 X C_2 X C_4 X C_12, so a(6) = gcd(6, 2)*gcd(6, 2)*gcd(6, 4)*gcd(6, 12) = 2*2*2*6 = 48.
PROG
(PARI) a(n)=prod(i=1, primepi(n-1), gcd(n, prime(i)-1)*prime(i)^valuation(n, prime(i)))*(if(n<=4||Mod(n, 2)==1, 1, 2))
CROSSREFS
KEYWORD
nonn
AUTHOR
Jianing Song, Aug 29 2018
STATUS
approved