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\).

- dino (2025/03/11)

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.

- dino (2025/03/11)

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.

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.

- dino (2025/03/15)

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

- dino (2025/03/11)

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.

- dino (2025/03/11)

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 \]

- dino (2025/03/14)

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.

- dino (2025/03/11)

This problem requires checking the Sundays of \(100\) years, which is not completely impossible to do manually. Let's be a bit smarter than this. Two years that both start on the same day of the week and are both not leap years (or are both leap years) will have identical calendars, so maybe we can find and exploit some periodicity in the calendars of the 20th century to simplify this for us.

First, in order to find how many Sundays fall on the first of the month in a year, we'll keep track of what day of the week is the first of each month. For a non-leap year, we have

\[ \begin{array}{r|cccccccccccc|c} \text{Month} & Ja & F & Mr & Ap & My & Jn & Jl & Au & S & O & N & D & \\ \hline \text{Days in each month} & 31 & 28 & 31 & 30 & 31 & 30 & 31 & 31 & 30 & 31 & 30 & 31 & \\ \text{Days} \pmod 7 & 3 & 0 & 3 & 2 & 3 & 2 & 3 & 3 & 2 & 3 & 2 & 3 & \\ \text{Cum. Sum} \pmod 7 & 0 & 3 & 3 & 6 & 1 & 4 & 6 & 2 & 5 & 0 & 3 & 5 & 1 \end{array} \]

The last row of this table is the day of the week that the corresponding month starts on (with respect to the day of the week the year started on). The middle row is the remainder of dividing the number of days in each month by \(7\), which makes the calculation of the last row easier. For example, 1900 started on a Monday, so its May started on a Tuesday since \(0\) is Monday and \(1\) is Tuesday for 1900. For leap years, the number of days in February changes and so does the rest of the last row after February:

\[ \begin{array}{r|cccccccccccc|c} \text{Month} & Ja & F & Mr & Ap & My & Jn & Jl & Au & S & O & N & D & \\ \hline \text{Days in each month} & 31 & 29 & 31 & 30 & 31 & 30 & 31 & 31 & 30 & 31 & 30 & 31 & \\ \text{Days} \pmod 7 & 3 & 1 & 3 & 2 & 3 & 2 & 3 & 3 & 2 & 3 & 2 & 3 & \\ \text{Cum. Sum} \pmod 7 & 0 & 3 & 4 & 0 & 2 & 5 & 0 & 3 & 6 & 1 & 4 & 6 & 2 \end{array} \]

This way, we see that 1904, which was a leap year and started on a Thursday, had its July starting also on a Thursday, since July has its last row's number be \(0\).

The last number of both tables lets us know what day of the week the next year will start on. Since a non-leap year will have \(365\) days, the next year's calendar is displaced \(365 \bmod 7 = 1 \) days, while a leap year displaces the following year by \(366 \bmod 7 = 2\) days.

Now, if a non-leap year starts on a Sunday, it will have two Sundays falling on the first of the month, since there are two zeroes (that will correspond to Sundays) on the last row of the non-leap year table. If it starts on a Monday, Sundays will correspond to \(6\), so there will be two Sundays falling on the first of the month since there are also two sixes on the row. Therefore, we can construct the following table that counts the Sundays that fall on the first of the month depending on which day the year starts on (I don't personally like considering that weeks start on Sunday, but it is convenient in this case):

\begin{array}{r|ccccccc} \text{First day of the year} & Su & M & Tu & W & Th & F & Sa \\ \text{Number corresponding to Sunday} & 0 & 6 & 5 & 4 & 3 & 2 & 1 \\ \hline \text{Sundays on a non-leap year} & 2 & 2 & 2 & 1 & 3 & 1 & 1 \\ \text{Sundays on a leap year} & 3 & 2 & 1 & 2 & 2 & 1 & 1 \end{array}

We've simply counted the numbers corresponding to Sundays on the previous two tables to build this table. Therefore, we can start counting the number of Sundays in each year from 1901 until we find a pattern using this table:

\[ \begin{array}{c|ccc} \text{Year} & \text{Was leap year?} & \text{Started on} & \text{Sundays} \\ \hline 1901 & \text{No} & Tu & 2 \\ 1902 & \text{No} & W & 1 \\ 1903 & \text{No} & Th & 3 \\ 1904 & \text{Yes} & F & 1 \\ 1905 & \text{No} & Su & 2 \\ 1906 & \text{No} & M & 2 \\ 1907 & \text{No} & Tu & 2 \\ 1908 & \text{Yes} & W & 2 \\ 1909 & \text{No} & F & 1 \\ 1910 & \text{No} & Sa & 1 \\ 1911 & \text{No} & Su & 2 \\ 1912 & \text{Yes} & M & 2 \\ 1913 & \text{No} & W & 1 \\ 1914 & \text{No} & Th & 3 \\ 1915 & \text{No} & F & 1 \\ 1916 & \text{Yes} & Sa & 1 \\ \end{array} \hspace{8em} \begin{array}{c|ccc} \text{Year} & \text{Was leap year?} & \text{Started on} & \text{Sundays} \\ \hline 1917 & \text{No} & M & 2 \\ 1918 & \text{No} & Tu & 2 \\ 1919 & \text{No} & W & 1 \\ 1920 & \text{Yes} & Th & 2 \\ 1921 & \text{No} & Sa & 1 \\ 1922 & \text{No} & Su & 2 \\ 1923 & \text{No} & M & 2 \\ 1924 & \text{Yes} & Tu & 1 \\ 1925 & \text{No} & Th & 3 \\ 1926 & \text{No} & F & 1 \\ 1927 & \text{No} & Sa & 1 \\ 1928 & \text{Yes} & Su & 3 \\ 1929 & \text{No} & Tu & 2 \\ 1930 & \text{No} & W & 1 \\ 1931 & \text{No} & Th & 3 \\ 1932 & \text{Yes} & F & 1 \\ \end{array} \]

Maybe it's taken a bit long, but notice that 1929 started on a Tuesday and came after a leap year. This would have been the same thing that would have happened on 1901 if 1900 had been a leap year, but it wasn't cause it was a multiple of 100 and not of 400. Regardless, 1091 and 1929 behaved the exact same and had the same position in the "No, No, No, Yes" pattern of leap years. Because there were no more exceptions of leap years in the 20th century like there were in 1900, this pattern of 28 years between 1901 and 1928 starts again on 1929.

This pattern went on from 1901 to 1928; from 1929 to 1956; from 1957 to 1984; and from 1985 to 2012 (2000 was a leap year). Therefore, adding up the Sundays on the table from 1901 to 1928, we get \(48\) Sundays in each cycle, so a total of \(48*3 = 144\) Sundays from 1901 to 1984. We also know that the sixteen years from 1985 to 2000 were identical to the years from 1901 to 1916, so adding up the Sundays from 1901 to 1916 we get \(27\) Sundays from 1985 to 2000.

In total, there were \(144 + 27 = 171\) Sundays from 1901 to 2000, which is our final answer.

- dino (2025/04/04)

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\).

- dino (2025/03/14)

If \(\phi = \frac{1 + \sqrt 5}{2} \approx 1.618\) is the golden ratio, Binet's formula tells us that

\[ F_n = \frac{\phi^n - \left( 1 - \phi \right)^n}{\sqrt 5}, \]

where \(1 - \phi = \frac{-1}{\phi} = \frac{1 - \sqrt 5}{2} \approx -0.618\). Since \(1-\phi \in (-1,1)\), we have that \( \lim_{n \to \infty} (1-\phi)^n = 0 \). In fact, this term is negligible and we can consider the approximation \(F_n \approx \phi^n / \sqrt 5\), which will only get better as \(n\) grows. In fact, already at \(n=4\) we have that \(\phi^4 / \sqrt 5 \approx 3.0652 \approx 3 = F_4\).

Now, any number \(m \in \mathbb N\) with \(d\) digits has that \(10^{d-1} \leq m < 10^d\), so \(d-1 \leq \log_{10} m < d\). On the other hand, we have that

\[ \log_{10} F_n \approx \log_{10}\left(\frac{\phi^n}{\sqrt 5}\right) = n \log_{10} \phi - \tfrac{1}{2} \log_{10} 5. \]

Therefore, if \(F_n\) has \(d\) digits, we have that, for large enough values of \(n\),

\[ d-1 \leq n \log_{10} \phi - \tfrac{1}{2} \log_{10} 5 < d \]

\[ \frac{d-1 + \tfrac{1}{2} \log_{10} 5}{\log_{10} \phi} \leq n < \frac{d + \tfrac{1}{2} \log_{10} 5}{\log_{10} \phi}. \]

Using this formula, we can find the first integer value of \(n\) immediately above \(\frac{d-1 + \tfrac{1}{2} \log_{10} 5}{\log_{10} \phi}\) to find the first Fibonacci number with \(d\) digits. For example, using \(d = 3\), we obtain

\[ \frac{d-1 + \tfrac{1}{2} \log_{10} 5}{\log_{10} \phi} = \frac{2 + \tfrac{1}{2} \log_{10} 5}{\log_{10} \phi} \approx 11.24, \]

so the first Fibonacci number with \(3\) digits is the \(12\)^th one, as the statement says. Using \(d = 1000\), we have

\[ \frac{d-1 + \tfrac{1}{2} \log_{10} 5}{\log_{10} \phi} = \frac{999 + \tfrac{1}{2} \log_{10} 5}{\log_{10} \phi} \approx 4781.86, \]

hence our final answer is that the first term to contain \(1000\) digits is the \(4782\)^th one.

- dino (2025/03/14)

We can number each "layer" of the spiral with a number \(n\): the center \(1\) being layer \(0\), the \(3\) by \(3\) square being layer \(1\), the \(5\) by \(5\) square being layer \(2\) and so on...

\[ \begin{array}{ccccc} {\color{red}1} & \qquad & \begin{array}{ccc} {\color{red}7} & 8 & {\color{red}9} \\ 6 & & 2 \\ {\color{red}5} & 4 & {\color{red}3} \end{array} & \qquad & \begin{array}{ccccc} {\color{red}21} & 22 & 23 & 24 & {\color{red}25} \\ 20 & & & & 10 \\ 19 & & & & 11 \\ 18 & & & & 12 \\ {\color{red}17} & 16 & 15 & 14 & {\color{red}13} \end{array} \\ n = 0 & & n = 1 & & n = 2 \end{array} \]

Except for the \(0\)^th layer, every layer has \(8n\) numbers and has the following structure:

\[ \begin{array}{ccccc} {\color{red}6n} & 6n+1 & 6n+2 & \cdots & {\color{red}8n} \\ \vdots & & & & 1 \\ 4n+2 & & & & 2 \\ 4n+1 & & & & \vdots \\ {\color{red}4n} & \cdots & 2n+2 & 2n+1 & {\color{red}2n} \end{array} \]

We have written this structure starting at \(1\), but really each layer starts at a certain number \(s_n+1\) (it is more convenient to say that \(s_n\) is the end of the previous layer instead of the start of the \(n\)^th layer). Therefore, the layers in the spiral can be constructed by adding \(s_n\) to each number in the pattern we have shown. Because of this, the corners of each layer are \(2n + s_n\), \(4n + s_n\), \(6n + s_n\) and \(8n + s_n\). In total, each layer adds \(2n + 4n + 6n + 8n + 4s_n = 20 n + 4 s_n\) to the total of the diagonal sum.

Now, \(s_n\) is the number that the previous layer ends at, which is the "size" of all the layers that come before the \(n\)^th layer. The side length of each layer is \(2n+1\), so the previous layer has side length \(2n-1\) and, since it forms a square, it has \((2n-1)^2\) numbers inside it, which will be our \(s_n\). We could have also seen that \(s_n = 1 + \sum_{k=1}^{n-1} 8k\). Therefore, the contribution of each layer (except the center one) to the total sum is

\[ 20 n + 4s_n = 20 n + 4 (2n-1)^2 = 20n + 16 n^2 - 16 n + 4 = 4 (4 n^2 + n + 1) \]

If we have a spiral with layers up to the \(N\)^th layer, the sum of the diagonals of this spiral can be written as

\begin{align*} 1 + \sum_{n=1}^N 4 (4n^2 + n + 1) & = 1 + 16 \sum_{n=1}^N n^2 + 4 \sum_{n=1}^N n + 4 \sum_{n=1}^N 1 = \\ & = 1 + \tfrac{8}{3} N (N+1) (2N+1) + 2 N (N+1) + 4N = \\ & = \tfrac{1}{3} (16 N^3 + 30 N^2 + 26 N + 3) \end{align*}

We see that our \(5\) by \(5\) spiral had layers from \(n=0\) to \(n=2\), so it had \(N=2\) and the sum of its diagonals was

\[ \tfrac{1}{3} (16 \cdot 2^3 + 30 \cdot 2^2 + 26 \cdot 2 + 3) = \tfrac{1}{3} (128 + 120 + 52 + 3) = \frac{303}{3} = 101 \]

which is what the statement says. Now, the \(1001\) by \(1001\) spiral has layers up to \(N=500\) (an \(L\) by \(L\) spiral will have \(N=\tfrac{1}{2} (L-1)\)). Therefore, its diagonals add up to

\begin{align*} \tfrac{1}{3} (16 \cdot 500^3 & + 30 \cdot 500^2 + 26 \cdot 500 + 3) = \\ & = \tfrac{1}{3} (2000000000 + 7500000 + 13000 + 3) = \\ & = \frac{2007513003}{3} = 669171001 \end{align*}

which is our answer. We can also rewrite the polynomial as \(\tfrac{1}{6} (4 L^3 + 3L^2 + 8L - 9)\) after substituting with \(L = 2N+1\), and this new polynomial gives the same solution at \(L=1001\).

- dino (2025/04/10)

The pattern in Champernowne's constant is simple and it's possible to find an arbitrary digit by hand. We can divide the decimal representation of the constant in sections by the number of digits in the integers we are concatenating: The first nine decimal digits of the constant are the nine digits from \(1\) to \(9\), while the following \(180\) decimals of the constant are the digits of the integers from \(10\) to \(99\). We know there are \(90\) numbers of two digits, since together with the one-digit numbers they make up the integers from \(1\) to \(99\).

We can follow this pattern and reason that there are \(9 \cdot 10^{n-1}\) integers with \(n\) digits, which require \(9 n \cdot 10^{n-1}\) digits to be written down in Champernowne's constant. Therefore, the \(n\)-digit section starts at the position given by \(1 + \sum_{m=1}^{n-1} 9m \cdot 10^{m-1}\) (we add \(1\) because the first digit is \(d_1 = 1\)). That is, the one-digit section starts at position \(1\); the two-digit section starts at position \(1+9 = 10\); the three-digit section starts at position \(1+9+180 = 190\) and so on:

\begin{array}{ccc} \text{Digits} & \text{Section size} & \text{Section start} \\ \hline 1 & 9 \cdot 1 \cdot 10^0 = 9 & 1 \\ 2 & 9 \cdot 2 \cdot 10^1 = 180 & 10 \\ 3 & 9 \cdot 3 \cdot 10^2 = 2700 & 190 \\ 4 & 9 \cdot 4 \cdot 10^3 = 36000 & 2890 \\ 5 & 9 \cdot 5 \cdot 10^4 = 450000 & 38890 \\ 6 & 9 \cdot 6 \cdot 10^5 = 5400000 & 488890 \\ 7 & 9 \cdot 7 \cdot 10^6 = 63000000 & 5888890 \\ \end{array}

The seven-digit section starts at position \(5888890\), which is greater than \(1000000\), the position of the last digit the question asks to find, so we can stop here and we know that the \(1000000\)^th digit falls in the six-digit section.

Now, once we know the position of a digit, we can know its position inside of the section it falls in by looking at the previous table. If we are looking at the digit in position \(m\) and it falls in the \(n\)-digit section, which starts at position \(s\), we'll know that this digit corresponds to the \(\lfloor (m-s) / n \rfloor\)^th integer in this section and will be the digit at position \((m-s) \bmod n\) of this integer, its \(0\)^th digit being the most-significant. We need to take into account that the \(0\)^th integer in the \(n\)-digit section corresponds to \(10^{n-1}\), so the integer corresponding to the \(m\)^th digit is \(\lfloor (m-s) / n \rfloor + 10^{n-1}\).

For example, \(d_1\) falls in the one-digit section and is the \((1-1) \bmod 1 = 0\)^th digit of the integer \(\lfloor (1-1) / 1 \rfloor + 10^0 = 1 \), so \(d_1 = 1\). Next, \(d_{10}\) falls in the two-digit section and is the \((10-10) \bmod 2 = 0\)^th digit of the integer \(\lfloor (10-10) / 2 \rfloor + 10^1 = 10 \), so \(d_{10} = 1\). Next, \(d_{100}\) also falls in the two-digit section and is the \((100-10) \bmod 2 = 0\)^th digit of the integer

\[ \left\lfloor \frac{100-10}{2} \right\rfloor + 10^1 = 45 + 10 = 55, \]

so \(d_{100} = 5\). We can find the rest of the digits with this method:

\[ \begin{array}{c|c|c|c|c} m & n \text{ (Section)} & m-s \text{ (Position in section)} & \text{Integer} & d_m \\ \hline 1 & 1 & 1-1 = 0 = 0 \cdot 1 + 0 & {\color{red}1} & 1 \\ 10 & 2 & 10 - 10 = 0 = 0 \cdot 2 + 0 & {\color{red}1}0 & 1 \\ 100 & 2 & 100 - 10 = 90 = 45 \cdot 2 + 0 & {\color{red}5}5 & 5 \\ 1000 & 3 & 1000 - 190 = 810 = 270 \cdot 3 + 0 & {\color{red}3}70 & 3 \\ 10000 & 4 & 10000 - 2890 = 7110 = 1777 \cdot 4 + 2 & 27{\color{red}7}7 & 7 \\ 100000 & 5 & 100000 - 38890 = 61110 = 12222 \cdot 5 + 0 & {\color{red}2}2222 & 2 \\ 1000000 & 6 & 1000000 - 488890 = 511110 = 85185 \cdot 6 + 0 & {\color{red}1}85185 & 1 \\ \end{array} \]

Therefore, our solution is \(1 \cdot 1 \cdot 5 \cdot 3 \cdot 7 \cdot 2 \cdot 1 = 210\).

- dino (2025/04/04)

We can make use of Euler's totient function's properties to solve this problem. For a start, it is multiplicative, which in the context of number theory means that \(\phi(n m) = \phi(n) \phi(m)\) if \(n\) and \(m\) are coprime numbers. For example, \(\phi(6) = \phi(2) \phi(3) = 1 \cdot 2 = 2\), so \(6 / \phi(6) = 3\). Another thing we notice is that every number under a prime number \(p\) is relatively prime with \(p\), so \(\phi(p) = p-1\) and \(p / \phi(p) = 1 + \frac{1}{p-1}\).

But most importantly, we notice that when we multiply a number \(n\) by one of its prime factors \(p\), the resulting ration \(np / \phi(np)\) is the same as \(n / \phi(n)\). This is because there are \(\phi(n)\) numbers relatively prime to \(n p\) from \(1\) to \(n\); there are \(\phi(n)\) relatively prime numbers from \(n+1\) to \(2n\); and so on: there are \(\phi(n)\) relatively prime numbers in every interval \(kn+1\) to \((k+1) n\), and since there are \(p\) of these intervals, \( \phi(np) = \phi(n) p \), so \(np / \phi(np) = np / (\phi(n) p) = n / \phi(n)\). For example, \(\phi(6) = 2\), \(\phi(12) = 4\) and \(\phi(18) = 6\), and these three numbers have the same ratio \(n / \phi(n) = 3\).

Therefore, if we factorize a number \(n\), we don't care about the exponents over its prime factors, but just what prime factors it has. Since \(p / \phi(p) = 1 + \frac{1}{p-1}\) is greater than \(1\) but also decreases as \(p\) increases, we want this number \(n\) to have many prime factors and for these prime numbers to be small. If one of these factors is raised to some power different than \(1\), we are making \(n\) unnecessarily large and we might be loosing the chance to add more prime factors. Therefore, the ideal number would be one like \(2 \cdot 3 \cdot 5 \cdot 7\), the product of succesive prime numbers. These numbers are called the primorials. A list of the first primorials can be found in the OEIS as sequence A002110.

We can see that \(2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 = 510510\), while the next primorial is \(510510 \cdot 19 = 9699690\), which is greater than \(1000000\). Therefore, our answer is \(510510\), which has \(\phi(510510) = 92160\) and \(510510/\phi(510510) = 510510/92160 \approx 5.5394\).

- dino (2025/04/07)