Project Euler – Problem # 39 – Solved with Python

Problem:

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p <= 1000, is the number of solutions maximised?

One Possible Solution:

# Python version = 2.7.1
# Platform = win32

import math

def count_occ(L):
    """Count occurrences of items in list L
    and return the Answer"""
    Answer = 0
    for i in L:
        x = L.count(i)
        if x > Answer:
            Answer = i
    return Answer

def main():
    """Main Program"""
    L = []
    for a in range(1, 1000):
        for b in range(1, 1000):
            c = math.sqrt((a ** 2) + (b ** 2))
            p = a + b + c
            if p % 1 == 0 and p <= 1000:
                L.append(p)
            else:
                continue
    Answer = count_occ(L)
    print "Answer = ", Answer
        
if __name__ == '__main__':
    main()
Advertisements

Project Euler – Problem # 38 – Solved with Python

Problem:

Take the number 192 and multiply it by each of 1, 2, and 3:

  • 192 * 1 = 192
  • 192 * 2 = 384
  • 192 * 3 = 576

By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3)

The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, … , n) where n > 1?

One Possible Solution:

# Python version = 2.7.1
# Platform = win32

def find_length(L):
    """Find the length of the items
    in the list L (is it == 9?)"""
    x = 0
    for i in L:
        x = x + len(str(i))
    return x

def ispandigital(L):
    """Is the 9 digit number pandigital"""
    concat = ''
    L1 = []
    for i in L:
        x = str(i)
        concat += x
    for b in concat:
        if b not in L1:
            if b != '0':
                L1.append(b)
            else:
                return "False"
        else:
            return "False"
    return "True", concat
    
def main():
    """Main Program"""
    largest = 0
    for i in range(1, 10000):
        L = []
        for y in range(1, 10):
            x = i * y
            if x not in L:
                L.append(x)
                c = find_length(L)
                if c == 9:
                    k = ispandigital(L)
                    if k[0] == "True":
                        if largest < k[1]:
                            largest = k[1]
                        else:
                            continue
                    else:
                        continue
                elif c > 9:
                    break
                else:
                    continue
            else:
                print "Error Message"
    print "Answer = ", largest
        
if __name__ == '__main__':
    main()

Project Euler – Problem # 37 – Solved with Python

Problem:

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

One Possible Solution:

# Python version = 2.7.1
# Platform = win32

def isprime(n):
    '''check if integer n is a prime'''
    # make sure n is a positive integer
    n = abs(int(n))
    # 0 and 1 are not primes
    if n < 2:
        return False
    # 2 is the only even prime number
    if n == 2:
        return True
    # all other even numbers are not primes
    if not n & 1:
        return False
    # range starts with 3 and only needs to go up the squareroot of n 
    # for all odd numbers
    for x in range(3, int(n ** 0.5) + 1, 2):
        if n % x == 0:
            return False
    return True

def peel_left(i):
    """Remove digits left to right,
    then check for prime number"""
    x = list(str(i))
    for n in range(1, len(x)):
        y = x[n:]
        s = int(''.join(y))
        if isprime(s):
            continue
        else:
            return "False"
    return "True"

def peel_right(i):
    """"Remove digits right to left,
    then check for prime number"""
    x = list(str(i))
    for n in range(1, len(x)):
        y = x[:(-n)]
        s = int(''.join(y))
        if isprime(s):
            continue
        else:
            return "False"
    return "True" 
    
def main():
    """Main Program"""
    L = []
    for i in range(10, 1000000):
        if isprime(i):
            if (peel_left(i) == "True") and (peel_right(i) == "True"):
                L.append(i)
            else:
                continue
        else:
            continue
    print "L = ", L
    print "Answer = ", sum(L)

if __name__ == '__main__':
    main()

Project Euler – Problem # 36 – Solved with Python

Problem:

The decimal number, 585 = 10010010012 (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

One Possible Solution:

# Python version = 2.7.1
# Platform = win32

def binary_rep(i):
    """Take decimal i and convert to binary with
    built in function bin, slice off first two
    characters."""
    x = bin(i)
    y = x[2:]
    return y

def reverse_binary(y):
    """Take binary number y and reverse characters"""
    x = y[::-1]
    return x

def reverse_decimal(i):
    """Take decimal number i and reverse characters"""
    y = str(i)
    d = y[::-1]
    return d

def main():
    """Main Program"""
    L = []
    Answer = 0
    for i in range(1, 1000000):
        x = binary_rep(i)
        y = reverse_binary(x)
        if x == y:
            a = int(reverse_decimal(i))
            if i == a:
                L.append(i)
        else:
            continue
    Answer = sum(L)
    print "Sum = ", Answer
        
if __name__ == '__main__':
    main()

Project Euler – Problem # 35 – Solved with Python

Problem:

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

One Possible Solution:

# Python version = 2.7.1
# Platform = win32

def isprime(n):
    '''check if integer n is a prime'''
    # make sure n is a positive integer
    n = abs(int(n))
    # 0 and 1 are not primes
    if n < 2:
        return False
    # 2 is the only even prime number
    if n == 2:
        return True
    # all other even numbers are not primes
    if not n & 1:
        return False
    # range starts with 3 and only needs to go up the squareroot of n 
    # for all odd numbers
    for x in range(3, int(n ** 0.5) + 1, 2):
        if n % x == 0:
            return False
    return True

def new_rotation(y, n):
    """Checks the rotation of each prime number
    for primes"""
    c = 0
    while n != c:
        j = y[1:]
        r = y[0]
        j.append(r)
        s = ''.join(j)
        c = int(s)
        if isprime(c):
            pass
        else:
            return "False"
        y = list(str(s))
    return "True"

def main():
    """Main Program"""
    L = []
    for n in range(10, 1000000):
        if isprime(n):
            y = list(str(n))
            if new_rotation(y, n) == "True":
                L.append(n)
            else:
                continue
    print "len(L) = ", len(L) + 4
    # add 4 to the total (manually add prime 2, 3, 5, and 7)
    print L
            
if __name__ == '__main__':
    main()

Project Euler – Problem # 34 – Solved with Python

Problem:

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.

One Possible Solution:

# Python version = 2.7.1
# Platform is win32

def factorial(L):
    """Get the factorials"""
    sum_factorial = 0
    for i in L:
        fact = 1
        for j in range(1, (int(i) + 1)):
            fact = fact * j
        sum_factorial = sum_factorial + fact
    return sum_factorial

def main():
    """Main Program"""
    L = []
    LN = []
    for n in range(1, 1000001):
        L = list(str(n))
        x = factorial(L)
        if x == n:
            LN.append(n)
    y = sum(LN)
    print "LN = ", LN
    print "Answer = ", y - 3
    # subract 3 for 1! and 2!

if __name__ == '__main__':
    main()