Project Euler

This Python 3 notebook contains some solutions for the Project Euler challenge.

/!\ Warning: do not spoil yourself the pleasure of solving these problems by yourself!

I (Lilian Besson) started in February 2015, and worked occasionally on Project Euler problems in March and April 2015. I should try to work on it again, hence this notebook...

Badge giving the number of solved problems

Problem 12 : Highly divisible triangular number

That's slow if you test for divisors until n, but using this $\lfloor \sqrt{n} \rfloor$ trick speeds it up!

Problem 19: Counting Sundays

==> 171

Problem 26: Reciprocal cycles TODO

Let's try with 1000 digits, and I'll just increase it if the solution is not good.

Example:

How to detect a cycle and its length:

How to detect a cycle in a decimal number of the form $\frac{1}{d}$:

Now it's easy to find a number with maximum cycle length:

I have not yet found a way to conclude. Working with strings and decimal.Decimal numbers is probably a wrong idea.

Problem 32: Pandigital products

Problem 33: Digit cancelling fractions

So there are 3916 fractions of $x/y$ with $x,y$ having exactly two numbers, such that $x/y \leq 1$. For each of them, we will try to remove one of the digits from $x$ and from $y$, and check if the resulting "reduced" fraction is equal to the original one. If we remove $0$, we won't count it.

It's easy to remove digits when working with strings:

So we can check if the fraction $i/j$ can be "wrongly" simplified/reduced by such code:

Let's try it:

So there are indeed exactly four such fractions (with exactly two digits on nominator and denominator).

Let's compute their product:

Problem 34: Digit factorials

Let's compute efficiently the factorial function, by using memoisation:

First, we need to bound the size of the largest integer that can be the sum of the factorials of its digits.

Let $k$ the number of digits of $x$, for instance $k=2$. Then $x$ is between $100...0 = 10^{k-1}$ (eg $10$ for $k=2$) and $999..9 = 10^k - 1$ (eg $99 = 100-1$ for $k=2$). The sum of the factorials of the digits of $x$ is between $1 * 1! + (k-1) * 0! = 1$ and $k * 9! = 362880 k$.

And thus, as soon as $362880 k < 10^{k-1}$ then it is not possible for $x$ to be equal to the sum of the factorials of its digits.

For small values of $k$, such that $k=3$ (for the example $145$), $10^{k-1} \leq 362880 k$ but we can easily find the smallest $k$ that violates this inequality.

So the smallest $k$ that don't work is the smallest $k$ such that $362880 k < 10^{k-1}$. The right-hand side grows exponentially while the left-hand side grows linearly, so clearly there will be a solution. Intuitively, it won't be large. Let's find out manually:

We can also easily test if a number is the sum of the factorials of its digits:

Now we can list all the numbers up-to a certain bound, and keep the ones we want, then compute their sum:

For numbers up-to $1000$, only 145 works:

Now let's use the bound we computed:

Problem 35: Circular primes

Now we have all the prime numbers up-to one million, and a constant-time way of checking if small numbers are prime.

Problem 36: Double-base palindromes

It's very easy to check if $n$ is a palindrome in base $10$:

It's also very easy to check if $n$ is a palindrome in base $2$:

Problem 37: Truncatable primes

The tricky part is to bound the largest number than can be a truncatable prime. The problem states that there are only eleven primes that are truncatable primes. How to find an upper bound on these numbers?

Well, one solution could just to enumerate prime numbers until we find 11 candidates, then stop. Let's cheat and do that.

That's a good sign, for prime numbers up-to a million we could not find the 12th truncatable prime.

Problem 38: Pandigital multiples

Well I wrote the code and my notebook froze so I lost everything... Not so motivated to start again.

The first thing to do is to mathematically bound the largest integer $x$ such that the product of $x$ by $1,\dots,n$ gives a 1-to-9 pandigital number.

Let's simply try them all.

Now we can just try all the possible values for $x$ and $n$ and keep a list of the candidates and return the largest one.

Problem 39: Integer right triangles

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120 : {20,48,52}, {24,45,51}, {30,40,50}

For which value of p ≤ 1000, is the number of solutions maximised?

Well there is no need to be smart here, we just need to try all the values $a,b,c=\sqrt{a^2+b^2}$ such that the longer slide is an integer, keep the list of values of p and the number of solutions, and find the p that maximize this number of solutions.

We could be much smarter in narrowing down the possible values for $a,b,c$, but we don't really need to.

So the answer is $p=840$, which have 8 solutions.

Problem 40: Champernowne's constant

Let's use a huge string and simply access its value at index $i=1,10,100,1000,10000,100000,1000000$. It will take some time but it'll work easily.

Now we can just build a huge string and access it.

Problem 41: Pandigital prime

If $p$ is a prime $n$-digit pandigital number, then $p$ is smaller than $n(n-1)..1$ (written in base $10$), eg with $n=5$, $p$ is smaller than $54321$. For $n=9$, the largest possible $9$-digit pandigital number is $987654321$. Let's build a Erathostene sieve of size $987654321+1$ and just check all the prime numbers for being $n$-digit pandigital, for $n=1$ to $n=9$. It won't be fast, but it'll work.

For 10 million primes, this takes about 3 seconds on my machine, thanks to Cython being faster than naive Python code.

For about 1 billion primes, this takes about 30 seconds on my machine, thanks to Cython being faster than naive Python code.

For about 10 billion primes, this should take about 15 minutes on my machine, thanks to Cython being faster than naive Python code.

Now we have a LARGE bool array to check in constant time if a number is prime, we can build the list of prime numbers up-to this $max_p = 987654321$.

Let's test if a number is 1-to-n pandigital.

Problem 32: Coded triangle numbers

Now we have these 1786 words.

Good, it wasn't that hard!

Problem 43: sub-string divisibility

Now we simply have to try all the 0-to-9 pandigital numbers, from 0123456789 (smallest) to 9876543210 (largest), and count the number of such numbers that satisfy this property.

It's easy to test all such pandigital numbers by using permutations of the string 0123456789, using itertools.permutations.

Problem 44: pentagon numbers

From the formula of $P_n = n(3n-1)/2$, it is clear that for any fixed $i$, $|P_{i+k}-P_i| = (i+k)(3(i+k)-1)/2 - i(3i-1)/2 = ( i(3i-1) + k(3i-1) + i(3k-1) + k(3k-1) - i(3i-1) )/2 = (k(3i-1) + i(3k-1) + k(3k-1))/2$ is an increasing function of $k$, and also for any fixed $k$, an increasing function of $i$.

Let's try naively to compute the first 1 million pentagonal numbers, put them in a set $\mathcal{P}$ then check if there are any $P_j,P_k$ (with $k > j$) that satisfy $P_j+P_k \in \mathcal{P}$ and $P_k - P_j \in \mathcal{P}$.

My intuition is that the solution that minimizes $D=|P_k-P_j|$ will be found within the first 1 million pentagonal numbers, so we don't need to mathematically bound the value of the largest $k,j$.

I got bored of waiting, and tadam the first solution is the good one!

Problem 45: Triangular, pentagonal, and hexagonal

Ideally, this problem will be easy to solve if there is a $\mathcal{O}(1)$ method to check if a number is a triangle, pentagonal and hexagonal number. I don't see an easy method, so let's just compute a lot of each of them, and try.

Now we can generate a set of a lot of triangle numbers, pentagonal numbers, hexagonal numbers, and find their intersection.

First, let's check that 40755=$T_{285}=P_{165}=H_{143}$ can indeed be found using this approach:

How can we know when to stop? I simply tried augmenting max_n until I found the next triangle number that is also pentagonal and hexagonal.

Problem 46: Goldbach's other conjecture

For 10 million primes, this takes about 3 seconds on my machine, thanks to Cython being faster than naive Python code.

It was that fast, about 24 seconds, but it's enough. There is surly plenty of solutions to solve this problem faster, but I don't care.

Problem 47: distinct primes factors

Now let's find the first number to have $x$ consecutive integers each having $y$ prime factors:

Now let's try with $x=y=2$ and $x=y=3$, to check the example given in the problem statement, before trying with $x=y=4$:

Now to answer the problem, let's compute for $x=y=4$:

Problem 49:

TODO

Continue