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)

Comments | Gallery