Project Euler

Python code

These are my attempts at the problems presented.
My mathematics and programming skills are at a basic level
therefore a fair amount of 'Googling' and head scratching is
called for.

I have a son studying software engineering at De Montfort
University and he is an invaluable asset with the Python language.

I also have the challenge of writing this page in reStructuredText.

Copy/paste the helper functions, these are called if required.
# Problem 1

def multiple(num):
    '''(int) -> int
    Find the sum of all the multiples of
    3 or 5 below 1000
    '''
    total = 0

    for i in range(1, num):
        # check for a remainder (modulus)
        if i % 3 == 0 or i % 5 == 0:
            total = total + i
    return total

ans = multiple(1000)
print(ans)

'''------------------------------------------------------------------------------------------'''

# Problem 2

 def fib_even_sum(num):
     first = 0
     second = 1
     result = 0
     total = 0

     while result < num:
          result = first + second

          # Next two lines check and sum even terms

          if (result % 2) == 0 :
             total = total + result

          first = second
          second = result
     return total

 ans = fib_even_sum(4000000)
 print(ans)

'''-------------------------------------------------------------------------------------------'''

# Problem 3
'''The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ? '''

from rogutil import *

def highest_prime_factor(num):
    '''(int) -> int
    reduce the candidate by division using prime
    numbers till it equals the value of the prime number '''

    # Produce 3000 prime numbers then use a generator
    # to pick them one by one'''
    z = 0
    prims = gen_x(3000, gen_primes)
    prim = prims[z]

    while num != prim:
        if num % prim == 0:
            num = num / prim
        else:
            z += 1
            prim = prims[z]

    return prim


ans = highest_prime_factor(600851475143)
print(ans)

'''-----------------------------------------------------------------------------------------'''

# Problem 4
'''A palindromic number reads the same both ways.
The largest palindrome made from the product of
two 2-digit numbers is 9009 = 91 x 99.
'''

def palindrome(num1, num2):
    '''(int, int) -> int
    Return the largest palindrome made from
    the product of two 3-digit numbers'''
    first = num1
    second = num2
    sett = set()

    for x in range(first, 1, -1):
        for y in range(second, 1, -1):
            # start at 999*999 and work down
            str1 = str(x * y)
            if len(str1) == 6:
                firstpart = str1[0:3]
                lastpart = str1[3:6]
                reverse = lastpart[::-1]
                # if palindrome add to set
                if firstpart == reverse:
                    sett.add(str1)
    return max(sett)



ans = palindrome(999, 999)
print(ans)

'''-----------------------------------------------------------------------------------------'''

'''
2520 is the smallest number that can be divided by each of
 the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly
 divisible by all of the numbers from 1 to 20?
'''

def lcm(num):
        prime_list = [2 ,3, 5, 7, 11, 13, 17, 19]

        dict1 = {}

        for y in prime_list:

                # compute factors and place in a dictionary
                # key = factor, value = raised to the power of
                for x in range(1, num + 1):
                        count = 0
                        while x % y == 0:
                                count += 1
                                x = x / y
                                if y not in dict1:
                                        dict1[y] = count
                                if count > dict1[y]:
                                        dict1[y] = count

        # find value of each factor / power combination
        multiplier_list = []
        for x in dict1:
                        multiplier_list.append(x ** dict1[x])

        # multiply the resulting values
        total = 1
        for item in multiplier_list:
                total  = total * item

        return total

#---------------------------------------------------

ans = lcm(20)
print(ans)

'''---------------------------------------------------------------------------------------'''

# Problem 6
'''Created on 26 Jul 2010

@author: rog

The sum of the squares of the first ten natural numbers is,
1^(2) + 2^(2) + ... + 10^(2) = 385

The square of the sum of the first ten natural numbers is,
(1 + 2 + ... + 10)^(2) = 55^(2) = 3025

Hence the difference between the sum of the squares of the
first ten natural numbers and the square of the sum is 3025,
385 + 2640.

Find the difference between the sum of the squares of the first one
hundred natural numbers and the square of the sum.  25164150'''

import time
t = time.time()

def main():

    n = 100

    # 'sum of the squares' equation:  n(n+1)(2n+1)/6
    sumsq = ( n * (n + 1) * (2 * n + 1)) / 6

    # 'square of the sum' equation: (n(n+1)/2)^2
    sqsum = ((n * (n + 1)) / 2) ** 2

    print(sqsum - sumsq)

if __name__ == '__main__':
    main()
    print(time.time() -t)

'''------------------------------------------------------------------------------------------'''

# Problem 7

'''By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13,
we can see that the 6^(th) prime is 13.

What is the 10001^(st) prime number?'''


def main():
    pass


    def gen_primes():
        """ Generate an infinite sequence of prime numbers.
        """
        # Maps composites to primes witnessing their compositeness.
        # This is memory efficient, as the sieve is not "run forward"
        # indefinitely, but only as long as required by the current
        # number being tested.
        #
        D = {}

        # The running integer that's checked for primeness
        q = 2

        while True:
            if q not in D:
                # q is a new prime.
                # Yield it and mark its first multiple that isn't
                # already marked in previous iterations
                #
                yield q
                D[q * q] = [q]
            else:
                # q is composite. D[q] is the list of primes that
                # divide it. Since we've reached q, we no longer
                # need it in the map, but we'll mark the next
                # multiples of its witnesses to prepare for larger
                # numbers
                #
                for p in D[q]:
                    D.setdefault(p + q, []).append(p)
                del D[q]

            q += 1

    ans = gen_primes()

    for x in range(1, 10001, 1):
        (next(ans))

    print(next(ans))


if __name__ == '__main__':
    main()

'''-----------------------------------------------------------------------------------------'''

Problem 8.

'''Find the greatest product of five consecutive digits in the
1000-digit number.'''

import sys
sys.path.append("../")
from rogutil import *
import string
__author__="rog"
__date__ ="$29-Jul-2010 00:24:25$"
numstr = """73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450""".replace("", "")


def main():
    highscore = 0
    # Loop through the string, -5 off the end due to the fact that we
    #will be looking at the next 5 numbers.

    for i in range(len(numstr) - 5):
        # Adjust the start and end values here to change what values you
        # want stripped.
        start = i
        end = i + 5

        # Strip all numbers from start to end, convert them to integers,
        # put the result into a list (array)
        new_list = [int(integral) for integral in list(numstr[start:end])]

        # Multiply all the resulting numbers together from the list (array)
        result = multiplylist(new_list)

        # Set the high score
        if result > highscore:
            highscore = result

    # Print the final result
    print(highscore)

if __name__ == "__main__":
    main()

'''------------------------------------------------------------------------------------------'''

# Problem 9

#! /usr/bin/python

'''A Pythagorean triplet is a set of three natural numbers,
 a < b < c, for which,
a^(2) + b^(2) = c^(2)

For example, 3^(2) + 4^(2) = 9 + 16 = 25 = 5^(2).

There exists exactly one Pythagorean triplet for
 which a + b + c = 1000.
Find the product abc.'''

__author__="rog"
__date__ ="$29-Jul-2010 12:44:04$"

import math

def main():
    result = 0

    while result != 1000:
        # generate two numbers between 1 and 500
        for a in range (1, 500, 1):
            for b in range(1, 500, 1):
                # work out the c of a,b,c
                c = math.sqrt(a ** 2 + b ** 2)
                result = a + b + c

                if result == 1000:
                    print("product = ", a*b*c)
                    exit()

if __name__ == "__main__":
    main()

'''------------------------------------------------------------------------------------------'''

Problem 10.

#! /usr/bin/python

# To change this template, choose Tools | Templates
# and open the template in the editor.

__author__="rog"
__date__ ="$29-Jul-2010 12:44:04$"

'''The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.'''
import time
import random
import sys
sys.path.append("../")
from rogutil import *
tt = time.time()

def main():
    results = []
    for item in gen_primes():
        if item >= 2000000:
            break
        results.append(item)

    print ("Summing...")
    print (sum(results))

if __name__ == "__main__":
    main()
    print(time.time() - tt)

Comments | Gallery