### Pandigital prime

#### Problem 41

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?



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)




result: 7652413 (1.61s)



### Coded triangle numbers

#### Problem 42

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

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)




result: 162 (0.02s)



### Sub-string divisibility

#### Problem 43

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)




result: 16695334890 (7.12s)



### Pentagon numbers

#### Problem 44

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)




result: 5482660 (3.76s)



### Triangular, pentagonal, and hexagonal

#### Problem 45

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)




result: 1533776805 (0.22s)



### Goldbach's other conjecture

#### Problem 46

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)




result: 5777 (0.26s)



### Distinct primes factors

#### Problem 47

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)




result: 134043 (5.48s)



### Self powers

#### Problem 48

The series, $1^1 + 2^2 + 3^3 + ... + 10^{10} = 10405071317$.

Find the last ten digits of the series, $1^1 + 2^2 + 3^3 + ... + 1000^{1000}$.



In [60]:

from euler import timer

def p048():
return (range(1,1001) >> Seq.sumBy(lambda i: i ** i)) % (10 ** 10)

timer(p048)




result: 9110846700 (0.01s)




In [52]:

[ 1 .. 1000 ]
|> Seq.sumBy (fun i -> pown (bigint i) i)
|> fun n -> n%(pown 10I 10)




Out[52]:

val it : Numerics.BigInteger = 9110846700 {IsEven = true;
IsOne = false;
IsPowerOfTwo = false;
IsZero = false;
Sign = 1;}



### Prime permutations

#### Problem 49

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)




result: 296962999629 (0.06s)



### Consecutive prime sum

#### Problem 50

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)




result: 997651 (0.03s)