Project Euler 754 - Product of Gauss Factorials

Official link: https://projecteuler.net/problem=754

Note: My code takes around ~2400s

Thought Process

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:

  1. Sieve all the Totient and Möbius values, in arrays, phi_sieve, and mu_sieve

  2. Pre-compute all modulo factorial values in and array factorial

  3. Initialise a variable G = ∏ n^φ(n), n = 1 to 10^8

  4. 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):

    1. Initialise a common value which I call fac = factorial[d]/d^d, use modulo division as well

    2. 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)

    3. Then multiply G by fac^mu_total

  5. 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

Interactive Code

Enter an integer (yourinput)

Code will output G(yourinput) mod (10^9 + 7)