Project Euler 650 - Divisors of Binomial Product

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

Thought Process

Recall the formula for sum of divisors function. It is based on the prime factorization of B(n), this mean that we don't actually need to calculate B(n) which grows too fast, instead we simply keep track of it's prime factorization.

We derive a relation for B(n) using B(n - 1) as follows:

Therefore, if we have the prime factorization of B(n - 1) we just need to add the prime factors of n^n and remove the factors of n!

Prime factors of n^n: This is easy, just take prime factorization of n and if p^e divides n where p is a prime, then p^(ne) divides n^n. Essentially we just need the prime factorization of n.
Prime factors of n!: We can use Legendre's formula, but this becomes too slow. Instead, I precompute the prime factors of n! iteratively using prime factors of (n - 1)! and n.

In both of these cases we see that we need the prime factors of n, since 20,000 is quite small I just pre-compute all of them using a variation of the prime generation function.

Interactive Code

Enter a number (yourinput)

Code will output S(yourinput) (mod 1,000,000,007)

Page updated

Google Sites

Report abuse