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 \cdot 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 & & 2 & 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 divisor 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 = 1000\) 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!} \). On a \(2 \times 2\) grid, there will be \(\binom42 = \frac{4!}{2! 2!} = \frac{24}{2 \cdot 2} = 6 \) routes, as the problem statement shows. Therefore, we have that the number of possible routes on 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 \cdot 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 remaining digits.
• The second digit of the \(m\)^th permutation will be the first digit of the \(b\)^th permutation of the remaining 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 problem statement seems to imply that fractions like \(\frac{11}{22}=\frac12\) are not trivial, but this is clearly not the case, since there are more than four of these. In fact, let's see that all these non-trivial fractions are of the form \(\frac{10a + c}{10c + b} = \frac{a}{b}\).

If they were of the form \(\frac{10a + c}{10b + c} = \frac{a}{b}\), we would have that

\[ (10a + c) b = (10b+c) a \Longrightarrow 10ab + bc = 10ab + ac \Longrightarrow bc = ac. \]

If \(c=0\), then the fraction would be of the form \(\frac{10a}{10b} = \frac{a}{b}\), which we already know is a trivial solution. If \(c \neq 0\), then we will have that \(a=b\) and the fraction is of the form \(\frac{10a+c}{10a+c} = \frac{a}{a}\), of which there are more than four of, like \(\frac{32}{32}=\frac{3}{3}\).

On the other hand, if the fraction is of the form \(\frac{10c+a}{10c+b} = \frac{a}{b}\), then we will have

\[ (10c+a)b = (10c+b)a \Longrightarrow 10bc + ab = 10ac + ab \Longrightarrow bc = ac. \]

In this form, \(c\) cannot be zero, so this implies \(a = b\) and we arrive at a fraction like \(\frac{10c+a}{10c+a} = \frac{a}{a}\), which is again trivial by the same reasoning.

Therefore, indeed the only non-trivial fractions are of the form \(\frac{10a + c}{10c + b} = \frac{a}{b}\). In this case, we have

\[ (10a+c)b = (10c+b)a \Longrightarrow 10ab +bc = 10ac + ab \Longrightarrow 9ab + bc = 10ac \Longrightarrow (9a + c) b = 10 ac. \]

Now, this means that \(9a+c\) divides \(10ac\), so if we fix the values of \(a\) and \(c\), we can check if this is the case and find the corresponding value of \(b\), which would give us a non-trivial solution. \(a\) and \(c\) can only take values from \(1\) to \(9\), which means there are only \(81\) combinations to check, enough to try by hand.

Before doing so, let's eliminate some of these combinations by using modular arithmetic. The previous equation \((9a+c) b = 10ac\) means \((9a+c) b \equiv b (c - a) \equiv 0 \pmod{10}\). If \(c-a\) was coprime with \(10\), that is, if it was congruent with \(1, 3, 7\) or \(9\), then we could "divide" by \(c-a\) and find that \(b \equiv 0 \pmod{10}\). This implies that \(b=0\), but this cannot be, since then \(\frac{a}{b}\) would be undefined. Threfore, we can ignore the combinations of \(a\) and \(c\) such that \(c-a\) is coprime with \(10\). Here is a table of these combinations after having marked these:

\[ \begin{array}{cc|cccccccc} b & & & & & & a & & & & \\ & & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline &1& \times & \times & & \times & & & & \times & \\ &2& \times & \times & \times & & \times & & & & \times \\ &3& & \times & \times & \times & & \times & & & \\ &4& \times & & \times & \times & \times & & \times & & \\ c&5& & \times & & \times & \times & \times & & \times & \\ &6& & & \times & & \times & \times & \times & & \times \\ &7& & & & \times & & \times & \times & \times & \\ &8& \times & & & & \times & & \times & \times & \times \\ &9& & \times & & 8 & & \times & & \times & \times \\ \end{array} \]

We have also marked \(b=8\) at \(a=5\) and \(c=9\) like the problem statement says and crossed out all the cells with \(a=c\), since this implies

\[ b = \frac{10ac}{9a+c} = \frac{10a^2}{10a} = a, \]

and this means that the fraction is of the form \(\frac{10a+a}{10a+a} = \frac{a}{a}\), which is a trivial solution.

According to the statement, there's only \(3\) more cells in this table that will be valid, so let's try to find those, starting at \(a=1\) and \(c=3\). We have that

\[ b = \frac{10ac}{9a+c} = \frac{10 \cdot 1 \cdot 3}{9+3} = \frac{30}{12}. \]

It's clear that \(13\) does not divide \(30\), so we cross out this cell. The same thing happens at \(a=1\) and \(c=5\) since \(9a+c = 14\) does not divide \(10ac=50\). However, at \(a=1\) and \(c=6\), we find \(9a+c = 15\) and \(10ac=60\), so \(b=\frac{60}{15} = 4\). Therefore, \(\frac{16}{64} = \frac{1}{4}\) is a non-trivial solution.

Let's keep looking at the following cells:

\[ \begin{align*} & a=1, c=7 \Longrightarrow b = \frac{10 \cdot 1 \cdot 7}{9 \cdot 1 + 7} = \frac{70}{16} \notin \mathbb Z, \\ & a=1, c=9 \Longrightarrow b = \frac{10 \cdot 1 \cdot 9}{9 \cdot 1 + 9} = \frac{90}{18} = 5, \\ & a=2, c=4 \Longrightarrow b = \frac{10 \cdot 2 \cdot 4}{9 \cdot 2 + 4} = \frac{80}{22} \notin \mathbb Z, \\ & a=2, c=6 \Longrightarrow b = \frac{10 \cdot 2 \cdot 6}{9 \cdot 2 + 6} = \frac{120}{24} = 5. \end{align*} \]

We have found another two non-trivial fractions: \(\frac{19}{95} = \frac{1}{5}\) and \(\frac{26}{65} = \frac{2}{5}\). If the statement is correct, then these are all the non-trivial solutions.

\[ \begin{array}{cc|cccccccc} b & & & & & & a & & & & \\ & & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline &1& \times & \times & & \times & & & & \times & \\ &2& \times & \times & \times & & \times & & & & \times \\ &3& \times & \times & \times & \times & & \times & & & \\ &4& \times & \times & \times & \times & \times & & \times & & \\ c&5& \times & \times & & \times & \times & \times & & \times & \\ &6& 4 & 5 & \times & & \times & \times & \times & & \times \\ &7& \times & & & \times & & \times & \times & \times & \\ &8& \times & & & & \times & & \times & \times & \times \\ &9& 5 & \times & & 8 & & \times & & \times & \times \\ \end{array} \]

Therefore, our product of these four fractions is

\[ \frac{16}{64} \cdot \frac{19}{95} \cdot \frac{26}{65} \cdot \frac{49}{98} = \frac{1}{4} \cdot \frac{1}{5} \cdot \frac{2}{5} \cdot \frac{4}{8} = \frac{2}{200} = \frac{1}{100}, \]

and our final solution is \(100\).

- dino (2026/01/17)

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)

The convergents of a simple continued fraction \(x\) of the form

\[ x = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \cdots}}} =: [a_0; a_1, a_2, a_3, \dots] \]

are the approximations \(x_n \in \mathbb Q\) given by truncating the continued fraction at \(n\) terms. For example,

\[ x_0 = a_0, \]

\[ x_1 = a_0 + \frac{1}{a_1}, \]

\[ x_2 = a_0 + \frac{1}{a_1 + \frac{1}{a_2}}, \]

\[ x_3 = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3}}}. \]

When written as a fraction \(x_n = \frac{p_n}{q_n}\), it can be shown that the numerators and denominators of convergents follow the recurrence formulas

\[ p_n = a_n p_{n-1} + p_{n-2}, \quad q_n = a_n q_{n-1} + q_{n-2}, \quad \forall n \geq 2. \]

In the case of the square root of \(2\), we have \(x = \sqrt 2 = [1;2,2,2,\dots]\), so \(a_n = 2 \;\forall n \geq 1\) and this expression simplifies to the following linear recurrence relation with constant coefficients:

\[ p_n = 2 p_{n-1} + p_{n-2}, \quad q_n = 2 q_{n-1} + q_{n-2}, \quad \forall n \geq 2. \]

These are both recurrence relations similar to that of Fibonacci's sequence. Furthermore, like with the terms of Fibonacci's sequence, one can find a closed-form expression for the terms of these sequences \(p_n\) and \(q_n\). This would be our analogue of Binet's formula. Such a formula would be of the form

\[ p_n = A \mu^n + B \lambda^n, \quad q_n = C \mu^n + D \lambda^n, \quad \forall n \geq 1, \]

where \(\mu\) and \(\lambda\) are the real roots of the sequence's characteristic polynomial \(x^2 - 2x - 1\) and \(A,B,C,D \in \mathbb R\) are constant coefficients which will be determined by equating \(p_1, p_2, q_1, q_2\) with their known values (the problem's statement shows us that \(\frac{p_1}{q_1} = \frac{3}{2}\) and \(\frac{p_2}{q_2} = \frac{7}{5}\)). We can see \(\mu\) and \(\lambda\) are given by

\[ \mu, \lambda = \frac{2 \pm \sqrt{4 + 4}}{2} = \frac{2 \pm \sqrt 8}{2} = 1 \pm \sqrt 2. \]

Therefore, \(p_n\) and \(q_n\) would be given by

\[ p_n = A (1 + \sqrt 2)^n + B (1 - \sqrt 2)^n, \quad q_n = C (1 + \sqrt 2)^n + D (1 - \sqrt 2)^n, \quad \forall n \geq 1. \]

As was said before, we can substitute with \(n=1\) and \(2\) to find two systems of linear equations depending on \(A,B\) and \(C,D\):

\[ \left\{ \begin{array}{l} p_1 = A (1 + \sqrt 2) + B (1 - \sqrt 2) = 3 \\ p_2 = A (1 + \sqrt 2)^2 + B (1 - \sqrt 2)^2 = 7 \end{array} \right. \quad \left\{ \begin{array}{l} q_1 = C (1 + \sqrt 2) + D (1 - \sqrt 2) = 2 \\ q_2 = C (1 + \sqrt 2)^2 + D (1 - \sqrt 2)^2 = 5 \end{array} \right. \]

Solving these systems of linear equations (notice that the corresponding matrices are equal, so one could find the inverse of this matrix to solve both systems) gives the values

\[ A = \frac{1 + \sqrt 2}{2}, \quad B = \frac{1 - \sqrt 2}{2}, \quad C = \frac{2 + \sqrt 2}{4}, \quad D = \frac{2 - \sqrt 2}{4}, \]

which we can plug in the previous formulas. In short, the numerators and denominators of any convergent of the square root of \(2\) can be found with the formulas

\[ p_n = \frac{(1 + \sqrt 2)^{n+1} + (1 - \sqrt 2)^{n+1}}{2}, \quad q_n = \frac{(2 + \sqrt 2) (1 + \sqrt 2)^n + (2 - \sqrt 2) (1 - \sqrt 2)^n}{4}, \quad \forall n \geq 1. \]

Note the resemblance with the complex formulations of cosines and sines, which have

\[ \cos x = \frac{e^{ix} + e^{-ix}}{2}, \quad \sin x = \frac{e^{ix} - e^{-ix}}{2i}. \]

In fact, one could rewrite

\[ q_n = \frac{(1+\sqrt 2)^{n+1} - (1 - \sqrt 2)^{n+1}}{2 \sqrt 2}, \]

which is very similar to the sine's expression in this analogy. However, we will use the former expression for \(q_n\).

Now, we are interested in finding which values of \(n\) verify that \(p_n\) has more digits than \(q_n\). Recall that the number of digits of an integer \(m\) can be expressed as \(\lfloor \log_{10} m \rfloor + 1\), so we are interested in finding when \(\lfloor \log_{10} p_n \rfloor > \lfloor \log_{10} q_n \rfloor\). Observe that there is no nice expression for \(\log_{10} p_n\) since the previous formula involves a sum. However, as in problem 25's solution, we notice that \(\left\lvert 1 - \sqrt 2 \right\rvert \approx 0.4142 \lt 1\) so the second summand in both expressions approaches zero as \(n\) increases and we can approximate \(p_n \approx \frac{1}{2} (1 + \sqrt 2)^{n+1}\) and \(q_n \approx \frac{2 + \sqrt 2}{4} (1 + \sqrt 2)^n\). Both these approximations only get better and better as \(n\) increases. Therefore, we can fairly approximate these logarithms as

\[ \log_{10} p_n \approx \log_{10} \left( \frac{1}{2} (1 + \sqrt 2)^{n+1} \right) = n \log_{10}(1 + \sqrt 2) + \log_{10} \frac{1 + \sqrt 2}{2}, \]

\[ \log_{10} q_n \approx \log_{10} \left( \frac{2 + \sqrt 2}{4} (1 + \sqrt 2)^{n+1} \right) = n \log_{10}(1 + \sqrt 2) + \log_{10} \frac{2 + \sqrt 2}{4}. \]

Both these expressions are linear functions of \(n\) (Caution! these are \textit{linear functions} in the sense that they are degree \(1\) polynomials whose graphs are straight lines. Since they have non-zero intercept, they are not \textit{linear} in the linear algebra sense.) and they have the same slope, so let's denote the real functions

\[ P(x) := x \log_{10}(1 + \sqrt 2) + \log_{10} \frac{1 + \sqrt 2}{2}, \quad Q(x) := x \log_{10}(1 + \sqrt 2) + \log_{10} \frac{2 + \sqrt 2}{4}. \]

We will have that \(p_n\) has more digits than \(q_n\) if \(\lfloor P(n) \rfloor \gt \lfloor Q(n) \rfloor\). One way to find which values of \(n \in \mathbb N\) verify this is to find the regions in which \(x \in \mathbb R\) verifies it too and then check if those regions contain integer numbers. One of these regions is \([a,b)\) where \(P(a) = 0\) and \(Q(b) = 0\), since at \(x=a\), we have that \(\lfloor P(x) \rfloor\) goes from \(-1\) to \(0\) while \(Q(a) = -1\); and at \(x=b\), \(\lfloor Q(b) \rfloor\) goes up to \(0\). One can find these values \(a,b\) as follows:

\[ P(a) = a \log_{10} (1 + \sqrt 2) + \log_{10} \frac{1 + \sqrt 2}{2} = 0 \Longrightarrow a = - \frac{\log_{10} \frac{1 + \sqrt 2}{2}}{\log_{10}(1 + \sqrt 2)} = \frac{\log_{10} 2}{\log_{10}(1 + \sqrt 2)} - 1, \]

\[ Q(b) = b \log_{10} (1 + \sqrt 2) + \log_{10} \frac{2 + \sqrt 2}{4} = 0 \Longrightarrow b = - \frac{\log_{10} \frac{2 + \sqrt 2}{4}}{\log_{10}(1 + \sqrt 2)} = \frac{2 \log_{10} 2 - \log_{10}(2 + \sqrt 2)}{\log_{10}(1 + \sqrt 2)}. \]

These values are, approximately, \(a \approx -0.2136\) and \(b \approx 0.1797\). This means that \(\lfloor P(x) \rfloor \gt \lfloor Q(x) \rfloor\) for any \(x \in [-0.2136, 0.1797)\), and in particular, for \(x=0\), which is an integer. However, this doesn't mean that \(p_0 = 1\) has more digits than \(q_0 = 1\). This is because the approximation \(q_n \approx \frac{2 + \sqrt 2}{4} (1 + \sqrt 2)^n\) gives \(q_0 \approx \frac{2 + \sqrt 2}{4} \approx 0.8536 \lt 1\), which makes our "algorithm" think \(q_0\) has zero digits instead of one. We will suppose that this approximation is good enough as \(n\) increases so that we won't have to worry about this kind of errors for higher values of \(n\).

Notice that, since \(P(x)\) and \(Q(x)\) are linear functions with the same slope, the next region in which \(\lfloor P(x) \rfloor \gt \lfloor Q(x) \rfloor\) is just a translation of \([a,b)\) to the point where \(P(x) = 1\). This slope is \(\log_{10}(1 + \sqrt 2)\), so the interval is translated by \(d := \frac{1}{\log_{10}(1 + \sqrt 2)}\) and the next region is given by \([d + a, d + b)\). Approximately, this region is \([2.3989, 2.7922)\), as we can see in the graph of \(P(x)\) and \(Q(x)\). It doesn't contain any integers so we don't expect to find any of the interesting values of \(n\) in this interval.

Repeating this argument, the regions in which \(\lfloor P(x) \rfloor \gt \lfloor Q(x) \rfloor\) are given by the equally spaced intervals \(I_m := [md + a, md + b)\) for any \(m \in \mathbb Z\), though we will only care for values of \(m\) with \(m \geq 1\). The first intervals of these form are, approximately

\begin{align*} m=1: \quad & I_1 = [d+a, d+b) \approx [2.3989,2.7922), \\ m=2: \quad & I_2 =[2d + a, 2d + b) \approx [5.0114, 5.4047), \\ m=3: \quad & I_3 = [3d + a, 3d + b) \approx [7.6239,8.0171), \\ m=4: \quad & I_4 = [4d + a, 4d + b) \approx [10.2364,10.6296). \end{align*}

Of these intervals, only \(I_3\) contains an integer, which is \(n=8\). And indeed, as the statement says, the first convergent with more digits in the numerator than in the denominator is \(x_8\), which has \(p_8 = 1393\) and \(q_8 = 985\). Checking the following intervals, one can find that \(I_5\) doesn't have any integers but the interval \(I_6\) contains \(n=13\), so we will expect \(p_{13}\) to have more digits than \(q_{13}\). This is the case, since \(p_{13}= 114243\) and \(q_{13} = 80782\).

We can visualize what happens with every translation of these intervals by working in the circle group, that is, the real numbers modulo the integers \(\mathbb{R} / \mathbb{Z}\). This simply means discarding the integer part of the numbers we are working with and looking at their decimals. For example, if we want to look at \(\sqrt 2 \approx 1.4142\) in the circle group, it will be at the same place as \(0.4142\dots\), while every integer will be in the same place as \(0\). We will denote this decimal part of a number \(x \in \mathbb R\) as \(\overline x \in \mathbb R / \mathbb Z\). We can visualize this like this:

So the intervals \(I_m\) in the group circle looks like this:

In this illustration, \(0\) being contained in the interval means that \(I_m\) contains an integer. In each step, the interval is shifted \(d\) units. If we could find a periodicity in how these intervals are shifted, we could exploit it to simplify our task. Unfortunately, \(d\) is an irrational number, which means that there is no periodicity in these intervals.

However, we have that \(d = \frac{1}{\log_{10}(1 + \sqrt 2)} = 2.6124961\dots\) is surprisingly well approximated by \(2.6125 = 2 + \frac{49}{80}\), which means that, after \(80\) translations, we will have shifted the interval to an amount very close to an integer. This means that the intervals in the group circle are very close to being periodic every \(80\) times:

\[ I_0 = [a,b) \approx [-0.2136, 0.1797), \quad I_{80} = [80d + a, 80d + b) \approx [208.7861, 209.1794). \]

This means that \(290 \in I_{80}\) and \(p_{290}\) has more digits than \(q_{290}\), which is true since they have \(112\) and \(111\) digits respectively.

To see how tight this approximation is, we can see that \(80d = \frac{80}{\log_{10}(1+\sqrt 2)} \approx 208.9996911\), which is within almost three ten-thousands of an integer. We notice that \(1000 \lt 383 d + b\), that is, in \(383\) shifts we get to the upper bound the question statement asks of us. If we approximate \(d \approx 2 + \frac{49}{80}\), after these \(383\) shifts the interval \(I_{383}\) will be about \(0.0015\) units away from its real value. With a bit of luck, our approximation will work fine.

Obviously, \(I_m\) will contain an integer \(n\) if if \(md + a \leq n \lt md + b\). Since \(b = a + (b-a)\), this means that \(I_m\) will contain \(n\) if and only if \(md + a \leq n\) and \(md + a \gt n - (b-a)\), that is, if \(md + a \in (n - (b-a), n]\). In the unit circle, this is equivalent to \(\overline{md + a} \in \left(\overline {a-b}, \overline 0\right]\), that is, that the left side of \(\overline I_m\) is between \(\overline{a-b}\) and \(\overline 0\) (this might feel ambiguous since there's no ordering in the unit circle and "between two numbers" could mean anything, but hopefully the illustrations convey clearly what this means). Notice that \(a-b\) is a constant and its decimal part is approximately \(0.606780\). This way, instead of asking whether \(\overline 0\) is contained in \(\overline I_m\), we will ask if \(\overline{md+a} \in \left( \overline{a-b}, \overline 0\right]\), which is somewhat easier.

Now, since we can fairly approximate \(d \approx 2 + \frac{49}{80}\), we could think that \(md+a\) falls close to rational numbers such as \(\frac{k}{80}, k \in \mathbb Z\). The number \(md\) does fall close to these fractions, but \(80 a \approx -17.084824\), which is almost a tenth from an integer, which means that \(md+a\) is not too close to being a fraction like \(\frac{k}{80}\). However, since \(a\) is not multiplied by \(m\), this tenth of a unit error is not amplified as \(m\) increases like the approximation error of \(d\) does. Therefore, let's say that \(a \approx -\frac{17}{80}\). This way, we have that \(md + a \approx (2 + \frac{49}{80})m - \frac{17}{80}\), which is always a fraction like \(\frac{k}{80}\).

In the unit circle, we have \(\overline d \approx \overline{\frac{49}{80}}\) and \(\overline a \approx \overline{\frac{63}{80}}\), so that \(\overline{md+a} \approx \overline{\frac{49}{80} m - \frac{17}{80}}\). Notice that this means that \(\overline{md+a}\) is always falling in the subdivisions made by dividing the circle in \(80\) parts. This suggests that we can replace our faithful unit circle with an \(80\)-element cyclic group, like the integers modulo \(80\), \(\mathbb Z_{80} := \mathbb Z / 80 \mathbb Z = \left\{ \overline 0, \overline 1, \dots, \overline{79} \right\}\). This way, we associate \(I_m\) and \(\overline{md+a} \approx \overline{\frac{49}{80} m - \frac{17}{80}} \in \mathbb R / \mathbb Z\) with \(c_m := \overline {49 m - 17} \in \mathbb Z_{80}\).

Now, since \(80(a-b) \approx -31.45759\), we will have that \(\overline{md+a} \in (\overline{a-b},\overline 0]\) if \(c_m\) is any of the numbers \(\overline {-31} = \overline{49}, \overline{50}, \overline {51}, \dots, \overline {79}\) or \(\overline 0\).

This means that, if \(C \subseteq \mathbb Z_{80}\) is the set of these numbers from \(\overline{49}\) to \(\overline{0}\), \(I_m\) contains an integer if and only if \(c_m = \overline{49 m - 17} \in C\). For each of the numbers \(k \in C\), this is a modular equation of the form \(49 m - 17 \equiv k \pmod{80}\). We can solve this equation by adding \(17\) on both sides and multiplying by \(49^{-1}\), that is, the inverse modulo \(80\) of \(49\). This is a number that satisfies \(49 \cdot 49^{-1} \equiv 1 \pmod{80}\). It could be that no such number exists, which could make solving this equation much harder. However, a number \(x\) has an inverse modulo \(y\) if and only if \(x\) and \(y\) are coprime, which is the case here since \(49\) and \(80\) are coprime. This also means that the function \(\overline x \mapsto 49 \overline x\) is bijective and we know that we will find \(\lvert C \rvert = 32\) different solutions to this equation. Furthermore, this implies that we expect the solution to the problem to be about \(\frac{32}{80} \cdot 383 \approx 153\), since \(383\) was the number of interval shifts that we needed to do to get to \(1000\). Turns out that this is the correct answer! However, we can't be sure of this without plugging it in to the Project Euler website. Solving this modular equation, we can find the exact convergents that have more digits in the numerator than in the denominator.

Turns out that \(49^2 = 2401 = 30 \cdot 80 + 1\), so \(49\) is its own inverse modulo \(80\) and we get the solution

\[ m \equiv 49 (k + 17) \equiv 49k + 33 \pmod{80}. \]

Plugging the values of \(k \in C\) into this equation, we get the following solutions of \(\overline m\):

\[ \begin{array}{c|l} k & 49 k + 33 \ (\mathrm{mod}\ {80}) \\ \hline 49 & 34 \\ 50 & 3 \\ 51 & 52 \\ 52 & 21 \\ 53 & 70 \\ 54 & 39 \\ 55 & 8 \\ 56 & 57 \\ 57 & 26 \\ 58 & 75 \\ 59 & 44 \\ 60 & 13 \\ 61 & 62 \\ 62 & 31 \\ 63 & 0 \\ 64 & 49 \end{array} \quad \begin{array}{c|l} k & 49 k + 33 \ (\mathrm{mod}\ {80}) \\ \hline 65 & 18 \\ 66 & 67 \\ 67 & 36 \\ 68 & 5 \\ 69 & 54 \\ 70 & 23 \\ 71 & 72 \\ 72 & 41 \\ 73 & 10 \\ 74 & 59 \\ 75 & 28 \\ 76 & 77 \\ 77 & 46 \\ 78 & 15 \\ 79 & 64 \\ 0 & 33 \end{array} \]

Ordering these values, we get the \(32\) following values of \(m\) modulo \(80\) such that \(I_m\) contains an integer:

\[ \begin{array}{cccccccc} 0 & 3 & 5 & 8 & 10 & 13 & 15 & 18 \\ 21 & 23 & 26 & 28 & 31 & 33 & 34 & 36 \\ 39 & 41 & 44 & 46 & 49 & 52 & 54 & 57 \\ 59 & 62 & 64 & 67 & 70 & 72 & 75 & 77 \end{array} \]

As we said, \(1000 \lt 383 d + b\) and \(383 = 4 \cdot 80 + 63\). This means that, before getting to \(m=383\), \(c_m\) hits all values in \(\mathbb Z_{80}\) \(4\) times and the \(32\) solutions, and then, it hits all the values with \(m \lt 63\), which in the previous table has \(26\) solutions. So in total, we hit \(32 \cdot 4 + 26 = 154\) solutions. Finally, we need to substract one since we are counting \(m = 0\), which we have already argued is not a real solution, so our final answer is \(153\).

As an extra, let's find the values of \(n\) such that \(x_n\) has more digits in the numerator than in the denominator. For each solution \(m\), we can find the number \(n \in I_m\) by writing \(n = \lceil md + a \rceil\):

\[ \begin{array}{c|l} m & \lceil md + a \rceil \\ \hline 0 & 0 \\ 3 & 8 \\ 5 & 13 \\ 8 & 21 \\ 10 & 26 \\ 13 & 34 \\ 15 & 39 \\ 18 & 47 \\ 21 & 55 \\ 23 & 60 \\ 26 & 68 \\ 28 & 73 \\ 31 & 81 \\ 33 & 86 \\ 34 & 89 \\ 36 & 94 \end{array} \quad \begin{array}{c|l} m & \lceil md + a \rceil \\ \hline 39 & 102 \\ 41 & 107 \\ 44 & 115 \\ 46 & 120 \\ 49 & 128 \\ 52 & 136 \\ 54 & 141 \\ 57 & 149 \\ 59 & 154 \\ 62 & 162 \\ 64 & 167 \\ 67 & 175 \\ 70 & 183 \\ 72 & 188 \\ 75 & 196 \\ 77 & 201 \end{array} \]

So if \(N\) is the following set of numbers:

\[ \begin{array}{cccccccc} 0 & 8 & 13 & 21 & 26 & 34 & 39 & 47 \\ 55 & 60 & 68 & 73 & 81 & 86 & 89 & 94 \\ 102 & 107 & 115 & 120 & 128 & 136 & 141 & 149 \\ 154 & 162 & 167 & 175 & 183 & 188 & 196 & 201 \end{array} \]

then the convergent \(x_n, n \gt 0\) has one more digit in the numerator than in the denominator if and only if we can write \(n = s + 209 t\) for \(s \in N\) and \(t \in \mathbb Z\), where \(209\) comes from approximating \(80 d\). Therefore, the \(153\) values of \(n\) the problem is asking for are exactly

\[ \begin{array}{cccccccc} & 8 & 13 & 21 & 26 & 34 & 39 & 47 \\ 55 & 60 & 68 & 73 & 81 & 86 & 89 & 94 \\ 102 & 107 & 115 & 120 & 128 & 136 & 141 & 149 \\ 154 & 162 & 167 & 175 & 183 & 188 & 196 & 201 \\ \hline 209 & 217 & 222 & 230 & 235 & 243 & 248 & 256 \\ 264 & 269 & 277 & 282 & 290 & 295 & 298 & 303 \\ 311 & 316 & 324 & 329 & 337 & 345 & 350 & 358 \\ 363 & 371 & 376 & 384 & 392 & 397 & 405 & 410 \\ \hline 418 & 426 & 431 & 439 & 444 & 452 & 457 & 465 \\ 473 & 478 & 486 & 491 & 499 & 504 & 507 & 512 \\ 520 & 525 & 533 & 538 & 546 & 554 & 559 & 567 \\ 572 & 580 & 585 & 593 & 601 & 606 & 614 & 619 \\ \hline 627 & 635 & 640 & 648 & 653 & 661 & 666 & 674 \\ 682 & 687 & 695 & 700 & 708 & 713 & 716 & 721 \\ 729 & 734 & 742 & 747 & 755 & 763 & 768 & 776 \\ 781 & 789 & 794 & 802 & 810 & 815 & 823 & 828 \\ \hline 836 & 844 & 849 & 857 & 862 & 870 & 875 & 883 \\ 891 & 896 & 904 & 909 & 917 & 922 & 925 & 930 \\ 938 & 943 & 951 & 956 & 964 & 972 & 977 & 985 \\ 990 & 998 \end{array} \]

Now, the previous statement is not completely true. It holds for the first values of \(t\), but as \(t\) and \(m\) increase, the errors in our approximations also increase and, eventually, our formula will break. These values of \(n\) for which \(x_n\) has more digits in the numerator than in the denominator make up the OEIS sequence A273980, which refers to the Project Euler problem and gives a bit more insight into the properties of the sequence.

- dino (2026/01/16)

It is clear that \(10^n\) is a one followed by \(n\) zeros, so it has \(n+1\) digits for any integer \(n\) and therefore cannot be an \(n\)^th power with \(n\) digits. Also, for any base \(a \in \mathbb N\) with \(a \geq 10\), we will have \(a^n \geq 10^n\), so \(a^n\) will have \(n+1\) digits or more, so it won't work either. Therefore, we know that these numbers will be of the form \(a^n\) with \(a \lt 10\).

It's easy to see that \(a^1\) has \(1\) digit for each \(a \lt 10\), so the ten digits are trivially \(1\)-digit positive integers that are also "\(1\)^st powers". Now, since \(a \lt 10\), if \(a^n\) fails to be an \(n\)-digit number, it follows that \(a^{n+1} = a^n \cdot a\) will also fail to be an \(n+1\)-digit number and, in general, \(a^m\) won't be an \(m\)-digit number for any \(m \geq n\). Therefore, for each base \(a\), we just have to check when \(a^n\) fails to be an \(n\)-digit number and all powers below it will work for us.

For example, \(2^2 = 4\) is not a \(2\)-digit number, so we know that the only power with base \(2\) that we want is \(2^1\). The same thing happens with \(3\), since \(3^2 = 9\). However, \(4\) has that \(4^2 = 16\) is a \(2\)-digit number, but \(4^3 = 64\) doesn't have \(3\) digits. Checking all values for \(a\), we have

\[ \begin{array}{clc} a & \text{First Fail} & \text{Total Powers} \\ \hline 1 & 1^2 = 1 & 1 \\ 2 & 2^2 = 4 & 1 \\ 3 & 3^2 = 9 & 1 \\ 4 & 4^3 = 64 & 2 \\ 5 & 5^4 = 625 & 3 \\ 6 & 6^5 = 7776 & 4 \\ 7 & 7^7 = 823543 & 6 \\ 8 & 8^{11} = 8589934592 & 10 \\ 9 & 9^{22} = 984770902183611232881 & 21 \end{array} \]

In total, we obtain \(49\) powers. We could think that some of these are repeats, but it's clear that, if we have two numbers of this form \(a^n\) and \(b^m\) with \(n\) and \(m\) different, they are different since they have different numbers of digits. If they do have \(n\) and \(m\) equal but \(a\) and \(b\) different, they will also be different since, for every positive integer \(n\), \(x^n\) is an injective function for \(x\) integer. Therefore, we have no repeats and \(49\) is our answer.

- dino (2025/07/05)

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 ratio \(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)