Project Euler – Problem # 33 – Solved with Python

Problem:

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.

One Possible Solution:

# Python version 2.7.1
# Platform is win32

from __future__ import division

def find_fractions():
    """Find the curious fractions"""
    num_list = []
    den_list = []
    for n in range(10, 100):
        for d in range(10, 100):
            if d > n:
                x = n / d
                ln = list(str(n))
                ld = list(str(d))
                if (ln[0] == ld[1]) and (ln[0] != '0'):
                    if ld[0] != '0':
                        if (int(ln[1]) / int(ld[0])) == x:
                            print "n/d =", n, d
                            num_list.append(n)
                            den_list.append(d)
                        else:
                            continue
                elif (ln[1] == ld[0]) and (ln[1] != '0'):
                    if ld[1] != '0':
                        if (int(ln[0]) / int(ld[1])) == x:
                            print "n/d =", n, d
                            num_list.append(n)
                            den_list.append(d)
                    else:
                        continue
                else:
                    continue
    return num_list, den_list

def find_product(num_list, den_list):
    """Find the product of these four fractions,
    then divide the denominator by the numerator"""
    num_prod = 1
    den_prod = 1
    for i in num_list:
        num_prod = num_prod * i
    for j in den_list:
        den_prod = den_prod * j
    answer = den_prod / num_prod
    return answer
    
def main():
    """Main Program"""
    y = find_fractions()
    x = find_product(y[0], y[1])
    print "Answer = ", x
        
if __name__ == '__main__':
    main()
Advertisements

Project Euler – Problem # 32 – Solved with Python

Problem:

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 * 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

One Possible Solution:

def twos():
    """Return a set of two digit numbers that
    do not repeat or have a zero in them"""
    twos = []
    for i in range(10, 100):
        two_list = list(str(i))
        if (two_list[0] != '0' and two_list[1] != '0') \
           and (two_list[0] != two_list[1]):
            twos.append(i)
    return set(twos)

def threes():
    """Return a set of three digit numbers that
    do not repeat or have a zero in them"""
    threes = []
    for i in range(100, 1000):
        three_list = list(str(i))
        if ((three_list[0] != three_list[1]) and (three_list[0] != \
            three_list[2]) and (three_list[1] != three_list[2]))and \
           (three_list[0] != '0' and three_list[1] != '0' \
            and three_list[2] != '0'):
            threes.append(i)
    return set(threes)

def fours():
    """Return a set of four digit numbers that
    do not repeat or have a zero in them"""
    fours = []
    for i in range(1000, 10000):
        four_list = list(str(i))
        if ((four_list[0] != four_list[1]) and (four_list[0] \
            != four_list[2]) and (four_list[0] != four_list[3]) \
            and (four_list[1] != four_list[2]) and \
            (four_list[1] != four_list[3]) and (four_list[2] \
            != four_list[3])) and (four_list[0] != '0' and \
            four_list[1] != '0' and four_list[2] != '0' and \
            four_list[3] != '0'):
            fours.append(i)
    return set(fours)

def is_pandigital(is_pan):
    """Checks if multiplicand, multiplier,
    and the product are pandigital"""
    new = []
    for x in is_pan:
        if x not in new:
            new.append(x)
        else:
            return "False"
            
def pandigital(x, y, z):
    """Multiply the twos and threes together
    and the ones and fours to check for
    pandigitallity"""
    pospan = []
    # check the two * threes
    for i in x:
        for j in y:
            ij = i * j
            i1 = list(str(i))
            j1 = list(str(j))
            product = list(str(ij))
            if len(product) == 4:
                if product[0] == '0' or product[1] == '0' \
                   or product[2] == '0' or product[3] == '0':
                    continue
                else:
                    is_pan = str(i) + str(j) + str(ij)
                    if is_pandigital(is_pan) != "False":
                        print "is_pan =", is_pan
                        pospan.append(ij)
            elif len(product) == 5:
                if product[0] == '0' or product[1] == '0' \
                   or product[2] == '0' or product[3] == '0' \
                   or product[4] == '0':
                    continue
                else:
                    is_pan = str(i) + str(j) + str(ij)
                    if is_pandigital(is_pan) != "False":
                        print "is_pan =", is_pan
                        pospan.append(ij)
            else:
                print "Error Message"
    # check the ones * fours
    for g in range(1, 10):
        for h in z:
            gh = g * h
            g1 = list(str(g))
            h1 = list(str(h))
            product = list(str(gh))
            if len(product) == 4:
                if product[0] == '0' or product[1] == '0' \
                   or product[2] == '0' or product[3] == '0':
                    continue
                else:
                    is_pan = str(g) + str(h) + str(gh)
                    if is_pandigital(is_pan) != "False":
                        print "is_pan =", is_pan
                        pospan.append(gh)
            elif len(product) == 5:
                if product[0] == '0' or product[1] == '0' \
                   or product[2] == '0' or product[3] == '0' \
                   or product[4] == '0':
                    continue
                else:
                    is_pan = str(g) + str(h) + str(gh)
                    if is_pandigital(is_pan) != "False":
                        print "is_pan =", is_pan
                        pospan.append(gh)
    return set(pospan)
    
def main():
    """Main Program"""
    x = twos()
    y = threes()
    z = fours()
    xy = pandigital(x, y, z)
    print xy
    print sum(xy)

if __name__ == '__main__':
    main()

Project Euler – Problem 30 – Solved with Python

Problem:

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.

One Possible Solution:

def split_number(x):
    """Split number x into a list yy of individual numbers"""
    yy = list(str(x))
    return yy

def sum_of_powers(x, y, length_y):
    """Find the sum of the individual numbers raised to the 5th power
    and determine if they are equal to x"""
    x1, x2, x3, x4, x5, x6 = 0, 0, 0, 0, 0, 0
    if length_y == 1:
        x1 = int(y[0]) ** 5
        if x1 == x:
            return "True"
        else:
            return "False"
    elif length_y == 2:
        x1 = int(y[0]) ** 5
        x2 = int(y[1]) ** 5
        if x1 + x2 == x:
            return "True"
        else:
            return "False"
    elif length_y == 3:
        x1 = int(y[0]) ** 5
        x2 = int(y[1]) ** 5
        x3 = int(y[2]) ** 5
        if x1 + x2 + x3 == x:
            return "True"
        else:
            return "False"
    elif length_y == 4:
        x1 = int(y[0]) ** 5
        x2 = int(y[1]) ** 5
        x3 = int(y[2]) ** 5
        x4 = int(y[3]) ** 5
        if x1 + x2 + x3 + x4 == x:
            return "True"
        else:
            return "False"
    elif length_y == 5:
        x1 = int(y[0]) ** 5
        x2 = int(y[1]) ** 5
        x3 = int(y[2]) ** 5
        x4 = int(y[3]) ** 5
        x5 = int(y[4]) ** 5
        if x1 + x2 + x3 + x4 + x5 == x:
            return "True"
        else:
            return "False"
    elif length_y == 6:
        x1 = int(y[0]) ** 5
        x2 = int(y[1]) ** 5
        x3 = int(y[2]) ** 5
        x4 = int(y[3]) ** 5
        x5 = int(y[4]) ** 5
        x6 = int(y[5]) ** 5
        if x1 + x2 + x3 + x4 + x5 + x6 == x:
            return "True"
        else:
            return "False"
    else:
        print "Error Message"
        
def main():
    """Main Program"""
    L = []
    for x in range(2, 1000000):
        y = split_number(x)
        length_y = len(y)
        xy = sum_of_powers(x, y, length_y)
        if xy == 'False':
            pass
        else:
            L.append(x)
    print "L = ", L
    print "Sum of list L = ", sum(L)

if __name__ == '__main__':
    main()

Project Euler – Problem 29 – Solved with Python

Problem:

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?

**********

Using a list L for each term, we can then find the set of that list which will eliminate duplicates. Then find the length of that set with len

One Possible Soultion:

def get_terms():
    """Find the terms and put them in a list L,
    return the set of list L"""
    L = []
    for a in range(2, 101):
        for b in range(2, 101):
            term = (a ** b)
            L.append(term)
    return set(L)

def main():
    """Main program"""
    x = get_terms()
    print "Number of Terms = ", len(x)
    
if __name__ == '__main__':
    main()

Project Euler – Problem # 28 – Solved with Python

Problem:

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

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?

One Possible Solution:

def add_diagonal(passed):
    """Calculate sum of individual diagonal"""
    summer = 1
    adder = 0
    tallyer = 0
    for i in range(0, 500):
        if i < 1:
            adder = passed
        else:
            adder = adder + 8
        summer = summer + adder
        tallyer = tallyer + summer
    return tallyer
        
def main():
    """Main program:
    Finds sum of each diagonal
    and adds 1 for the center"""
    lr = add_diagonal(2)
    print "lr = ", lr
    ll = add_diagonal(4)
    print "ll = ", ll
    ul = add_diagonal(6)
    print "ul = ", ul
    ur = add_diagonal(8)
    print "ur = ", ur
    tally = lr + ll + ul + ur + 1
    print "tally = ", tally

if __name__ == '__main__':
    main()

Project Euler – Problem # 26 – Solved with Python

Problem:

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.

One Possible Solution:

from decimal import *

def find_fraction(i):
    """Finds the fraction of x to the .prec place"""
    getcontext().prec = 1500
    x = Decimal(1) / Decimal(i)
    #print "i = %s x = %s" % (i, x) 
    return x

def find_period(x1):
    """Find period for repeating"""
    L = (str(x1))
    length = len(L)
    l_one, l_two, l_three = 0, 0, 0
    #print "L = ", L
    if L[2:3] != '0':
        index = L[2:6]
        l_one = 1
    elif L[2:3] == '0' and L[3:4] != '0':
        index = L[3:7]
        l_two = 1
    elif L[2:3] == '0' and L[3:4] == '0':
        index = L[4:8]
        l_three = 1
    else:
        print "There may be an error in your program"
    max_period = 0
    for v in range(3, length):
        if l_one == 1:
            indexi = L[v:(v + 4)]
        elif l_two == 1:
            indexi = L[(v + 1):(v + 5)]
        elif l_three == 1:
            indexi = L[(v + 2):(v + 6)]
        else:
            print "There has been an error"
        if index == indexi:
            #print "index = ", index
            #print "indexi = ", indexi
            #print "They are equal"
            #print "L[i] = ", (v-2)
            max_period = v
            break
    return max_period

def main():
    """Main program"""
    place_holder = 0
    for i in range(1, 1001):
        x1 = find_fraction(i)
        y1 = find_period(x1)
        #print "max_period = ", y1
        if y1 > place_holder:
            place_holder = y1
            max_number = i
    print "max_number = ", max_number

if __name__ == '__main__':
    main()