Calvi, Corsica
1982 Puzzle I purchased on Ebay – 1500 pieces, completed on May 27th, 2011
May 27, 2011
May 18, 2011
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()
May 17, 2011
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()
May 16, 2011
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()
May 13, 2011
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()
May 12, 2011
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’
May 10, 2011
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)
May 8, 2011
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()
