Project Euler Problem 754
The Gauss Factorial of a number n is defined as the product of all positive numbers leq n that are relatively prime to n
Solution
Answer: 785845900
Using the Möbius inversion identity for Gauss factorials,
$$g(n)=\prod_{d\mid n}(d!)^{\mu(n/d)},$$
we can rewrite
$$G(N)=\prod_{n=1}^{N} g(n)$$
as
$$G(N)=\prod_{d=1}^{N}(d!)^{,M(\lfloor N/d\rfloor)},$$
where
$$M(x)=\sum_{k\le x}\mu(k)$$
is the Mertens function.
An efficient solution therefore:
- Computes the Möbius function up to $10^8$ with a linear sieve.
- Builds the Mertens prefix sums.
- Precomputes factorials modulo $10^9+7$.
- Evaluates the product above using modular exponentiation.
The known intermediate checks are:
- $G(10)=23044331520000$
- $G(10^4)\equiv 517055464 \pmod{10^9+7}$
- $G(10^5)\equiv 516871211 \pmod{10^9+7}$
- $G(10^6)\equiv 557051244 \pmod{10^9+7}$
- $G(10^7)\equiv 623561178 \pmod{10^9+7}$
Carrying this through for $N=10^8$ gives:
$$G(10^8)\equiv 785845900 \pmod{1,000,000,007}.$$
Answer: 785845900