Euler project in Python


Solution to Euler project in Python

Problem 1-10


## For class Helper see below
helperObj = Helper()


def problem1(self):
'''
    Add all the natural numbers below one thousand
    that are multiples of 3 or 5.
'''
    numbers = range(0,1000)
    return reduce(lambda x,y: x+y, filter(lambda(x):x%3==0 or x%5==0, numbers))

def problem2(self):
'''
    By considering the terms in the Fibonacci sequence whose values do
    not exceed four million, find the sum of the even-valued terms.
'''
    index = 1
    fibNumbers = []
    while(True):
        value = helperObj.fib(index)
        if value < 4000000:
            fibNumbers.append(helperObj.fib(index))
            index+=1
        else:
            break
    return reduce(lambda x,y: x+y, filter(lambda(x):x%2==0, fibNumbers))

def problem3(self):
'''
    What is the largest prime factor of the number 600851475143 ?
'''
    factors = helperObj.factors(600851475143)
    index = -1
    while(True):
        if helperObj.isPrime(factors[index]) == 0:
            return factors[index]
        else:
            index -= 1
            continue

def problem4(self):
'''
    Find the largest palindrome made from the product
    of two 3-digit numbers.
'''
    largestNumber = 999
    max = 0
    while(largestNumber > 300):
        counter = 999
    while(counter > 300):
        if helperObj.isPalindrome(largestNumber * counter):
            p = largestNumber*counter
            if p > max:
                max = p
            counter = counter - 1

        largestNumber -= 1
    return max

def problem5(self):
'''
    What is the smallest positive number that is evenly divisible
    by all of the numbers from 1 to 20?
'''
    return reduce(helperObj.lcm, range(1, 20+1))

def problem6(self):
'''
    Find the difference between the sum of the squares of the first
    one hundred natural numbers and the square of the sum.
'''
    return helperObj.sumOfSquares(100) - helperObj.sumOfNumbers(100) ** 2

def problem7(self):
'''
    What is the 10001st prime number?
'''
    index = 0
    num = 2
    while(index < 10001):
        if helperObj.isPrime(num) == 0:
            index += 1
        num += 1
    return num-1

def problem8(self):
'''
    Find the greatest product of five consecutive digits
    in the 1000-digit number.
'''
    num = "73167176531330624919225119674426574742355349194934" + \
          "96983520312774506326239578318016984801869478851843" + \
          "85861560789112949495459501737958331952853208805511" + \
          "12540698747158523863050715693290963295227443043557" + \
          "66896648950445244523161731856403098711121722383113" + \
          "62229893423380308135336276614282806444486645238749" + \
          "30358907296290491560440772390713810515859307960866" + \
          "70172427121883998797908792274921901699720888093776" + \
          "65727333001053367881220235421809751254540594752243" + \
          "52584907711670556013604839586446706324415722155397" + \
          "53697817977846174064955149290862569321978468622482" + \
          "83972241375657056057490261407972968652414535100474" + \
          "82166370484403199890008895243450658541227588666881" + \
          "16427171479924442928230863465674813919123162824586" + \
          "17866458359124566529476545682848912883142607690042" + \
          "24219022671055626321111109370544217506941658960408" + \
          "07198403850962455444362981230987879927244284909188" + \
          "84580156166097919133875499200524063689912560717606" + \
          "05886116467109405077541002256983155200055935729725" + \
          "71636269561882670428252483600823257530420752963450"
    max = 0
    for index in range(0,995):
        product = reduce(lambda x,y: int(x)*int(y), list(num[index:index+5]))
        if product > max:
            max = product
    return max

def problem9(self):
'''
    There exists exactly one Pythagorean triplet for which a + b + c = 1000.
    Find the product abc.
'''
    for a in range(1,1001):
        for b in range(1,1001):
            c = 1000 - (a+b)
            if helperObj.isPythagorean(a,b,c) == 0:
                return a*b*c

def problem10(self):
'''
    Find the sum of all the primes below two million
'''
        sum = 0
        for x in xrange(3,2000000+1, +2):
            if helperObj.isPrime(x) == 0:
                sum += x
        return sum + 2

listOfProblems = [1,3,5]
for i in listOfProblems:
    print eval("problem" + str(i) + "()")

class Helper:
'''
    Helper class used in solutions
'''
    def fib(self, number):
        if number==1:
            return 1
        if number==2:
            return 2
        return self.fib(number-2) + self.fib(number-1)

    def factors(self, number):
        list = []
        for num in range(2,int(number**0.5)):
            if number%num == 0:
                list.append(num)
            return list

    def isPrime(self, number):
        for num in range(2,number-1):
            if number%num == 0:
                return -1
            else:
                continue
        return 0

    def isPalindrome(self,number):
        number = str(number)
        return number == number[::-1]

    def sumOfNumbers(self, number):
        return (number * (number+1))/2

    def sumOfSquares(self,number):
        return (number * (number+1) * (2*number+1))/6

    def isPythagorean(self, num1, num2, num3):
        if num3**2 == num2**2 + num1**2:
            return 0
        else:
            return -1

    def gcd(self, a, b):
        return (self.gcd(b,a%b) if b else a)

    def lcm(self, a, b):
        return (a*b) / self.gcd(a,b)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s