# Project Euler

```
# Problem 23.
#!/usr/bin/env python
'''A perfect number is a number for which the sum of its
proper divisors is exactly equal to the number.
For example, the sum of the proper divisors of
28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that
28 is a perfect number.
A number n is called deficient if the sum of its proper
divisors is less than n and it is called abundant if this
sum exceeds n.
As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16,
the smallest number that can be written as the sum of two
abundant numbers is 24. By mathematical analysis, it can
be shown that all integers greater than 28123 can be written
as the sum of two abundant numbers. However, this upper limit
cannot be reduced any further by analysis even though it is
known that the greatest number that cannot be expressed
as the sum of two abundant numbers is less than this limit.
Find the sum of all the positive integers which CANNOT
be written as the sum of two abundant numbers.'''
import math
import sys
sys.path.append("../")
from rogutil import *
import time
tt = time.time()
def main():
pass
result = 0
count = 0
increm = 1
'''generator for trinum'''
v = (x for x in range(28123, 0, -1))
trinum = next(v)
#trinum = 12
kounter = 0 # errr... counter
prim = 0 # The Prime Number for division of the Triangle number
i, z = 0, 0
prims = gen_x(10000, gen_primes) # prime number genny
prim = prims[z] # For incrementing the Prime Number
div_lst = [] #Divisor list
power_lst = [] #Prime number (power) list
sum_lst = [] #Sum of the divisors
sums_divslst = []
numbers_lst = []
dd = trinum
numbers_lst.append(dd) #keep list of numders for comparison later
odd_abundant =[]
even_abundant = []
abundant = []
paired_abundant = set()
filtered = []
#------------------Calculate divisors-----------------------
while dd > 3:
if not trinum % prim == 0: # Is there a modulus, if so, increase the Prime Number
if count > 0: #Divisor counter
kounter = count + 1
power_lst.append(kounter)
count = 0
z += 1
prim = prims[z]
continue
trinum = trinum / prim
if not prim in div_lst:
div_lst.append(prim)
count += 1
if trinum == 1: #Divide down to 1, test the amount of divisors and
kounter = count + 1 # if too low, increase the Triangle Number
power_lst.append(kounter)
#----------Sum of divisors formula-----------------
a = len(div_lst)
b = a - 1 #starts at 0
ans = 1
#print("divlist,powerlist = ",div_lst,power_lst)
'''Sum formula'''
for i in range(b, -1, -1):
c = ((div_lst[i] ** power_lst[i]) - 1) /(div_lst[i] - 1)
sum_lst.append(c)
'''Product of the sum list'''
product = 1
for i in sum_lst:
product *= i
product = product - dd
#-----------gathering list of abundant numbers---------------------
if product > dd :
abundant.append(dd)
#-----------------------------------------------------------------
count = 0
z = 0
prim = prims[z]
increm +=1
trinum = next(v)
dd = trinum
numbers_lst.append(dd)
sum_lst = []
div_lst = []
power_lst = []
continue
if trinum == 2:
break
#---------End of While loop-------------------------
#import pdb; pdb.set_trace()
#----------Gather paired abundants------------------
sums =set() #Using a set for filtering later
for item1 in abundant:
for item2 in abundant:
if item1+item2<28124:
sums.add(item1+item2)
#------filter non-paired_abundant integers----------
filtered = 0
for j in range(1,28124):
if j not in sums:
filtered += j
print (filtered)
#--------------------------------------------------
if __name__ == '__main__':
main()
print(time.time() - tt)
```

```
# Problem 24.
''''A permutation is an ordered arrangement of objects. For example,
3124 is one possible permutation of the digits 1, 2, 3 and 4.
If all of the permutations are listed numerically or alphabetically,
we call it lexicographic order.
The lexicographic permutations of 0, 1 and 2 are:
012 021 102 120 201 210
What is the millionth lexicographic permutation of
the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?'''
# a simple recursive permutation function
# the number of permutations of a sequence of n
# unique items is given by n! (n factorial)
# more details at http://mathworld.wolfram.com/Permutation.html
import time
tt = time.time()
def main():
def permutate(seq):
"""permutate a sequence and return a list of the permutations"""
if not seq:
return [seq] # is an empty sequence
else:
temp = []
for k in range(len(seq)):
part = seq[:k] + seq[k+1:]
for m in permutate(part):
temp.append(seq[k:k+1] + m)
return temp
# permutate a list
list1 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
list2 = []
list3 = []
for list2 in permutate(list1):
list3.append(list2)
print(list3[999999])
if __name__ == "__main__":
main()
print(time.time() - tt)
```

```
# Problem 25.
'''The Fibonacci sequence is defined by the recurrence relation:
F_(n) = F_(n-1) + F_(n-2), where F_(1) = 1 and F_(2) = 1.
Hence the first 12 terms will be:
F_(1) = 1
F_(2) = 1
F_(3) = 2
F_(4) = 3
F_(5) = 5
F_(6) = 8
F_(7) = 13
F_(8) = 21
F_(9) = 34
F_(10) = 55
F_(11) = 89
F_(12) = 144
The 12th term, F_(12), is the first term to contain three digits.
What is the first term in the Fibonacci sequence to contain
1000 digits?'''
kount = 1
term1 = 0
term2 = 1
term3 = 0
while True:
''' Using Fn = Fn-1 + Fn-2'''
term3 = term1 + term2
term1 = term2
term2 = term3
kount += 1
if len(str(term3)) == 1000:
break
print("First term to contain 1000 digits: ",kount)
```

```
Problem 26.
'''A unit fraction contains 1 in the numerator.
The decimal representation of the unit fractions with
denominators 2 to 10 are given:
^(1)/_(2) = 0.5
^(1)/_(3) = 0.(3)
^(1)/_(4) = 0.25
^(1)/_(5) = 0.2
^(1)/_(6) = 0.1(6)
^(1)/_(7) = 0.(142857)
^(1)/_(8) = 0.125
^(1)/_(9) = 0.(1)
^(1)/_(10) = 0.1
Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle.
It can be seen that ^(1)/_(7) has a 6-digit recurring cycle.
Find the value of d < 1000 for which ^(1)/_(d) contains the
longest recurring cycle in its decimal fraction part'''
import time
tt = time.time()
from decimal import *
num = 0
denom = 4
'''index of list(lst)'''
w = 5
x = 5
y = 8
''' I'll give it 3000 digits! '''
getcontext().prec = 3000
for n in range (1, 999, 1):
w,x,y = 5,5,8
lst = Decimal(1) / Decimal(n)
lst = str(lst)
''' Now checking for a recurring cycle '''
while n < 1000:
'''if too short, break'''
if y >= len(lst) - 2:
break
'''start checking, left to right'''
if lst[2:x] == lst[w:y]:
chk = len(lst[2:x])
if chk > num:
num = chk
denom = n
break
else:
w += 1
x += 1
y += 2
print(time.time() - tt)
print("denominator is ",denom," with length ",num,".")
```

```
# Problem 27.
#!/usr/bin/env python
'''
Euler published the remarkable quadratic formula:
n^2 + n + 41
It turns out that the formula will produce 40 primes
for the consecutive values n = 0 to 39. However, when
n = 40, 40^(2) + 40 + 41 = 40(40 + 1) + 41 is divisible
by 41, and certainly when n = 41, 41^2 + 41 + 41 is clearly
divisible by 41.
Using computers, the incredible formula n^2 + 79n + 1601
was discovered, which produces 80 primes for the consecutive
values n = 0 to 79.
The product of the coefficients, -79 and 1601, is -126479.
Considering quadratics of the form:
n^2 + an + b, where |a| < 1000 and |b| < 1000
where |n| is the modulus/absolute value of n
e.g. |11| = 11 and |-4| = 4
Find the product of the coefficients, a and b, for the
quadratic expression that produces the maximum number
of primes for consecutive values of n, starting with n = 0.
'''
from rogutil import *
import time
t = time.time()
def main():
pass
kount = 0
co_effs = ""
count_tally = 0
for a in range(-999, 999, 2):
for x in range(1, 1000, 1):
if isprime(x):
b = x
kount = 0
n = 0
while True:
ans = (n**2) + (a *n) + b
if isprime(ans):
kount += 1
n += 1
if kount > count_tally:
count_tally = kount
co_effs = a,b
else:
break
print("Count: ",count_tally," Product: ",co_effs[0] * co_effs[1])
print(time.time() - t)
if __name__ == '__main__':
main()
```

```
# Problem 28
'''Starting with the number 1 and moving to the right in a
clockwise direction a 5 by 5 spiral is formed as follows:
21 22 23 24 25
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13
It can be verified that the sum of the numbers on the
diagonals is 101.
What is the sum of the numbers on the diagonals in a
1001 by 1001 spiral formed in the same way? '''
# After trying to work out geometric progressions of each arm,
# it was noted that one arm was squares only.
# Using that fact a formula was put together for each arm
# eg x^2 - (x - 1) then the four combined to give the result
# below. The centre piece, 1, is then added.
ans = 0
for x in range(3, 1002, 2):
ans1 = (4 * (x ** 2)) - (6 * (x - 1))
ans = ans1 + ans
print(ans + 1)
```

```
# Problem 29.
'''
Consider all integer combinations of a^(b) for 2 = a = 5
and 2 = b = 5:
2^(2)=4, 2^(3)=8, 2^(4)=16, 2^(5)=32
3^(2)=9, 3^(3)=27, 3^(4)=81, 3^(5)=243
4^(2)=16, 4^(3)=64, 4^(4)=256, 4^(5)=1024
5^(2)=25, 5^(3)=125, 5^(4)=625, 5^(5)=3125
If they are then placed in numerical order, with any
repeats removed, we get the following sequence of 15
distinct terms:
4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
How many distinct terms are in the sequence generated
by a^(b) for 2 = a = 100 and 2 = b = 100? '''
lst = set()
for a in range(2, 101, 1):
for b in range(2, 101, 1):
ans = a ** b
lst.add(ans)
print(len(lst))
```

```
# Problem 30.
''' Surprisingly there are only three numbers that can be
written as the sum of fourth powers of their digits:
1634 = 1^(4) + 6^(4) + 3^(4) + 4^(4)
8208 = 8^(4) + 2^(4) + 0^(4) + 8^(4)
9474 = 9^(4) + 4^(4) + 7^(4) + 4^(4)
As 1 = 1^(4) is not a sum it is not included.
The sum of these numbers is 1634 + 8208 + 9474 = 19316.
Find the sum of all the numbers that can be written as
the sum of fifth powers of their digits.'''
lst2 = []
lst3 = []
lst4 = []
for x in range(25, 270000, 1):
'''list the first number to be tested'''
lst2 = []
lst3 = []
lst = str(x)
for g in lst:
'''split and convert to integer'''
lst2.append(int(g))
for lst2_index in range(0, len(lst2), 1):
'''index for lst2'''
r = lst2[lst2_index]
r = r ** 5
lst3.append(r)
if sum(lst3) == x:
lst4.append(x)
print("****",lst4, " Number = ",x)
print("List: ",lst4," Sum of List: ",sum(lst4))
exit()
```

```
# Problem 31.
#!/usr/bin/env python
'''In England the currency is made up of pound, £,
and pence, p, and there are eight coins in general circulation:
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
It is possible to make £2 in the following way:
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
How many different ways can £2 be made using any
number of coins?'''
import time
timer = time.time()
def main():
pass
a = 100
b = 50
c = 20
d = 10
e = 5
f = 2
g = 1
num = 1
for r in range(0, 3, 1):
if r == 2:
num += 1
print(num)
print(time.time() - timer)
exit()
for s in range(0, 5, 1):
for t in range(0, 11, 1):
for u in range(0, 21, 1):
for v in range(0, 41, 1):
for w in range(0, 101, 1):
for x in range(0, 201, 1):
pounds = r * a
fifties = s * b
twenties = t * c
tens = u * d
fives = v * e
twos = w * f
ones = x * g
result = pounds + fifties + twenties \
+ tens + fives + twos + ones
if result == 200:
num += 1
break
elif result > 200:
break
if __name__ == '__main__':
main()
```

```
#Problem 32
import time
tt = time.time()
the_set = set()
result = ""
for i in range(50):
for j in range(2000):
product = i * j
result = str(i) + str(j) + str(product)
if "0" in result:
continue
if len(result) == len(set(result)) == 9:
the_set.add(int(product))
else:
continue
print(i,j)
print(sum(the_set))
print(time.time() - tt)
```

```
#Problem 33
#!/usr/bin/env python
'''
The fraction 49/98 is a curious fraction, as an
inexperienced mathematician in attempting to simplify it
may incorrectly believe that 49/98 = 4/8, which is correct,
is obtained by cancelling the 9s.
We shall consider fractions like, 30/50 = 3/5, to be
trivial examples.
There are exactly four non-trivial examples of this type
of fraction, less than one in value, and containing two
digits in the numerator and denominator.
If the product of these four fractions is given in its
lowest common terms, find the value of the denominator.
'''
import sys
sys.path.append("../")
from rogutil import *
#import pdb; pdb.set_trace()
def main():
x = 0
y = 0
numer_mult = 1
denom_mult = 1
count = 0
for a in range(1, 10, 1):
for b in range(1, 10, 1):
for c in range(1, 10, 1):
#print(a,b,c)
x = a * 10 + b
y = b * 10 + c
if x/y == a/c and x != y:
count += 1
numer_mult *= x
denom_mult *= y
print(a,b,c)
ans = denom_mult / numer_mult
print("Ans ",ans )
if __name__ == '__main__':
#pdb.runcall(main)
main()
```

```
#Problem 34.
'''
145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.
Find the sum of all numbers which are equal to the sum of
the factorial of their digits.
Note: as 1! = 1 and 2! = 2 are not sums they are not included.
'''
import time
st = time.time()
ref_list = [1]
total = 1
answer_store = []
numb_str = ()
total2 = 0
answer = 0
#------------------------------
#populate factorials
for i in range(1,10,1):
total *= i
ref_list.append(total)
#------------------------------
for n in range (10,90000,1): # number to be tested
total2 = 0
num_str = str(n) # convert to string, put in a list
for c in num_str: # iterate thru the list
z = int(c) # convert to integer
total2 += (ref_list[z]) # sum together
if total2 == n: # Are they the same?
answer_store.append(total2) #if so, in here...
#-----------------------------------------------
for items in answer_store:
answer += items
#-----------------------------------------------
print("Answer = ", answer)
print(time.time() - st)
```