Calvi, Corsica

1500 piece jigsaw puzzle
Calvi, Corsica

1982 Puzzle I purchased on Ebay – 1500 pieces, completed on May 27th, 2011

Corsica on Bing Maps

Advertisements

Project Euler – Problem # 58 – Solved with Python

Problem:

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 ~ 62%.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

**********

This problem is similar to Project Euler problem # 28. I just reworked that problem: We form a diagonal, and check the numbers in the diagonal for primality. I used high – low, ‘guess this number’ testing for the length of the diagonal. 13121 is the first number that came out as less than 10% for the ratio. So if we double that number we get 26242, with 26241 being the answer to this problem. (The last diagonal with 10% or more primes is 13120. Multiply this by 2 we get 26240, then add 1 for the center and we have 26241.)

One Possible Solution:

# Python version = 2.7.1
# Platform = win32

from __future__ import division
import gmpy

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

def form_diagonal(passed):
    """Form a leg of the diagonal, return the
    number of primes in that leg, and (i), which
    is 1/2 the length of the diagonal."""
    summer = 1
    adder = 0
    L = []
    for i in range(1, 13121): # 1/2 the length of the diagonal
        if i < 2:
            adder = passed
        else:
            adder = adder + 8
        summer = summer + adder
        if isprime(summer):
            L.append(summer)
    return len(L), i
        
def main():
    """Main Program"""
    upper_right = form_diagonal(2)
    upper_left = form_diagonal(4)
    lower_left = form_diagonal(6)
    lower_right = form_diagonal(8)
    primes = upper_right[0] + upper_left[0] + \
             lower_left[0] + lower_right[0]
    all_numbers = (lower_right[1] * 4) + 1
    ratio = primes / all_numbers
    print "ratio = ", ratio
    if ratio < .10:
        print "Ratio is less than 10%"
    
if __name__ == '__main__':
    main()

Project Euler – Problem # 56 – Solved with Python

Problem:

A googol (10100) is a massive number: one followed by one-hundred zeros; 100100 is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.

Considering natural numbers of the form, ab, where a, b < 100, what is the maximum digital sum?

One Possible Solution:

# Python version = 2.7.1
# Platform = win32

def main():
    """Main Program"""
    answer = 0 
    for a in range(1, 101):
        for b in range(1, 101):
            natural_number = a ** b
            L = list(str(natural_number))
            digital_sum = 0
            for i in L:
                digital_sum = digital_sum + int(i)
            if digital_sum > answer:
                answer = digital_sum
    print "Answer = ", answer

if __name__ == '__main__':
    main()

Project Euler – Problem # 55 – Solved with Python

Problem:

If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.

Not all numbers produce palindromes so quickly. For example,

  • 349 + 943 = 1292,
  • 1292 + 2921 = 4213
  • 4213 + 3124 = 7337

That is, 349 took three iterations to arrive at a palindrome.

Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome. A number that never forms a palindrome through the reverse and add process is called a Lychrel number. Due to the theoretical nature of these numbers, and for the purpose of this problem, we shall assume that a number is Lychrel until proven otherwise. In addition you are given that for every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).

Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is 4994.

How many Lychrel numbers are there below ten-thousand?

NOTE: Wording was modified slightly on 24 April 2007 to emphasise the theoretical nature of Lychrel numbers.

One Possible Solution:

# Python version = 2.7.1
# Platform = win32

def palindromic(tally):
    """Check if number (tally) is a palindrome"""
    x = str(tally)
    y = x[::-1]
    if x == y:
        return True
    else:
        return False

def isLychrel(n):
    """Check if number (n) is a Lychrel number"""
    counterL = 0
    while counterL < 50:
        reverse = int(str(n)[::-1])
        tally = n + reverse
        if palindromic(tally):
            return False
        else:
            n = tally
        counterL += 1
    return True
   
def main():
    """Main Program"""
    counter = 0
    for n in range(10, 10001):
        if isLychrel(n):
            counter += 1
    print "Answer = ", counter

if __name__ == '__main__':
    main()

Project Euler – Problem # 54 – Solved with Python

Problem:

In the card game poker, a hand consists of five cards and are ranked, from lowest to highest, in the following way:

  • High Card: Highest value card.
  • One Pair: Two cards of the same value.
  • Two Pairs: Two different pairs.
  • Three of a Kind: Three cards of the same value.
  • Straight: All cards are consecutive values.
  • Flush: All cards of the same suit.
  • Full House: Three of a kind and a pair.
  • Four of a Kind: Four cards of the same value.
  • Straight Flush: All cards are consecutive values of same suit.
  • Royal Flush: Ten, Jack, Queen, King, Ace, in same suit.

The cards are valued in the order:
2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King, Ace.

If two players have the same ranked hands then the rank made up of the highest value wins; for example, a pair of eights beats a pair of fives (see example 1 below). But if two ranks tie, for example, both players have a pair of queens, then highest cards in each hand are compared (see example 4 below); if the highest cards tie then the next highest cards are compared, and so on.

Consider the following five hands dealt to two players:

Hand Player 1 Player 2 Winner
1 5H 5C 6S 7S KD 2C 3S 8S 8D TD Player 2
Pair of Fives Pair of Eights
2 5D 8C 9S JS AC 2C 5C 7D 8S QH Player 1
Highest card Ace Highest card Queen
3 2D 9C AS AH AC 3D 6D 7D TD QD Player 2
Three Aces Flush with Diamonds
4 4D 6S 9H QH QC 3D 6D 7H QD QS Player 1
Pair of Queens Pair of Queens
Highest card Nine Highest card Seven
5 2H 2D 4C 4D 4S 3C 3D 3S 9S 9D Player 1
Full House Full House
With Three Fours With Three Threes

The file, poker.txt, contains one-thousand random hands dealt to two players. Each line of the file contains ten cards (separated by a single space): the first five are Player 1’s cards and the last five are Player 2’s cards. You can assume that all hands are valid (no invalid characters or repeated cards), each player’s hand is in no specific order, and in each hand there is a clear winner.

How many hands does Player 1 win?

One Possible Solution:

# Python version = 2.7.1
# Platform = win32

from collections import Counter

d = {'1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, \
     '7': 7, '8': 8, '9': 9, 'T': 10, 'J': 11, 'Q': 12, \
     'K': 13, 'A': 14, 'One Pair': 29, 'Two Pairs': 59, \
     'Three of a Kind': 74, 'Straight': 89, 'Flush': 104, \
     'Full House': 119, 'Four of a Kind': 134,
     'Straight Flush': 149, 'Royal Flush': 164}

def high_card(dL):
    """Is the hand High Card?"""
    holder = 0
    if len(dL) == 5:
        return True
    else:
        return False

def one_pair(dL):
    """Is the hand One Pair?"""
    if len(dL) == 4:
        for k, v in dL.iteritems():
            if v == 2:
                return True
            else:
                continue
    else:
        return False

def two_pairs(dL):
    """Is the hand Two Pairs?"""
    counter = 0
    k1 = 0
    if len(dL) == 3:
        for k, v in dL.iteritems():
            if v == 2:
                if k > k1:
                    k1 = k
                counter += 1
                if counter == 2:
                    return True
            else:
                continue
    else:
        return False
    
def three_of_a_kind(dL):
    """Is the hand Three of a Kind?"""
    if len(dL) == 3:
        for k, v in dL.iteritems():
            if v == 3:
                return True
            else:
                continue
    else:
        return False

def straight(L):
    """Is the hand a Straight?"""
    L = sorted(L)
    if (L[0] + 1) == L[1] and (L[0] + 2) == \
       L[2] and (L[0] + 3) == L[3] and \
       (L[0] + 4) == L[4]:
        return True
    else:
        return False
    
def flush(L1):
    """Is the hand a Flush"""
    if len(Counter(L1)) == 1:
        return True
    else:
        return False

def full_house(dL):
    """Is the hand a Full House?"""
    if len(dL) == 2:
        for k, v in dL.iteritems():
            if v == 3:
                return True
            else:
                continue
    else:
        return False

def four_of_a_kind(dL):
    """Is the hand Four of a Kind?"""
    if len(dL) == 2:
        for k, v in dL.iteritems():
            if v == 4:
                return True
            else:
                continue
    else:
        return False

def straight_flush(L, L1):
    """Is the hand a Straight Flush?"""
    L = sorted(L)
    if len(Counter(L1)) == 1 and \
       ((L[0] + 1) == L[1] and (L[0] + 2) == \
       L[2] and (L[0] + 3) == L[3] and \
       (L[0] + 4) == L[4]):
        return True
    else:
        return False

def royal_flush(L, L1):
    """Is the hand a Royal Flush?"""
    if len(Counter(L1)) == 1 and sum(L) == 60:
        return True
    else:
        return False
    
def examine_cards(cards):
    """Examine Cards"""
    L, L1 = [], []
    dL = {}
    for i in range(0, 9, 2):
        x1 = d[cards[i]]
        L.append(x1)
    for i in range(1, 10, 2):
        x1 = cards[i]
        L1.append(x1)
    for i in L:
        dL[i] = L.count(i)
    if royal_flush(L, L1):
        return d['Royal Flush']
    elif straight_flush(L, L1):
        return d['Straight Flush']
    elif four_of_a_kind(dL):
        c1 = 0
        for k, v in dL.iteritems():
            if v == 4:
                c1 = k
        return d['Four of a Kind'] + c1
    elif full_house(dL):
        c2 = 0
        for k, v in dL.iteritems():
            if v == 3:
                c2 = k
        return d['Full House'] + c2
    elif flush(L1):
        c3 = 0
        for k, v in dL.iteritems():
            if k > c3:
                c3 = k
        return d['Flush'] + c3
    elif straight(L):
        c4 = 0
        for k, v in dL.iteritems():
            if k > c4:
                c4 = k
        return d['Straight'] + c4
    elif three_of_a_kind(dL):
        c5 = 0
        for k, v in dL.iteritems():
            if v == 3:
                c5 = k
        return d['Three of a Kind'] + c5
    elif two_pairs(dL):
        k1 = 0
        for k, v in dL.iteritems():
            if v == 2:
                if k > k1:
                    k1 = k
        return d['Two Pairs'] + k1
    elif one_pair(dL):
        c6 = 0
        for k, v in dL.iteritems():
            if v == 2:
                c6 = k
        return d['One Pair'] + c6 
    elif high_card(dL):
        count1 = 0
        for k, v in dL.iteritems():
            if k > count1:
                count1 = k
        return count1
    else:
        print "***Error Message***"
    
def main():
    """Main Program"""
    player1 = 0
    f = open('poker.txt', 'r')
    for line in f:
        x = line.split(' ')
        y = ''.join(x)
        player_one = y[0:10]
        player_two = y[10:20]
        j = examine_cards(player_one)
        t = examine_cards(player_two)
        if j == t:
            print "player_one = ", player_one
            print "player_two = ", player_two
            print "EQUAL"
        elif j < t:
            continue
        elif j > t:
            player1 += 1
        else:
            pass
    f.close()
    print "Answer = ", player1
    
if __name__ == '__main__':
    main()

Project Euler – Problem # 52 – Solved with Python

Problem:

It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.

Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.

One Possible Solution:

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

import time

d = {0: "zero", 1: "one", 2: "two", 3: "three", 4: "four", \
     5: "five", 6: "six", 7: "seven", 8: "eight", 9: "nine"}

def main():
    """Main Program"""
    start_time = time.clock()
    counter = 1
    while counter < 150000:
        L = []
        for n in range(2, 7):
            result = str(counter * n)
            L.append(result)
        L3 = []
        for number in L:
            L2 = []
            for i, digit in enumerate(number):
                s = int(digit)
                L2.append(d[s])
            L3.append(L2)
        if cmp(sorted(L3[0]), sorted(L3[1])) == 0 and \
           cmp(sorted(L3[0]), sorted(L3[2])) == 0 and \
           cmp(sorted(L3[0]), sorted(L3[3])) == 0 and \
           cmp(sorted(L3[0]), sorted(L3[4])) == 0:
            print "YAHOO = ", counter
        counter += 1
    stop_time = time.clock() - start_time
    print "stop_time = ", stop_time
    
if __name__ == '__main__':
    main()

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()

1500 Piece Jigsaw Puzzle

1500 Piece Jigsaw Puzzle
1500 Piece Jigsaw Puzzle Completed on May 12, 2011

I completed this 1500 piece jigsaw puzzle today. The box did not have a name for the picture… I guess I can call it ‘Happenings in town’

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()