Project Euler – Problem # 51 – Solved with Python

Problem:

By replacing the 1st digit of *3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.

By replacing the 3rd and 4th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.

Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.

**********

The string.replace(old, new) method made this solution work.

One Possible Solution:

# Python version = 2.7.1
# Platform = win32

import gmpy
import string

def isprime(n):
    """Return True of False - Prime number"""
    if gmpy.is_prime(n):
        return True
    else:
        return False

def prime_list():
    """Create prime number list below 1000000"""
    L = []
    for n in xrange(100, 1000000):
        if isprime(n):
            L.append(n)
    return L

def replace(s1, n):
    """Replace repeating digits"""
    L1 = []
    for i in range(1, 10):
        y = str(i)
        x = s1.replace(n, y)
        L1.append(x)
    return L1
        
def are_prime(x):
    """Check new number for primality"""
    L2 = []
    for number in x:
        if isprime(int(number)):
            L2.append(int(number))
        else:
            continue
    if len(L2) == 8:
        print "L2 = ", L2
        print "YAHOOOO!"
        return True
            
def call_this(s1, k):
    """Intermediate step"""
    for n in s1:
        if n == k:
            x = replace(s1, n)
            if are_prime(x):
                return True
                
def find_duplicates(prime):
    """Find digits that repeat"""
    s = ''
    s1 = str(prime)
    s = s1[0:-1]
    d = {}
    for i in s:
        # Create Dictionary
        d[i] = s.count(i)
    for k, v in d.items():
        if v > 1:
            if call_this(s1, k):
                break
        else:
            continue

def main():
    """Main Program"""
    x = prime_list()
    for prime in x:
        y = find_duplicates(prime)
        
if __name__ == '__main__':
    main()
Advertisements

Project Euler – Problem # 50 – Solved with Python

Problem:

The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

**********

Ok, Here is what I came up with – not 100% confident about how I came to the Answer

We can take the list of all prime number below 1,000,000, start with the 1st number -2 , add them together, save the added results (primes) in a list, then take the last number in the list(this would be the result of adding the most consecutive prime numbers), and how many repetitions it took to get this number. After this we can go on to the second numer in the primes list – 3, and start adding, save the added primes in a list, then take the last number in the list, and how many repetitions it took to get that number. The output I’ve included is for the first 20 increments from the start of the prime number list (2, 3, 5, 7, 11, 13, 17, etc), after this the number of repetitions (consecutive numbers) starts dwindling. So looking at the list of the first 20 adds, can you pick out the largest prime with the most repetitions?

One Possible Solution:

# Python version = 2.7.1
# Platform = win32

import gmpy

def isprime(n):
    """Return True of False - Prime number"""
    if gmpy.is_prime(n):
        return True
    else:
        return False

def prime_list():
    """Create prime number list below 1000000"""
    L = []
    for n in xrange(1, 1000000):
        if isprime(n):
            L.append(n)
    return L

def add_primes(primes, switch):
    """Return the last number in the list (largest prime),
    and the in-loop counter (consecutive numbers)"""
    counter = switch # start with this prime number
    in_counter = 0
    sum = 0
    L = []
    while sum < 1000000:
        sum = sum + primes[counter]
        if isprime(sum):
            L.append(sum)
        in_counter += 1 # in loop counter
        counter += 1
    if L[-1] < 1000000:
        return L[-1], in_counter
    elif L[-1] > 1000000:
        print "****"
        return L[-2], in_counter
       
def main():
    """Main Program"""
    primes = prime_list()
    main_counter = 0
    for switch in range(0, 20):
        x = add_primes(primes, switch)
        print x[0], x[1]
        if x[0] > main_counter:
            main_counter = x[0]
    print "Answer = ", main_counter
            
if __name__ == '__main__':
    main()

Output:

958577 547
920291 546
978037 545
997651 544
****
954697 543
966307 542
****
993689 541
989743 540
****
970147 539
868051 538
908849 537
989641 536
970027 535
958339 534
****
985597 533
997333 532
908597 531
973691 530
834949 529
981391 528
Answer =  (997651, 544)

Project Euler – Problem # 49 – Solved with Python

Problem:

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

One Possible Solution:

# Python version = 2.7.1
# Platform = win32

import gmpy
import itertools

def get_primes():
    """Get a list of all 4 digit prime numbers"""
    L = []
    for n in range(1000, 10000):
        if gmpy.is_prime(n) > 0:
            L.append(n)
        else:
            continue
    return L

def isprime(n):
    """Check if a number is prime"""
    if gmpy.is_prime(n) > 0:
        return True
    else:
        return False
    
def get_permutations(i):
    """Get all permutations of a number i"""
    L = []
    y = str(i)
    x = itertools.permutations(y, 4)
    for e in x:
        e1 = ''.join(map(str, e))
        L.append(e1)
    return L

def are_permutations(x, i, i1, i2):
    """Check if arithmetic sequence are permutations
    of each other?"""
    if (str(i1) in x) and (str(i2) in x):
        print "Answer = ", str(i) + str(i1) + str(i2)

def main():
    """Main Program"""
    L = get_primes()
    for i in L:
        for n in range(1, 3331):
            i1 = i + n
            i2 = (i + n) + n
            if isprime(i1) and isprime(i2):
                x = get_permutations(i)
                y = are_permutations(x, i, i1, i2)
            else:
                continue

if __name__ == '__main__':
    main()

Project Euler – Problem # 48 – Solved with Python

Problem:

The series, 11 + 22 + 33 + … + 1010 = 10405071317.

Find the last ten digits of the series, 11 + 22 + 33 + … + 10001000.

One Possible Solution:

# Python version = 2.7.1
# Platform = win32

def main():
    """Main Program"""
    total = 0
    tally = ''
    for i in range(1, 1001):
        total = total + (i ** i)
    x = str(total)
    y = len(x) - 10
    s = x[y:]
    print "Answer = ", s
    
if __name__ == '__main__':
    main()

Project Euler – Problem # 47 – Solved with Python

Problem:

The first two consecutive numbers to have two distinct prime factors are:

  • 14 = 2 * 7
  • 15 = 3 * 5

The first three consecutive numbers to have three distinct prime factors are:

  • 644 = 22 * 7 * 23
  • 645 = 3 * 5 * 43
  • 646 = 2 * 17 * 19.

Find the first four consecutive integers to have four distinct primes factors. What is the first of these numbers?

One Possible Solution:

# Python version = 2.7.1
# Platform = win32
# stop_time =  6.33370859353 (seconds)

import sympy
import time
    
def get_factors(n):
    """Factor number n"""
    f = sympy.factorint(n)
    return f
        
def main():
    """Main Program"""
    start_time = time.clock()
    counter = 0
    for n in range(1000, 1000000):
        if counter == 4:
            print "Answer=", n - 4
            break
        else:
            x = get_factors(n)
            if len(x) == 4:
                counter += 1
            else:
                counter = 0
    stop_time = time.clock() - start_time
    print "stop_time = ", stop_time
    
if __name__ == '__main__':
    main()

Project Euler – Problem # 46 – Solved with Python

Problem:

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

  • 9 = 7 + 2*12
  • 15 = 7 + 2*22
  • 21 = 3 + 2*32
  • 25 = 7 + 2*32
  • 27 = 19 + 2*22
  • 33 = 31 + 2*12

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

One Possible Solution:

# Python version = 2.7.1
# Platform = win32

import gmpy

def get_primes():
    """Get primes up to 10000"""
    L = []
    for n in range(1, 10000, 2):
        if gmpy.is_prime(n) > 0:
            L.append(n)
    return L

def compute_conject(x, c):
    """Try the conjecture formula"""
    for n in range(1, 100):
        for ii in x:
            conject = ii + (2 * (n ** 2))
            if conject == c:
                return True
            else:
                continue
    return False
        
def main():
    """Main Program"""
    x = get_primes()
    composites = []
    for y in range(1, 10000, 2):
        # make composites up to 10000
        if y not in x:
            composites.append(y)
        else:
            continue
    for c in composites:
        if c > 33:
        # We already know up through 33
            x2 = compute_conject(x, c)
            if x2 == False:
                """print the first odd composite that cannot
                be written as the sum of a prime and twice the square"""
                print "Answer = ", c
                break
            else:
                continue
        else:
            continue
        
if __name__ == '__main__':
    main()