In [57]:
from euler import Seq, timer, is_prime
from itertools import permutations
def p041():
k = 9
results = []
while results == []:
results = (permutations(range(1, k+1) >> Seq.map(str))
>> Seq.map(lambda x: int("".join(x)))
>> Seq.filter(is_prime)
>> Seq.toList)
k-=1
return max(results)
timer(p041)
The nth term of the sequence of triangle numbers is given by, $t_n = \frac 1 2 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 = t_{10}$. 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?
In [129]:
from euler import Seq, timer
import re
def p042():
words = re.compile('[A-Z]+').findall(open('data/p042.txt').read())
scores = words >> Seq.map(lambda x: x >> Seq.sumBy(lambda x: ord(x) - 64)) >> Seq.toList
max_score = max(scores)
tri_numbers = (
Seq.initInfinite(lambda x: x*(x+1)/2)
>> Seq.skip(1)
>> Seq.takeWhile(lambda x: x < max_score)
>> Seq.toList)
is_tri = lambda n: n == (tri_numbers >> Seq.find(lambda k: k >= n))
return (
scores
>> Seq.filter(is_tri)
>> Seq.length)
timer(p042)
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 $d_1$ be the 1st digit, $d_2$ be the 2nd digit, and so on. In this way, we note the following:
$d_2d_3d_4=406$ is divisible by 2
$d_3d_4d_5=063$ is divisible by 3
$d_4d_5d_6=635$ is divisible by 5
$d_5d_6d_7=357$ is divisible by 7
$d_6d_7d_8=572$ is divisible by 11
$d_7d_8d_9=728$ is divisible by 13
$d_8d_9d_{10}=289$ is divisible by 17
Find the sum of all $0$ to $9$ pandigital numbers with this property.
In [150]:
from euler import Seq, timer
from itertools import permutations
def p043():
def test(n):
return (n[0] <> '0' and
int(n[1:4]) % 2 == 0 and
int(n[2:5]) % 3 == 0 and
int(n[3:6]) % 5 == 0 and
int(n[4:7]) % 7 == 0 and
int(n[5:8]) % 11 == 0 and
int(n[6:9]) % 13 == 0 and
int(n[7:10]) % 17 == 0)
return (
permutations(range(10) >> Seq.map(str))
>> Seq.map(lambda x: "".join(x))
>> Seq.filter(test)
>> Seq.sumBy(int))
timer(p043)
Pentagonal numbers are generated by the formula, $P_n=n(3n−1)/2$. The first ten pentagonal numbers are:
$1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...$
It can be seen that $P_4 + P_7 = 22 + 70 = 92 = P_8$. However, their difference, $70 − 22 = 48$, is not pentagonal.
Find the pair of pentagonal numbers, $P_j$ and $P_k$, for which their sum and difference are pentagonal and $D = |Pk − Pj|$ is minimised; what is the value of $D$?
In [5]:
from euler import Seq, timer
def p044():
pentagonals = (
Seq.initInfinite(lambda i: i*(3*i-1)/2)
>> Seq.skip(1)
>> Seq.takeWhile(lambda n: n < 10000000)
>> Seq.toSet)
# assuming that pj and pk are under 10M
return (
pentagonals
>> Seq.collect(lambda j: pentagonals >> Seq.map(lambda k: (j,k)))
>> Seq.filter(lambda (j,k): (j+k) in pentagonals)
>> Seq.filter(lambda (j,k): (k-j) in pentagonals)
>> Seq.map(lambda (j,k): k-j)
>> Seq.min)
timer(p044)
Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:
| Triangle | $T_n=n(n+1)/2$ | 1, 3, 6, 10, 15, ... |
| Pentagonal | $P_n=n(3n−1)/2$ | 1, 5, 12, 22, 35, ... |
| Hexagonal | $H_n=n(2n−1)$ | 1, 6, 15, 28, 45, ... |
It can be verified that $T_{285} = P_{165} = H_{143} = 40755$.
Find the next triangle number that is also pentagonal and hexagonal.
In [13]:
from euler import Seq, timer
def p045():
maxN = 10000000000
hexs = (Seq.initInfinite(lambda i: i*(2*i-1))
>> Seq.skipWhile(lambda n: n <= 40755)
>> Seq.takeWhile(lambda n: n < maxN)
>> Seq.toSet)
pents = (Seq.initInfinite(lambda i: i*(3*i-1)/2)
>> Seq.skipWhile(lambda n: n <= 40755)
>> Seq.takeWhile(lambda n: n < maxN)
>> Seq.toSet)
tris = (Seq.initInfinite(lambda i: i*(i+1)/2)
>> Seq.skipWhile(lambda n: n <= 40755)
>> Seq.takeWhile(lambda n: n < maxN)
>> Seq.toSet)
return hexs.intersection(pents).intersection(tris).pop()
timer(p045)
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×1^2$
$15 = 7 + 2×2^2$
$21 = 3 + 2×3^2$
$25 = 7 + 2×3^2$
$27 = 19 + 2×2^2$
$33 = 31 + 2×1^2$
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?
In [37]:
from euler import Seq, timer, primes, is_prime
from math import sqrt
def p046():
def is_square(n):
t = int(sqrt(n))
return n == t*t
def valid(n):
return (primes()
>> Seq.takeWhile(lambda k: k < n)
>> Seq.exists(lambda k: is_square((n-k)/2)))
return (
Seq.initInfinite(lambda k: k*2+9)
>> Seq.filter(lambda k: not(is_prime(k)))
>> Seq.find(lambda k: not(valid(k))))
timer(p046)
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 = 2^2 × 7 × 23$
$645 = 3 × 5 × 43$
$646 = 2 × 17 × 19$.
Find the first four consecutive integers to have four distinct prime factors. What is the first of these numbers?
In [56]:
from euler import FactorInteger, timer, Seq
def p047():
len = 4
return (
Seq.initInfinite(lambda x: x)
>> Seq.map(lambda n: FactorInteger(n) >> Seq.length)
>> Seq.window(len)
>> Seq.findIndex(lambda xs: xs >> Seq.forall(lambda x: x == len)))
timer(p047)
In [60]:
from euler import timer
def p048():
return (range(1,1001) >> Seq.sumBy(lambda i: i ** i)) % (10 ** 10)
timer(p048)
In [52]:
[ 1 .. 1000 ]
|> Seq.sumBy (fun i -> pown (bigint i) i)
|> fun n -> n%(pown 10I 10)
Out[52]:
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?
In [14]:
from euler import Seq, timer, is_prime, primes
from itertools import permutations, combinations
def p049():
def get_prime_permutations(n):
return (permutations(str(n) >> Seq.map(str))
>> Seq.toSet
>> Seq.map(lambda chars: int("".join(chars)))
>> Seq.filter(lambda x: x >= 1000 and is_prime(x))
>> Seq.sort
>> Seq.toList)
return (
int("".join(
primes()
>> Seq.map(get_prime_permutations)
>> Seq.filter(lambda l: l >> Seq.length >= 3)
>> Seq.collect(lambda l: combinations(l,3) >> Seq.filter(lambda x: (x[1]-x[0]) == (x[2]-x[1])))
>> Seq.distinct
>> Seq.nth(1)
>> Seq.map(str))))
timer(p049)
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?
In [17]:
from euler import primes, Seq, fst, is_prime, primes, timer
def p050():
def max_prime(skip):
return (
primes()
>> Seq.skip(skip)
>> Seq.scan(lambda state, n: (1+state[0], n+state[1]), (0,0))
>> Seq.takeWhile(lambda n: n[1] < 1000000)
>> Seq.filter(lambda n: is_prime(n[1]))
>> Seq.maxBy(fst))
def loop(k,result):
test = primes() >> Seq.skip(k) >> Seq.take(result[0]) >> Seq.sum
if (test > 1000000):
return result[1]
else:
r = [max_prime(k), result] >> Seq.maxBy(fst)
return loop(k+1, r)
return loop(1, max_prime(0))
timer(p050)