Project Euler by hand

The sum of the first \(n\) numbers is given by the triangular number formula

\[ 1 + 2 + \cdots + n = \sum_{k=1}^n k = \frac{n(n+1)}{2}. \]

Then we can easily find the sum of the first \(n\) numbers that are multiples of \(m\) by using

\[ m + 2m + \cdots + nm = m (1 + 2 + \cdots + n) = m \sum_{k=1}^n k = \frac{m n (n+1)}{2}. \]

In order to find the sum of multiples of \(3\) and \(5\) below \(1000\), we will find the sum of the multiples of \(3\) below \(1000\) and the sum of multiples of \(5\) below \(1000\). We will have double counted the multiples of \(3\) and \(5\), which are exactly the multiples of \(3 \cdot 5 = 15\), so we will "uncount" these once by substracting the sum of multiples of \(15\) below \(1000\).

There are \( \lceil 1000 / 3 \rceil - 1 = 333 \) multiples of \(3\) below \(1000\), \( \lceil 1000 / 5 \rceil - 1 = 199 \) multiples of \(5\) below \(1000\) and \( \lceil 1000 / 15 \rceil - 1 = 66 \) multiples of \(15\) below \(1000\). We ceil and substract one from this division because we are interested in the numbers strictly below \(1000\). If we only floored this division, we would get \( \lfloor 1000 / 5 \rfloor = 200 \) multiples of 5 below \(1000\), which is taking \(1000\) into account.

Therefore, the sums of multiples of 3, 5 and 15 are, respectively,

\[ \frac{3 \cdot 333 \cdot 334}{2} = 166833, \quad \frac{5 \cdot 199 \cdot 200}{2} = 99500, \quad \frac{15 \cdot 66 \cdot 67}{2} = 33165, \]

so the final answer is \(166833+99500-33165 = 233168\).

If the \(n\)-th term of the Fibonacci sequence is denoted as \(F_n\), the sum of the terms of the Fibonacci sequence from the \(a\)-th term to the \(b\)-th term, including these, is given by

\[ \sum_{n=a}^b F_n = F_{b+2} - F_{a+1}. \]

Instead of how the problem statement suggests, let's assume that the first and second Fibonacci term are \(F_1 = 1\) and \(F_2 = 1\). Then we have the following:

• The first two Fibonacci numbers are odd, therefore, the third Fibonacci number is \(F_3 = F_1 + F_2 = 1+1 = 2\), which is even since it's the sum of two odd numbers.
• The fourth Fibonacci number is \( F_4 = 1+2 = 3 \), which is odd since it's the sum of an even and an odd.
• The fifth Fibonacci number is \( F_5 = 2+3 = 5 \), which is odd since it's the sum of an odd and an even.
• The sixth Fibonacci number is \( F_6 = 3+5 = 8 \), which is even since it's the sum of two odd numbers.

From here, the pattern repeats and we see that the Fibonacci numbers follow this pattern: odd, odd, even, odd, odd, even, odd, odd, even... Because of this pattern and because each number is the sum of the previous two numbers, we see that the sum of the first \(n\) even numbers is the same as the sum of the odd numbers below those even numbers. For example, the sum of the first three even numbers in the Fibonacci sequence is

\begin{align*} 44 & = 2 + 8 + 34 = F_3 + F_6 + F_9 = \\ & = F_1 + F_2 + F_4 + F_5 + F_7 + F_8 = 1 + 1 + 3 + 5 + 13 + 21 = 44 \end{align*}

We see that the even numbers are at the positions in the Fibonacci sequence that are multiples of three, which will make our notation easier. The sum of the first \(n\) even Fibonacci numbers will be \( E_n := \sum_{k=1}^n F_{3k} \) and the sum of the odd Fibonacci numbers below these even numbers will be \( O_n := \sum_{k=1}^n F_{3k-2} + F_{3k-1} \). Since we have proven that these two are equal, we have that

\[ E_n = \tfrac{1}{2} (E_n + O_n) = \frac{1}{2} \sum_{k=1}^n F_{3k-2} + F_{3k-1} + F_{3k} = \frac{1}{2} \sum_{k=1}^{3n} F_k = \tfrac{1}{2} (F_{3n+2} - F_2). \]

We know \(F_2 = 1\), so \(E_n = \frac{1}{2} (F_{3n+2} - 1) \). It remains to find how many even numbers are there in the Fibonacci sequence under four million. Notice that \(3n\) is the position of the last even number we are considering, so we just have to find the position of the biggest even number under four million and this position will be \(3n\). Looking at a list of the Fibonacci sequence from the OEIS, we see that this highest even number is \( F_{33} = 3524578 \), while \( F_{34} = 5702887 \) exceeds four million. Then, we have that \( 3n = 33 \); there are 11 even Fibonacci numbers under four million; and the sum we are looking for is

\[ E_{11} = \tfrac{1}{2} (F_{35} - 1) = \tfrac{1}{2} (9227465 - 1) = \tfrac{1}{2} \cdot 9227464 = 4613732 \]

and this is our final answer.

The biggest product of two \(3\)-digit numbers is \(999 \cdot 999 = 998001\), so the best we can hope for is a \(6\)-digit number. Let's see that any \(6\)-digit palindromic number is a multiple of \(11\). If we write this number as \(\underline{abccba}\), where \(a,b,c \in \{0,1,\dots,9\}\) and the underlining means that this is the number's decimal representation, then,

\[ \underline{abccba} = 100001 a + 10010 b + 1100 c = 11 \cdot (9091 a + 910 b + 100 c), \]

so \(\underline{abccba}\) is a multiple of \(11\). Therefore, if \(x\) and \(y\) are the two \(3\)-digit numbers such that \(x y = \underline{abccba}\), we can assume that \(y\) is a multiple of \(11\).

The largest \(3\)-digit multiple of \(11\) is \(990 = 11*90\), but notice that its last digit is \(0\), so the first digit of \(xy\), which is \(a\), will also be \(0\). We don't want this, since this will mean that the most significant digit of our palindromic number will be \(0\) and it will be small. It won't even be a \(6\)-digit number. Actually, we don't immediately know if there are any \(6\)-digit palindromic numbers that don't start with \(0\), so it is possible that we should be looking at \(5\)-digit numbers instead. However, we can easily find \(11^4 = 121 \cdot 121 = 14641\), which is a \(6\)-digit palindromic number and a product of two \(3\)-digit numbers, so we at least know that we are on the right path.

Let's be greedy and try to look for a \(6\)-digit palindromic number with \(a = 9\). So, if \(y = 990\) isn't good, let's try the previous multiple of \(11\), which is \(y = 11 \cdot 89 = 979\). Since its last digit is \(9\), we want the last digit of \(x\) to be \(1\) so we get \(a = 9\). Then, we have \(90\) possible choices for the value of \(x\), from \(101\) to \(991\). However, we notice that \(911 \cdot 979 = 891869\) and \(921 \cdot 979 = 901659\), so our only choices for \(x\) are \(921,931,941,951,961,971,981\) and \(991\), since anything smaller than \(x = 921\) won't make \(xy\) have \(9\) at it's first digit. Let's check all these values for palindromic numbers:

\begin{array}{c|c} x & x y = 979 x \\ \hline 991 & 991 \cdot 979 = 970189 \\ 981 & 981 \cdot 979 = 960399 \\ 971 & 971 \cdot 979 = 950609 \\ 961 & 961 \cdot 979 = 940819 \\ 951 & 951 \cdot 979 = 931029 \\ 941 & 941 \cdot 979 = 921239 \\ 931 & 931 \cdot 979 = 911449 \\ 921 & 921 \cdot 979 = 901659 \end{array}

No luck, so let's try lower multiples of \(11\). The next one is \(y = 11 \cdot 88 = 968\), but notice that we don't want even multiples since we won't be able to get \(a = 9\) with these for similar reasons that we didn't want \(y = 990\). So the next multiple is \(y = 11 \cdot 87 = 957\). since \(7\cdot 7 = 49\), we want the last digit of \(x\) to be \(7\), and since \(937 \cdot 957 = 896709\) and \(947 \cdot 957 = 906279\), our choices for \(x\) are \(947, 957, 967, 977, 987\) and \(997\):

\begin{array}{c|c} x & x y = 957 x \\ \hline 997 & 997 \cdot 957 = 954129 \\ 987 & 987 \cdot 957 = 944559 \\ 977 & 977 \cdot 957 = 934989 \\ 967 & 967 \cdot 957 = 925419 \\ 957 & 957 \cdot 957 = 915849 \\ 947 & 947 \cdot 957 = 906279 \end{array}

No luck either, so the next candidate for \(y\) is \(y = 11 \cdot 85 = 935\), but this isn't good either since we can't get \(a = 9\) if the last digit of \(y\) is \(5\). So the next candidate is \(y = 11 \cdot 83 = 913\), which means that \(x\) should have \(3\) as its last digit. This time, \(983 \cdot 913 = 897479\), so the only candidate is \(993 \cdot 913 = 906609\), which is palindromic!

We've found our first palindromic number. Can we be sure that it is the largest one that is a product of two \(3\)-digit numbers? There might be a lower choice of \(y\) but higher choice of \(x\) that also get us a palindromic number that is higher. However, we see that this is impossible, since the next choice of \(y\) is \(y = 11 \cdot 81 = 891\), which has \(999 \cdot 891 = 890109\), so no lower choices of \(y\) can give us a palindromic number that starts with a \(9\).

We have exhausted all possibilities to find a palindromic number that starts with a \(9\) and the only one we've found is \(906609\), which is our final answer.

This is simply the least common multiple of the numbers from \(1\) to \(20\). Let \(p_n\) be the \(n\)-th prime number. If we have numbers \(a_1,a_2,\dots,a_m \in \mathbb N\) which we factorize as \(a_k = p_1^{\alpha_k^{(1)}} p_2^{\alpha_k^{(2)}} p_3^{\alpha_k^{(3)}} \cdots \) for certain (finitely non-zero) \(\alpha_k^{(1)},\alpha_k^{(2)},\dots \in \mathbb N\), we have that the least common multiple of \(a_1,a_2,\dots,a_m\) is given by

\[ \mathrm{lcm}(a_1,a_2,\dots,a_m) = \prod_{n=1}^\infty p_n^{\max_{k=1}^m \alpha_k^{(n)}}. \]

That is, we take the highest exponent of each prime number in the factorizations of \(a_1,a_2,\dots,a_m\). The greatest common divisor follows a similar formula, where we take the lowest exponents instead. Therefore, we need to factorize the numbers from \(1\) to \(20\) and find these largest exponents. In the following table, each row represents a prime number and each cell represents the exponent of that prime number found in the factorization of the column's number. We've left a blank cell instead of writing zeroes. At the right, we have the largest exponent of each row.

\[ \begin{array}{r|cccccccccccccccccccc|c} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & \\ \hline 2 & & 1 & & 2 & & 1 & & 3 & & 1 & & 2 & & 1 & & 4 & & 1 & & 1 & 4 \\ 3 & & & 1 & & & 1 & & & 2 & & & 1 & & & 1 & & & 2 & & & 2 \\ 5 & & & & & 1 & & & & & 1 & & & & & 1 & & & & & 1 & 1 \\ 7 & & & & & & & 1 & & & & & & & 1 & & & & & & & 1 \\ 11& & & & & & & & & & & 1 & & & & & & & & & & 1 \\ 13& & & & & & & & & & & & & 1 & & & & & & & & 1 \\ 17& & & & & & & & & & & & & & & & & 1 & & & & 1 \\ 19& & & & & & & & & & & & & & & & & & & 1 & & 1 \\ \end{array} \]

Therefore, the number we are looking for is

\[ \mathrm{lcm}(1,2,\dots,20) = 2^4 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 = 232792560 \]

and this is our final answer

The sum of the first \(n\) numbers is given by the triangular number formula \( \sum_{k=1}^n k = \frac{n (n+1)}{2} \). On the other hand, the sum of the squares of the first \(n\) numbers has a similar but slightly more complicated formula:

\[ 1^2 + 2^2 + \cdots + n^2 = \sum_{k=1}^n k^2 = \frac{n (n+1) (2n+1)}{6}. \]

Therefore, the difference between the sum of squares and the square of the sum of the first \(n\) numbers is given by

\begin{align*} \left( \sum_{k=1}^n k \right)^2 - \sum_{k=1}^n k^2 & = \left( \frac{n (n+1)}{2} \right)^2 - \frac{n (n+1)(2n+1)}{6} = \\ & = \tfrac{1}{12} (3 n^2 (n+1)^2 - 2 n (n+1) (2n+1)) = \\ & = \frac{n(n+1)}{12}(3n(n+1) - 2(2n+1)) = \\ & = \frac{n(n+1)}{12}(3n^2 +3n - 4n - 2) = \\ & = \frac{n (n+1) (3n^2 - n - 2)}{12} = \frac{n (n+1)(3n+2)(n-1)}{12}. \end{align*}

So, substituting with \(n=100\), we obtain

\[\frac{100 \cdot 101 \cdot 302 \cdot 99}{12} = \frac{301969800}{12} = 25164150, \]

which is our final answer.

Every Pythagorean triplet can be written as

\[ (a,b,c) = (d (m^2-n^2),2 d m n, d (m^2+n^2)) \]

\[ a+b+c = d(m^2-n^2) + 2 dmn + d(m^2 + n^2) = 2 d m^2 + 2 d m n = 1000 \Longrightarrow d m(m + n) = 500 \]

We can write \(d m (m+n) = 500 = 2^2 \cdot 5^3\). This number doesn't have many divisors, only twelve, so we can check them one by one. All the possible divisors of \(500\) and therefore values of \(d\) and \(m\) are \(1, 2, 4, 5, 10, 20, 25, 50, 100, 125, 250, 500\). Some combinations of \(d\) and \(m\) with these values are not valid, since \(d m\) would stop being a divisor of \(500\). For example, \(d = 20\) and \(m = 2\) would give \(dm = 40\), which is not a divior of \(500\). Checking all the valid choices of \(d\) and \(m\), we obtain the corresponding values of \(n = 500/(dm) - m\):

\begin{array}{r|cccccccccccc} & 1 & 2 & 4 & 5 & 10 & 20 & 25 & 50 & 100 & 125 & 250 & 500 \\ \hline 1 & 499 & 248 & 121 & 95 & 40 & \textcolor{red}{5} & -5 & -40 & -195 & -121 & -248 & -499 \\ 2 & 249 & 123 & & 45 & 15 & & -15 & -45 & & -123 & -249 & \\ 4 & 124 & & & 20 & & & -20 & & & -124 & & \\ 5 & 99 & 48 & 21 & 15 & 0 & -15 & -21 & -48 & -99 & & & \\ 10 & 49 & 23 & & 5 & -5 & & -23 & -49 & & & & \\ 20 & 24 & & & 0 & & & -24 & & & & & \\ 25 & 19 & 8 & \textcolor{red}{1} & -1 & -8 & -19 & & & & & & \\ 50 & 9 & 3 & & -3 & -9 & & & & & & & \\ 100 & 4 & & & -4 & & & & & & & & \\ 125 & 3 & 0 & -3 & & & & & & & & & \\ 250 & 1 & -1 & & & & & & & & & & \\ 500 & 0 & & & & & & & & & & & \\ \end{array}

Here each column corresponds to a value of \(m\) and each row to a value of \(d\). Marked in red are the only two combinations such that \(m > n > 0\). Both give the same triplet, since if \(d=1\), \(m=20\) and \(n = 5\), we have

\[ a = d (m^2-n^2) = 1 \cdot (20^2-5^2) = 375, \quad b = 2 d m n = 2 \cdot 1 \cdot 20 \cdot 5 = 200, \quad c = d (m^2 + n^2) = 1 \cdot(20^2 + 5^2) = 425, \]

and if \(d=25\), \(m=4\) and \(n=1\), we have

\[ a = d (m^2-n^2) = 25 \cdot (4^2-1^2) = 375, \quad b = 2 d m n = 2 \cdot 25 \cdot 4 \cdot 1 = 200, \quad c = d (m^2 + n^2) = 25 \cdot(4^2 + 1^2) = 425 \]

These three numbers clearly have \(a+b+c = 500\) and \(a^2 + b^2 = 180625 = c^2 \). Therefore, our answer is

\[ a b c = 375 \cdot 200 \cdot 425 = 31875000 \]

For each possible ordering of these steps there is one path; and for each possible path there is one order. Choosing a path and choosing an ordering is equivalent. Therefore the number of possible routes on a \(n \times n\) grid is the number of possible orders to be chosen. In this choice, we must choose to place \(n\) steps down and \(n\) steps right in a sequence of \(2n\) steps, so this number of choices is given by the combination formula \( \binom{2n}{n} = \frac{(2n)!}{n! n!} \). Therefore, we have that the number of possible routes in a \(20 \times 20\) grid is

\[ \binom{40}{20} = \frac{40!}{20! 20!} = \frac{21 \cdot 22 \cdot \cdots \cdot 40}{1 \cdot 2 \cdot \cdots \cdot 20} = 137846528820 \]

and this is our final answer.

When considering the permutations of \(n\) digits, there is a total of \(n!\) permutations and \((n-1)!\) permutations that start by each digit. The first \((n-1)!\) permutations start with \(0\), the next \((n-1)!\) start with \(1\), and so on.

Considering that the permutations start at the \(0\)th place, we have to find the \(999999\)th permutation. We can find the representation of this permutation using the following algorithm:

• To find the first digit of the \(m\)-th permutation, write \(m = a \cdot (n-1)! + b \) with \(a,b \in \mathbb N\) and \(b < (n-1)!\). The first digit of the permutation will be \(a\).
• Cross out \(a\) off your list of reminding digits.
• The second digit of the \(m\)-th permutation will be the first digit of the \(b\)-th permutation of the reminding digits. In fact, the rest of the permutation you haven't found is the \(b\)-th permutation of the reminding digits.
• Repeat until you've found all digits.

For example, to find the third, permutation of the digits \(0\), \(1\) and \(2\), we write \(2 = 1 \cdot (3-1)! + 0 \) (remember, we use \(2\) instead of \(3\) because we start at the \(0\)th permutation). Then, the first digit of our permutation will be \(1\). The second digit will be the first digit of the \(0\)th permutation of \(0\) and \(2\), so we write \(0 = 0 \cdot (2-1)! + 0\) and the second digit is \(0\). The only remaining digit is \(2\), which is also the \(0\)th permutation of the digit \(2\). Therefore, the third permutation of \(0\), \(1\) and \(2\) is \(102\), as we see in the problem statement.

Let's repeat this process but for \(9\) digits and the \(999999\)th permutation:

\begin{array}{c|ccc|c} n & (n-1)! & m = a \cdot (n-1)! + b & \text{digit} & 0123456789 \\ \hline 10 & 362880 & 999999 = 2 \cdot 362880 + 274239 & 2 & 01\phantom{2}3456789 \\ 9 & 40320 & 274239 = 6 \cdot 40320 + 32319 & 7 & 01\phantom{2}3456\phantom{7}89 \\ 8 & 5040 & 32319 = 6 \cdot 5040 + 2079 & 8 & 01\phantom{2}3456\phantom{78}9 \\ 7 & 720 & 2079 = 2 \cdot 720 + 639 & 3 & 01\phantom{23}456\phantom{78}9 \\ 6 & 120 & 639 = 5 \cdot 120 + 39 & 9 & 01\phantom{23}456\phantom{789} \\ 5 & 24 & 39 = 1 \cdot 24 + 15 & 1 & 0\phantom{123}456\phantom{789} \\ 4 & 6 & 15 = 2 \cdot 6 + 3 & 5 & 0\phantom{123}4\phantom{5}6\phantom{789} \\ 3 & 2 & 3 = 1 \cdot 2 + 1 & 4 & 0\phantom{12345}6\phantom{789} \\ 2 & 1 & 1 = 1 \cdot 1 + 1 & 6 & 0\phantom{123456789} \\ 1 & 1 & 0 = 0 \cdot 1 + 0 & 0 & \end{array}

So the millionth permutation is \(2783915460\).