Project Euler 704 - Factors of Two in Binomial Coefficients

Official link:

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

Further reading on the OEIS page shows that F(n) = x(n) - y(n) where x(n) =, y(n) =

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) = and the summation of y(n) =

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)