Project euler problem in python (problem 53)

Question

So I'm learning python so I'm going through some project euler problems. And I'm not sure if this is a python problem I'm having, or just me being retarded, but I seem to be getting the wrong answer for problem 53. Here's 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(n-r)))

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'm getting 3982 which is apparently the wrong answer. Am I just retarded? Or is something wrong that I'm doing that's specific to python?

Answer 1

range( a, b) does not include b.

Answer 2

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

for x in range(1,101):

Hope that helps. Euler rocks!

Answer 3

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

from math import factorial

def ncr(n,r):
    return (factorial(n)/(factorial(r)*factorial(n-r)))

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 are beginner I use this opportunity, considering project Euler's nature, to give coding alternative, which is self-contained and demonstrates lookup table approach to speed up recursive functions and saving the answers to dictionary and using the len as count.

Hope the 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(n-r)))

bigones= [(x,y) for x in range(1,1+100) for y in range(x) if ncr(x,y) > 1000000 ]

print len(bigones)