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.

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

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

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:
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

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

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)
```