# Solutions to Project Euler #1-#10


```python
# This enables fetching of a PE problem by
#
#  %pe 32
#
%load_ext fetch_euler_problem
```

## Problem 1

[Multiples of 3 and 5](https://projecteuler.net/problem=1)

> <p>If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.</p>
> <p>Find the sum of all the multiples of 3 or 5 below 1000.</p>


```python
def prob001(a: int = 3, b: int = 5, below: int = 1000) -> int:
    """
    >>> prob001(3, 5, 10)
    23
    """
    set1 = set(range(a, below, a))
    set2 = set(range(b, below, b))
    return sum(set1 | set2)

```


```python
prob001()
```




    233168




```python
%timeit prob001()
```

    20.6 µs ± 3.58 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)


**Another Solution:** filtering might be nice.


```python
def prob001b(a: int = 3, b: int = 5, below: int = 1000) -> int:
    """
    >>> prob001b(3, 5, 10)
    23
    """
    return sum(i for i in range(below) if i % a == 0 or i % b == 0)

```


```python
prob001b()
```




    233168




```python
%timeit prob001b()
```

    120 µs ± 8.08 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)


## Problem 2

[Even Fibonacci numbers](https://projecteuler.net/problem=2)

> <p>Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:</p>
> <p style="text-align:center;">1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...</p>
> <p>By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.</p>

Fibonacci sequence may be generated from repeated map of two-integer state. Or, in matrix form,

$$
\begin{align*}
    a_{n+1} &= b_n \\
    b_{n+1} &= a_n + b_n 
\end{align*}
$$

with $a_0 = 0$ and  $b_0 = 1$.

Also note that an infinite series is nicely handled with the Python generator.


```python
import itertools as it


def prob002(maxval: int = 4000000) -> int:

    def fibs():
        i, j = 0, 1
        while True:
            (i, j) = (j, i + j)
            yield j

    fibseq = fibs()
    finite_fibs = it.takewhile(lambda x: x <= maxval, fibseq)
    return sum(n for n in finite_fibs if n % 2 == 0)

```


```python
prob002()
```




    4613732




```python
%timeit prob002()
```

    12.7 µs ± 2.87 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)


## Problem 3

[Largest prime factor](https://projecteuler.net/problem=3)

> <p>The prime factors of 13195 are 5, 7, 13 and 29.</p>
> <p>What is the largest prime factor of the number 600851475143 ?</p>

Quick (and cheating) way to factor integers is to use `factorint()` in `sympy.ntheory` module.


```python
import sympy.ntheory
sympy.ntheory.factorint(13195)
```




    {5: 1, 7: 1, 13: 1, 29: 1}




```python
def prob003_sympy(n: int = 600851475143) -> int:
    """
    >>> prob003_sympy(13195)
    29
    """
    factors = sympy.ntheory.factorint(n)
    return max(factors)
```


```python
prob003_sympy()
```




    6857




```python
%timeit prob003_sympy()
```

    710 µs ± 119 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)


Many nice algorithms for [integer factorization](https://en.wikipedia.org/wiki/Integer_factorization) exist (such as [Pollard's rho algorithm](https://en.wikipedia.org/wiki/Pollard's_rho_algorithm)), but a simple approach is good enough for this problem.


I prepared a generator giving psudo-prime sequence. I don't worry about composite numbers in the sequence because the target number $n$ is not divisible by them.


```python
from typing import Iterator

def psudo_primes() -> Iterator[int]:
    """
    Generate numbers n > 1 that is NOT multiple of 2 or 3.
    
    >>> import itertools
    >>> xs = tuple(itertools.takewhile(lambda x: x < 30, psudo_primes()))
    (2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29)
    """
    yield 2
    yield 3

    x = 5
    while True:
        yield x
        x += 2
        yield x
        x += 4


def prob003(n: int = 600851475143) -> int:
    """
    >>> prob003(13195)
    29
    """
    assert n > 1
    for p in psudo_primes():
        while n % p == 0:
            n //= p
            maxval = p
        if p * p > n:
            break
    if n > 1:
        maxval = n
    return maxval

```


```python
prob003()
```




    6857




```python
%timeit prob003()
```

    198 µs ± 21.3 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)


## Problem 4

[Largest palindrome product](https://projecteuler.net/problem=4)

> <p>A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.</p>
> <p>Find the largest palindrome made from the product of two 3-digit numbers.</p>

$n$-digit number $x$ is equivalent to $10^{n-1} \leq x < 10^n$. Following brute force algorithm is quadratic time complexity. 

**[FIXME]** It should be faster.


```python
def is_palindrome(number: int) -> bool:
    """
    Check if number is palindrome, the numbers identical to its reversed-direction digits.

    >>> is_palindrome(15651)
    True

    >>> is_palindrome(56)
    False
    """
    s = str(number)
    return s == "".join(reversed(s))


def prob004(digits: int = 3):
    """
    >>> prob004(digits=2)
    (9009, 91, 99)
    """
    lower_bound = 10 ** (digits - 1)
    upper_bound = 10 ** digits
    result = (0, 0, 0)
    for i in range(lower_bound, upper_bound):
        for j in range(i, upper_bound):
            x = i * j
            if is_palindrome(x) and result < (x, i, j):
                result = (x, i, j)

    return result

```


```python
prob004(digits=3)
```




    (906609, 913, 993)




```python
%timeit prob004()
```

    605 ms ± 217 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)


## Problem 5

[Smallest multiple](https://projecteuler.net/problem=5)

> <p>2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.</p>
> <p>What is the smallest positive number that is <dfn title="divisible with no remainder">evenly divisible</dfn> by all of the numbers from 1 to 20?</p>

The problem is to find the loweset common multiplier (LCM). `lcm` is available in `sympy`.


```python
import sympy
import functools

functools.reduce(sympy.lcm, range(1,11))
```




    2520



Greatest common divisor (GCD) is actually in the standard library `fractions`. And GCD and LCM are related by the identity

$$ \mathrm{LCM}(a, b) = \frac{a\, b}{\mathrm{GCD}(a, b)}. $$


```python
import math
import functools

def lcm(a: int, b: int) -> int:
    """
    Return the lowest common multiplier of a and b
    """
    return a // math.gcd(a, b) * b


def prob005(maxval: int = 20) -> int:
    """
    >>> prob005(10)
    2520
    """
    return functools.reduce(lcm, range(1, maxval + 1))

```


```python
prob005()
```




    232792560




```python
%timeit prob005()
```

    9.05 µs ± 1.32 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)


## Problem 6

[Sum square difference](https://projecteuler.net/problem=6)

> <p>The sum of the squares of the first ten natural numbers is,</p>
> <div style="text-align:center;">1<sup>2</sup> + 2<sup>2</sup> + ... + 10<sup>2</sup> = 385</div>
> <p>The square of the sum of the first ten natural numbers is,</p>
> <div style="text-align:center;">(1 + 2 + ... + 10)<sup>2</sup> = 55<sup>2</sup> = 3025</div>
> <p>Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.</p>
> <p>Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.</p>

Knowing the sums,

\begin{align}
    \sum_{n=1}^{N} n   &= \frac{1}{2} N(N+1), \\
    \sum_{n=1}^{N} n^2 &= \frac{1}{6} N (N+1) (2N + 1).
\end{align}

we can calculate the difference between the sum of squares and the square of the sum.

$$ \left( \sum_{n=1}^{N} n \right)^2 - \sum_{n=1}^{N} n^2  = \frac{1}{12} n (3 n^3 + 2 n^2 - 3n -2). $$



`sympy` can reproduce the algebraic manipulations.


```python
import sympy
# sympy.init_printing()    # turn on sympy printing on Jupyter notebooks


def the_difference():
    i, n = sympy.symbols("i n", integer=True)
    simple_sum = sympy.summation(i, (i, 1, n))
    sum_of_squares = sympy.summation(i ** 2, (i, 1, n))
    formula = sympy.simplify(simple_sum ** 2 - sum_of_squares)
    return formula


def prob006_sympy(nval=100):
    """
    >>> prob006_sympy(10)
    2640
    """
    formula = the_difference()
    n = formula.free_symbols.pop()
    return int(formula.evalf(subs={n:nval}))

```

This problem only requires summation over first one hundred numbers so bruteforce approach works.


```python
def prob006(n: int = 100) -> int:
    """
    >>> prob006(10)
    2640
    """
    xs = range(1, n + 1)
    simple_sum = sum(xs)
    sum_of_squares = sum(x ** 2 for x in xs)
    return simple_sum ** 2 - sum_of_squares

```

Then all you need is to evaluate the formula with upper bound.


```python
prob006()
```




    25164150




```python
%timeit prob006()
```

    30.8 µs ± 2.64 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)


## Problem 7

[10001st prime](https://projecteuler.net/problem=7)

> <p>By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.</p>
> <p>What is the 10 001st prime number?</p>

**Solution:** `sympy.ntheory` package has prime number generators.


```python
sympy.ntheory.prime(6)
```




    13




```python
sympy.ntheory.prime(10001)
```




    104743



s a good enough algorithm to generate prime numbers. 


It is known [(wikipedia.org)](https://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number) that  $n$-th prime number $p_n$ is bounded by

$$ \log n + \log \log n - 1 < \frac{p_n}{n} < \log n + \log \log n  \ \ \ \textrm{ for $n \geq 6$}. $$

So, I'll select integers up to the upper bound with [Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes).


```python
import math
from typing import Iterator, List

# Reproduction from Problem #3
def psudo_primes() -> Iterator[int]:
    yield 2
    yield 3
    x = 5
    while True:
        yield x
        x += 2
        yield x
        x += 6


def sieve(n: int) -> List[int]:
    """
    Return all prime numbers below n
    
    >>> sieve(10)
    [2, 3, 5, 7]
    """
    assert n > 1
    remaining = [True] * n  # never use the first two elements (0th and 1st)
    for p in range(2, int(math.sqrt(n) + 1)):
        if not remaining[p]:
            continue
        for q in range(p * p, n, p):
            remaining[q] = False
    return [p for p in range(2, n) if remaining[p]]


def prime(n: int) -> List[int]:
    """
    Return first n prime numbers
    
    >>> prime(10)
    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    """
    log = math.log
    if n >= 6:
        upperbound = int(n * (log(n) + log(log(n))))
        out = sieve(upperbound)
    else:
        out = [2, 3, 5, 7, 11]
    return out[:n]


def prob007(n: int = 10001) -> int:
    """
    >>> prob007(6)
    13
    """
    return prime(n)[-1]

```


```python
prob007()
```




    104743




```python
import sympy
%timeit sympy.ntheory.prime(10001)
```

    17.3 ms ± 4.65 ms per loop (mean ± std. dev. of 7 runs, 100 loops each)



```python
%timeit prob007()
```

    16.7 ms ± 463 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)


## Problem 8

## Problem 8

[Largest product in a series](https://projecteuler.net/problem=8)

> <p>The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.</p>
> <p style="font-family:'courier new';text-align:center;">73167176531330624919225119674426574742355349194934<br/>96983520312774506326239578318016984801869478851843<br/>85861560789112949495459501737958331952853208805511<br/>12540698747158523863050715693290963295227443043557<br/>66896648950445244523161731856403098711121722383113<br/>62229893423380308135336276614282806444486645238749<br/>30358907296290491560440772390713810515859307960866<br/>70172427121883998797908792274921901699720888093776<br/>65727333001053367881220235421809751254540594752243<br/>52584907711670556013604839586446706324415722155397<br/>53697817977846174064955149290862569321978468622482<br/>83972241375657056057490261407972968652414535100474<br/>82166370484403199890008895243450658541227588666881<br/>16427171479924442928230863465674813919123162824586<br/>17866458359124566529476545682848912883142607690042<br/>24219022671055626321111109370544217506941658960408<br/>07198403850962455444362981230987879927244284909188<br/>84580156166097919133875499200524063689912560717606<br/>05886116467109405077541002256983155200055935729725<br/>71636269561882670428252483600823257530420752963450<br/></p>
> <p>Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?</p>


```python
import operator
import functools


def product(iterable):
    """
    >>> product(range(1, 6))
    120
    """
    return functools.reduce(operator.mul, iterable)


def prob008(s: str, seq_size: int = 5):

    def slice_N_digits(idx):
        for i in s[idx : idx + seq_size]:
            yield int(i)

    return max(product(slice_N_digits(idx)) for idx in range(len(s) - seq_size))

```


```python
s = """
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450"""

xs = [int(c) for c in s.replace("\n", "")]
prob008(xs)

```




    40824




```python
%timeit prob008(xs)
```

    2.5 ms ± 358 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)


## Problem 9

[Special Pythagorean triplet](https://projecteuler.net/problem=9)

> <p>A Pythagorean triplet is a set of three natural numbers, <var>a</var> &lt; <var>b</var> &lt; <var>c</var>, for which,</p>
> <div style="text-align:center;"> <var>a</var><sup>2</sup> + <var>b</var><sup>2</sup> = <var>c</var><sup>2</sup></div>
> <p>For example, 3<sup>2</sup> + 4<sup>2</sup> = 9 + 16 = 25 = 5<sup>2</sup>.</p>
> <p>There exists exactly one Pythagorean triplet for which <var>a</var> + <var>b</var> + <var>c</var> = 1000.<br/>Find the product <var>abc</var>.</p>


```python
from typing import Optional, Tuple


def prob009(total: int = 1000) -> Optional[Tuple[int, int, int, int]]:
    """
    >>> prob009(total=12)
    (3, 4, 5, 60)
    """
    ub = total // 2  # just an upper bound
    for a in range(1, ub):                                           
        for b in range(a, ub):
            c = total - a - b
            if a ** 2 + b ** 2 == c ** 2:
                product = a * b * c
                return (a, b, c, product)
    else:
        return None
```


```python
prob009(12)
```




    (3, 4, 5, 60)




```python
%timeit prob009()
```

    66.8 ms ± 2.58 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)


## Problem 10

[Summation of primes](https://projecteuler.net/problem=10)

> <p>The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.</p>
> <p>Find the sum of all the primes below two million.</p>

`sympy` module has `primerange`.


```python
list(sympy.sieve.primerange(1, 10))
```




    [2, 3, 5, 7]



So, Just take sum of the prime numbers between 1 and 200000.


```python
import sympy

def prob010_sympy(n=2000000):
    """
    >>> prob010_sympy(10)
    17
    """
    return sum(sympy.sieve.primerange(1, n))
```


```python
%timeit prob010_sympy()
```

    34.2 ms ± 147 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)


Use Eratosthenes sieve in Problem 7.


```python
from typing import List

# Reproduction from problem 7
def sieve(n: int) -> List[int]:
    assert n > 1
    remaining = [True] * (n + 1)  # never use the first two elements (0th and 1st)
    for p in range(2, int(math.sqrt(n) + 1)):
        if not remaining[p]:
            continue
        for q in range(p * p, n + 1, p):
            remaining[q] = False
    return [p for p in range(2, n + 1) if remaining[p]]


def prob010(n: int = 2000000) -> int:
    """
    >>> prob010(10)
    17
    """
    return sum(sieve(n))

```


```python
prob010()
```




    142913828922




```python
%timeit prob010()
```

    497 ms ± 128 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)


## [Appendix] Run doctests


```python
import doctest
doctest.testmod()
```




    TestResults(failed=0, attempted=16)




```python

```

6ed073906c09cbb86013d31d98422f322c490a51
ipynb
Jupyter Notebook
Problems_001-010.ipynb
yamaton/project-euler-jupyter
7566c0536627173d9eaa53400e81a7e6c7d4b994
MIT
2018-11-07T21:56:56.000Z
2018-11-07T21:56:56.000Z
Problems_001-010.ipynb
yamaton/project-euler-ipython
7566c0536627173d9eaa53400e81a7e6c7d4b994
MIT
Problems_001-010.ipynb
yamaton/project-euler-ipython
7566c0536627173d9eaa53400e81a7e6c7d4b994
MIT
2019-07-19T05:08:59.000Z
2021-05-02T18:11:33.000Z
Qwen/Qwen-72B
1. YES
2. YES