Euler project in python (# 53)

Question

So, I am learning python, so I am looking at some problems with the project euler. And I'm not sure if this is the python problem I am facing, or just being delayed, but it seems I am getting the wrong answer to problem 53. Here is a link to the problem http://projecteuler.net/index.php?section= problems & id = 53

and this is my code:

from math import factorial def ncr(n,r): return (factorial(n)/(factorial(r)*factorial(nr))) i = 0 for x in range(1,100): for y in range(0,x): if(ncr(x,y) > 1000000): i=i+1 print i 

I get 3982, which seems to be the wrong answer. Is there something wrong that I am doing this for python?

Answer 1

range( a, b) does not include b .

Answer 2

I think your code is correct, however you should iterate over x to 100 inclusive, so you should use

 for x in range(1,101): 

Hope this helps. Euler Rocks!

Answer 3

Note that n is greater than or equal to 1 AND is less than or equal to 100. Currently, your n goes from 1 to 99. You can use xrange .

 from math import factorial def ncr(n,r): return (factorial(n)/(factorial(r)*factorial(nr))) i = 0 for x in range(1,101): for y in range(1,x+1): if(ncr(x,y) > 1000000): i=i+1 print i 

Answer 4

If you're new, I take this opportunity by looking at the Euler nature project to give an encoding alternative that is self-contained and demonstrates a matching table approach to speed up recursive functions and save dictionary responses and use len as a counter.

I hope 4075 is the right answer!

 from __future__ import division factorials={} def factorial(n): """ factorial from lookup table ready or generate it to there """ if n not in factorials: factorials[n]=1 if n==0 else n*factorial(n-1) return factorials[n] def ncr(n,r): return (factorial(n)/(factorial(r)*factorial(nr))) bigones= [(x,y) for x in range(1,1+100) for y in range(x) if ncr(x,y) > 1000000 ] print len(bigones) 

Answer 5

Given the input of the problem : “Only when n = 23, the value exceeds one million”, you can make a range for the external from 23 to 101:

 for x in range(23,101): ... 

In addition, n over k can be calculated faster without generating three factorials:

 def noverk(n,k): noverk=1 if 2*k < n: k=nk; for i in range(1,n-k+1): noverk *= (i+k) noverk /= i return noverk;