In the 20 × 20 grid below, four numbers along a diagonal line have been marked in red.
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
The product of these numbers is $26 × 63 × 78 × 14 = 1788696$.
What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20 × 20 grid?
In [1]:
from euler import Seq, timer
import numpy as np
def p011():
table = np.loadtxt(open("data/p011.txt","rb"),delimiter=" ", dtype=np.int)
rows, columns = np.shape(table)
def collect(i,j,di,dj):
step = 4
acc = 1
while True:
if step==0:
return acc
elif (i<0) | (i>=rows) | (j<0) | (j>=columns):
return 0
else:
acc *= table[i,j]
step -= 1
i += di
j += dj
def goRight(i,j): return collect(i,j,0,1)
def goDown(i,j): return collect(i,j,1,0)
def goDiag1(i,j): return collect(i,j,1,1)
def goDiag2(i,j): return collect(i,j,1,-1)
return (
[[goRight(i,j), goDown(i,j), goDiag1(i,j), goDiag2(i,j)]
for i in range(1,rows+1)
for j in range(1,columns+1)]
>> Seq.flatten
>> Seq.max)
timer(p011)
The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be $1+2+3+4+5+6+7=28$. The first ten terms would be:
$1,3,6,10,15,21,28,36,45,55,...$
Let us list the factors of the first seven triangle numbers:
$1: 1$
$3: 1,3$
$6: 1,2,3,6$
$10: 1,2,5,10$
$15: 1,3,5,15$
$21: 1,3,7,21$
$28: 1,2,4,7,14,28$
We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?
In [2]:
from euler import Seq, DivisorSigma, timer
def p012():
return (
Seq.unfold(lambda (n,m): (n+m, (n+1, m+n)), (1,0))
>> Seq.find(lambda n: DivisorSigma(n) > 500))
timer(p012)
In [3]:
from euler import Seq, timer
def p013():
return int(
str(open('data/p013.txt').read().splitlines()
>> Seq.map(long)
>> Seq.sum)[0:10])
timer(p013)
The following iterative sequence is defined for the set of positive integers:
n → n/2 (n is even)
n → 3n + 1 (n is odd)
Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
Which starting number, under one million, produces the longest chain?
NOTE: Once the chain starts the terms are allowed to go above one million.
In [4]:
from euler import memoize, snd, timer
@memoize
def collatz(n):
if n == 1:
x = 1
elif n%2 == 0:
x = 1 + collatz(int(n/2))
else:
x = 1 + collatz(int(3*n+1))
return x
def p014():
return max([(i, collatz(i)) for i in range(1,1000000)], key=snd)[1]
timer(p014)
In [6]:
from euler import timer
from math import factorial
def p015():
return factorial(40) / factorial(20) / factorial(20)
timer(p015)
In [7]:
from euler import timer
def p016():
return sum(int(n) for n in str(2L ** 1000))
timer(p016)
If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are $3+3+5+4+4=19$ letters used in total.
If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?
NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.
In [9]:
from euler import timer
read_basics = {0: 0, 1: 3, 2: 3, 3: 5,
4: 4, 5: 4, 6: 3, 7: 5,
8: 5, 9: 4, 10: 3, 11: 6,
12: 6, 13: 8, 14: 8, 15: 7,
16: 7, 17: 9, 18: 8, 19: 8,
20: 6, 30: 6, 40: 5, 50: 5,
60: 5, 70: 7, 80: 6, 90: 6}
def read_length(x):
if x==1000:
return 3+8
elif x<=20:
return read_basics[x]
elif x<100:
ten = x/10 * 10
last = x%10
return read_basics[ten] + read_basics[last]
else:
hund = x/100
if x%100==0:
return read_basics[hund] + 7
else:
return read_basics[hund] + 7 + 3 + read_length(x%100)
def p017():
return sum(read_length(i) for i in range(1,1001))
timer(p017)
By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.
3
7 4
2 4 6
8 5 9 3
That is, $3+7+4+9=23$.
Find the maximum total from top to bottom of the triangle below:
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)
In [10]:
from euler import Seq, timer
def p018():
return (
open('data/p018.txt').read().splitlines()
>> Seq.map(lambda s: s.split(' ') >> Seq.map(int))
>> Seq.rev
>> Seq.reduce(lambda a,b: a
>> Seq.window(2)
>> Seq.map(max)
>> Seq.zip(b)
>> Seq.map(sum))
>> Seq.head)
timer(p018)
You are given the following information, but you may prefer to do some research for yourself.
1 Jan 1900 was a Monday. Thirty days has September, April, June and November. All the rest have thirty-one, Saving February alone, Which has twenty-eight, rain or shine. And on leap years, twenty-nine. A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400. How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?
In [11]:
from datetime import date, timedelta
from euler import Seq, timer
def p019():
beg_dt = date(1901,1,1)
end_dt = date(2000,12,31)
return (
Seq.init((end_dt - beg_dt).days + 1, lambda x: beg_dt + timedelta(x))
>> Seq.filter(lambda x: (x.day == 1) & (x.weekday() == 1))
>> Seq.length)
timer(p019)
In [12]:
from math import factorial
from euler import Seq, timer
def p020():
return str(factorial(100)) >> Seq.map(int) >> Seq.sum
timer(p020)