Project euler in python (#53)

So I'm learning python so I'm going through some project euler problems. 开发者_Python百科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. Is something wrong that I'm doing that's specific to python?

range( a, b) does not include b.

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!

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

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)

Considering the input from the problem specification: "It is not until n = 23, that a value exceeds one-million", you can make the range for the outer from 23 to 101:

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

Furthermore, n over k can be calculated faster without generating the three factorials:

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