Project Euler 704 - Factors of Two in Binomial Coefficients

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

Thought Process

Whenever it comes to finding factors of factorials, I am reminded of Legendre's Formula which lead me to Kummer's Theorem which is exactly what is needed to efficiently calculate g(n, m)

We also note that S2(n) is just the bit count of n, also known as the Hamming Weight. Using this we can very efficiently calculate g(n, m).

After generating the first few values of F(n) I found that it corresponds to https://oeis.org/A119387.

Further reading on the OEIS page shows that F(n) = x(n) - y(n) where x(n) = https://oeis.org/A000523, y(n) = https://oeis.org/A007814

Then S(n) is just the summation of F(n) and further reading on both the OEIS pages for x(n), and y(n) I found that the summation of x(n) = https://oeis.org/A061168 and the summation of y(n) = https://oeis.org/A011371.

This all results in a single line formula as shown below and gives an instant solution to the problem.

Interactive Code

Enter an integer (yourinput)

Code will output S(yourinput)

Page updated

Google Sites

Report abuse