Project Euler 231: The prime factorisation of binomial coefficients
The binomial coefficient 10C3 = 120. ,
120 = 23 ×3 ×5 = 2 × 2 × 2 × 3 × 5, and 2 + 2 + 2 + 3 + 5 = 14.
So the sum of the terms in the prime factorisation of 10C3 is 14.
Find the sum of the terms in the prime factorisation of 20000000C15000000.
Calculating the binomial in this problem and factoring it would take too long so another method had to be discovered.
The paper “Prime Factors of Binomial Coefficients” by Samin Riasat explains Legendre's theorem for finding the prime factors and their exponents for factorials and this extends nicely to binomial coefficients.
An application of Legendre’s theorem is to find how many zeros are there at the end of a factorial.
Let’s say you want to find the number of zeros at the end of 1000! You just need to find how many times the factors 2 AND 5 (because 2 × 5 = 10) appear in the prime factorization of 1000!. Since 2 factors many more numbers without 5 but is always required with 5 in order to count the zeros we just concern ourselves with 5. To paraphrase the paper:
This method was used to solve SPOJ 11 Trailing zeros in a factorial.
Below: Legendre’s extension used in the program’s loop to calculate the prime’s exponent, if it’s a factor. Evaluates to either 1 or 0 and then summed:
I wanted to further improve performance and studied Kummer’s method for calculating the exponents of the prime factors but it didn’t seem like it would make it any faster.
Project Euler 231 SolutionRuns < 1.9 seconds in Python 2.7.
from Euler import prime_sieve n, r, s = 20000000, 15000000, 0 for p in prime_sieve(n): pj = p while pj <= n: s += p * (n//pj - r//pj - (n - r)//pj) pj *= p print "Project Euler 231 Solution =", sUse this link to get the Project Euler 231 Solution Python 2.7 source.
AnswerSlowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
No afterthoughts yet.