Project Euler – Problem # 45 – Solved with Python

Problem:

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

  • Triangle Tn=n(n + 1)/2      1, 3, 6, 10, 15, …
  • Pentagonal Pn=n(3 * n – 1)/2      1, 5, 12, 22, 35, …
  • Hexagonal Hn=n(2 * n – 1)      1, 6, 15, 28, 45, …

It can be verified that T285 = P165 = H143 = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

One Possible Solution:

# Python version = 2.7.1
# Platform = win32

def main():
    """Main Program"""
    T = set((n * (n + 1) / 2) for n in range(2, 180000))
    P = set((n * ((3 * n) - 1) / 2) for n in range(2, 180000))
    H = set((n * ((2 * n) - 1)) for n in range(2, 180000))
    for i in T:
        if i in P and i in H:
            print "You found one"
            print i
        else:
            continue

if __name__ == '__main__':
    main()
Advertisements

Project Euler – Problem # 44 – Solved with Python

Problem:

Pentagonal numbers are generated by the formula, Pn=n(3 * n – 1)/2. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, …

It can be seen that P4 + P7 = 22 + 70 = 92 = P8. However, their difference, 70 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, Pj and Pk, for which their sum and difference is pentagonal and D = |Pk Pj| is minimised; what is the value of D?

One Possible Soultion:

# Python version = 2.7.1
# Platform = win32

from __future__ import division
import math

def main():
    """Main Program"""
    p = set(n * ((3 * n) - 1) / 2 for n in range(2, 4000))
    for i in p:
        for j in p:
            if i + j in p and j - i in p:
                x = i - j
            else:
                continue
    print "Answer = ", math.fabs(x)
    """Answer is the first vaule of x, as the
    pentagonal numbers get larger, they get farther
    apart, makes some sense..."""

if __name__ == '__main__':
    main()

Project Euler – Problem # 43 – Solved with Python

Problem:

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:

  • d2d3d4=406 is divisible by 2
  • d3d4d5=063 is divisible by 3
  • d4d5d6=635 is divisible by 5
  • d5d6d7=357 is divisible by 7
  • d6d7d8=572 is divisible by 11
  • d7d8d9=728 is divisible by 13
  • d8d9d10=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

One Possible Solution:

# Python version = 2.7.1
# Platform = win32
"""run_time was 36 seconds"""

import itertools
import time

def get_divisibles(s):
    """Get the 7 divisibles"""
    x = list(str(s))
    L = []
    for i in xrange(1, 8):
        d = x[i] + x[i + 1] + x[i + 2]
        L.append(d)
    return L

def isdivisible(y, LL):
    """Check the 7 divisibles"""
    if int(y[0]) % int(LL[0]) == 0 and int(y[1]) % int(LL[1]) == 0 \
       and int(y[2]) % int(LL[2]) == 0 and int(y[3]) % int(LL[3]) == 0 \
       and int(y[4]) % int(LL[4]) == 0 and int(y[5]) % int(LL[5]) == 0 \
       and int(y[6]) % int(LL[6]) == 0:
        return True
    else:
        return False

def main():
    """Main Program"""
    start_time = time.time()
    summer = 0
    x = itertools.permutations('0123456789', 10)
    for n in x:
        s = ''.join(n)
        y = get_divisibles(s)
        LL = [2, 3, 5, 7, 11, 13, 17]
        z = isdivisible(y, LL)
        if z == True:
            summer = summer + int(s)
        else:
            continue
    print "Answer = ", summer
    stop_time = time.time()
    run_time = stop_time - start_time
    print "run_time = ", run_time
        
if __name__ == '__main__':
    main()

Project Euler – Problem # 42 – Solved with Python

Problem:

The nth term of the sequence of triangle numbers is given by, tn = ½n(n+1); so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t10. If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt (right click and ‘Save Link/Target As…’), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

One Possible Solution:

# Python version = 2.7.1
# Platform = win32

letters = {'A': 1, 'B': 2, 'C': 3, 'D': 4, 'E': 5, 'F': 6, 'G': 7, \
        'H': 8, 'I': 9, 'J': 10, 'K': 11, 'L': 12, 'M': 13, 'N': 14, \
        'O': 15, 'P': 16, 'Q': 17, 'R': 18, 'S': 19, 'T': 20, \
        'U': 21, 'V': 22, 'W': 23, 'X': 24, 'Y': 25, 'Z': 26}

def get_word_value(xy):
    """Add up the value of the letters in the word xy"""
    counter = 0
    for i in xy:
        val = letters[i]
        counter = counter + val
    return counter

def get_triangle_number():
    """Create list L of triange numbers"""
    L = []
    for n in range(100):
        t = (.5 * n) * (n + 1)
        L.append(t)
    return L

def is_value_triangle_number(c, y):
    """Is the value of the word == to a triangle number?"""
    if c not in y:
        return False
    else:
        return True

def main():
    """Main Program"""
    L1 = []
    y = get_triangle_number()
    f = open('words.txt', "r")
    words = str(f.read())
    x = words.split('","')
    for word in x:
        if word == '"A':
            first = 'A'
            c = get_word_value(first)
            if is_value_triangle_number(c, y) == True:
                L1.append(first)
            else:
                continue
        elif word == 'YOUTH"':
            last = 'YOUTH'
            c = get_word_value(last)
            if is_value_triangle_number(c, y) == True:
                L1.append(last)
            else:
                continue
        elif word != '"A' or word != 'YOUTH"':
            xy = list(word)
            c = get_word_value(xy)
            if is_value_triangle_number(c, y) == True:
                L1.append(c)
            else:
                continue
        else:
            print "Error Message"
    print "Answer = ", len(L1)
            
if __name__ == '__main__':
    main()

Project Euler – Problem # 41 – Not Solved (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, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?

*********

I am still trying to figure out why I came up with 9,876,413 as a largest prime, which is also a pandigital number. Project euler accepts 7,652,413 as the answer. There may be a higher number than the one I found also, notice, it is only 7 digits long, a pandigital number can be up to 9 digits long.

My Solution for Problem # 41 (Takes about 3 minutes to run…)

# 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 ispandigital(n):
    """Check if integer n is pandigital"""
    x = list(str(n))
    L = []
    for i in x:
        if i not in L:
            L.append(i)
        else:
            return False
    return True

def main():
    """Main Program"""
    largest = 0
    for n in range(1000000, 10000000):
        if isprime(n) == True:
            if ispandigital(n) == True:
                if largest < n:
                    largest = n
                else:
                    continue
            else:
                continue
        else:
            continue
    print "Answer = ", largest
                
if __name__ == '__main__':
    main()

Project Euler – Problem # 40 – Solved with Python

Problem:

An irrational decimal fraction is created by concatenating the positive integers:

0.123456789101112131415161718192021…

It can be seen that the 12th digit of the fractional part is 1.

If dn represents the nth digit of the fractional part, find the value of the following expression.

d1 * d10 * d100 * d1000 * d10000 * d100000 * d1000000

One Possible Solution:

# Python version = 2.7.1
# Platform = win32

def main():
    """Main Program"""
    x = ''
    for n in range(1000000):
        x = x + str(n)
        if len(x) > 1000000:
            break
        else:
            continue
    Answer = int(x[1]) * int(x[10]) * int(x[100]) \
             * int(x[1000]) * int(x[10000]) * \
             int(x[100000]) * int(x[1000000])
    print "Answer = ", Answer

if __name__ == '__main__':
    main()