Reputation: 48577

Project euler in python (#53)

I'm learning python, so I'm going through some Project Euler problems. I'm not sure if this is a python problem I'm having, or just me missing something, 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 doing something wrong that's specific to python?

Upvotes: 9

Answers (5)

Peter B.

Reputation: 391

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;

Upvotes: 1

Tony Veijalainen

Reputation: 5555

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)

Upvotes: 1

thevilledev

Reputation: 2377

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

Upvotes: 2