// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 231 Solution

By ⋅ July 15, 2014 ⋅ Post a comment
Filed Under  , , , , , , ,
Project Euler 231 Solution

Project Euler 231: The prime factorisation of binomial coefficients

Problem Description

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.

Analysis

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:

There are ⌊1000/5⌋ = 200 factors of 5, each contributing at least a 5 in the prime factorization of 1000!. But hang on, there are also factors of 52 = 25 each of which contributes an extra 5. There are ⌊1000/52⌋ = 40 such factors. Similarly, each factor of 53 = 125 contributes eight more 5s, and each factor of 54 = 625 contributes one more 5. We don’t need to worry about 55 as there are no factors of 55 between 1 and 1000. Thus our answer is:
\lfloor\frac{1000}{5}\rfloor+\lfloor\frac{1000}{5^2}\rfloor+\lfloor\frac{1000}{5^3}\rfloor+\lfloor\frac{1000}{5^4}\rfloor=200+40+8+1=249~.

More generally:

\textit {The exponent of prime p in n!} \: \lfloor\frac{n}{p}\rfloor + \lfloor\frac{n}{p^2}\rfloor + \ldots = \sum\limits_{j=1}^\infty \lfloor\frac{n}{p^j}\rfloor~.

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:

\textit {The exponent of prime p in }\binom {n} {r}\textit { is }\sum\limits_{j=1}^\infty \left(\lfloor\frac{n}{p^j}\rfloor-\lfloor\frac{r}{p^j}\rfloor-\lfloor\frac{n-r}{p^j}\rfloor\right)~.

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 Solution

Runs < 1.9 seconds in Python 2.7.

download arrowUse this link to get the Project Euler 231 Solution Python 2.7 source.

Afterthoughts


    
No afterthoughts yet.



Project Euler 231 Solution last updated 

									
					

				

									                
    








Discussion





					
			
No comments yet.


		










Post a comment




	










	

		
		
	


	

		
		
	


	

		
		
	






	

		
		
	

	






	

		
		

	
	














                			
            	
            

            
            
            
                            

										              
					
Project Euler Level 24