Project Euler 754 - Product of Gauss Factorials
Official link: https://projecteuler.net/problem=754
Note: My code takes around ~2400s
I quickly found the sequence https://oeis.org/A001783 which corresponds to g(n) and then I got stuck, came back to it recently and was able to make some major speed ups, although I only managed to get the final value in ~40 minutes.
On the OEIS page the following equation was listed:
This is all I used to solve the problem.
The basic structure of my code is as follows:
Sieve all the Totient and Möbius values, in arrays, phi_sieve, and mu_sieve
Pre-compute all modulo factorial values in and array factorial
Initialise a variable G = ∏ n^φ(n), n = 1 to 10^8
Notice that we can directly calculate G instead of calculating all g(n), therefore for each d, representing a divisor, we directly compute G. Therefore for d in range(2, 10^8):
Initialise a common value which I call fac = factorial[d]/d^d, use modulo division as well
Notice that for each number that d divides, there is no difference in fac, the only part that changes is μ(n/d), therefore we can directly sum all of the μ(n/d), for a given d. Let mu_total = sum of all μ(n/d)
Then multiply G by fac^mu_total
Make sure to use modulo calculations everywhere to avoid overflow errors!
With this process we omit a lot of repeated calculations, we are able to solve the problem in less than an hour, below I list some test cases as the code is still a bit slow:
G(10^4) = 517055464,
G(10^5) = 516871211,
G(10^6) = 557051244,
G(10^7) = 623561178
Enter an integer (yourinput)
Code will output G(yourinput) mod (10^9 + 7)