# Project Euler Problem 46: Goldbach's other conjecture

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 \cdot 1^2 \\ 15 = 7 + 2 \cdot 2^2 \\ 21 = 3 + 2 \cdot 3^2 \\ 25 = 7 + 2 \cdot 3^2 \\ 27 = 19 + 2 \cdot 2^2 \\ 33 = 31 + 2 \cdot 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?

#### Version 1: Brute force¶

Formally stated, Goldbach's Other Conjecture says that all odd composite numbers $n$ can be expressed as

$$n = 2k^2 + p$$

for some integer $k$ and prime number $p$. Let

$$S_n = \{ n - 2k^2 : k = 1, 2, \dotsc, \lfloor \sqrt{\frac{n}{2}} \rfloor \}$$

If any element $n - 2k^2$ of $S_n$ is prime, then we call $k$ a witness to Goldbach's Other Conjecture for $n$. We are asked to find the smallest $n$ that has no witness, i.e. such that all elements of $S_n$ are composite.

Let $P_n$ be the set of all prime numbers stricly smaller than $n$, then our algorithm searches for the smallest $n$ such that $P_n \cap S_n = \emptyset$, providing a counterexample to Goldbach's Other Conjecture.

# Project Euler Problem 47: Distinct primes factors

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² × 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?

#### Version 1: Fun times with Itertools¶

First let's load up the prime factorization function we implemented earlier. Recall that this function returns a Counter with the prime factor as the key, and its exponent as the value.

In [1]:
%load_ext autoreload

In [2]:
from common.utils import prime_factors

In [3]:
from itertools import count, tee
from six.moves import map, reduce, zip


Define an $n$-wise iterator over an iterator, inspired by the implementation of pairwise in the Itertools recipes. It get $n$ iterators for the iterable, advances the $i$th iterator by $i$, and zips them back together.

In [4]:
def nwise(iterable, n=2):
iters = tee(iterable, n)
for i, it in enumerate(iters):
for _ in range(i):
next(it, None)
return zip(*iters)


# Project Euler Problem 48: Self powers

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}$.

#### Version 1: The obvious way¶

In [1]:
from six.moves import map, range, reduce

In [2]:
sum(map(lambda k: k**k, range(1, 1000+1))) % 10**10

Out[2]:
9110846700

# Project Euler Problem 4: Largest palindrome product

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

Find the largest palindrome made from the product of two 3-digit numbers.

In [1]:
from six.moves import filter, range

In [2]:
is_palindrome = lambda s: s == s[::-1]
num_is_palindrome = lambda n: is_palindrome(str(n))

In [3]:
max(filter(num_is_palindrome, (x*y for x in range(100, 1000) for y in range(x, 1000))))

Out[3]:
906609