This week’s Riddler Classic is a number theory problem, which I will paraphrase:

The number 50 can be represented using a set of interleaved dots where the number of columns is one greater than the number of rows; the same way the stars in the US flag are arranged. If we add 1 to this number, we obtain 51, which can be represented using concentric pentagons. Here are diagrams showing both arrangements:

What is the next number with the property that it can be represented as interleaved dots but when you add 1 to it it can be represented using concentric pentagons?

Here is my solution:

[Show Solution]

The arrangement on the left consists of an $(m+1) \times m$ grid on the outside, with an $m\times (m-1)$ grid on the inside, for a total of $m(m+1)+m(m-1)=2m^2$ points. In the case of the US flag, $m=5$ and we have 50 total points. If a number can be written as $2m^2$, I’ll call it a flag number.

The numbers represented on the right are called centered pentagonal numbers. We have 1 point in the center, 5 in the next layer, 10 in the next layer, 15 in the next layer, and so on. This means the centered pentagonal numbers have the form $\frac{5n^2+5n+2}{2}$. In our case shown above, $n=4$ and the formula produces 51, as anticipated.

To answer the question, we want to find centered pentagonal numbers that are one greater than a flag number. Mathematically, this amounts to finding pairs of positive integers $(n,m)$ such that:

\[

\frac{5n^2+5n+2}{2}-2m^2 = 1

\]Rearranging this equation a little bit, we can write it as:

\[

5(2n+1)^2-(4m)^2=5

\]Let’s rename $x=2n+1$, where $x$ is an integer. Due to the parity of the remaining terms, $x$ must always be odd so there is no loss of generality in solving for $x$ rather than $n$. Also, two of the terms are divisible by 5, so the third one must also be divisible by 5 and we conclude $4m=5y$ for some integer $y$. Eliminating $m$ and $n$, we obtain the following equation:

$\displaystyle

x^2-5y^2=1,\quad\text{where: }n=\frac{x-1}{2}\text{ and }m=\frac{5y}{4}

$

So if we find a particular solution $(x,y)$, we can convert it to $(n,m) = \left( \frac{x-1}{2}, \frac{5y}{4} \right)$, and then our pair of centered pentagonal and flag numbers that differ by 1 is given by $\frac{5n^2+5n+2}{2}$ and $2m^2$, respectively. The solution we originally had $(n,m)=(4,5)$ corresponds to the solution $(x,y)=(9,4)$ of the simplified equation above.

### Brute-force approach

If we rewrite the equation $x^2-5y^2=1$ as $x^2 = 5y^2+1$. We can then try different values $y=1,2,3,\dots$ until $5y^2+1$ becomes a perfect square. Not particularly elegant, but it is guaranteed to find us all solutions (eventually). Here are the first few solutions that we obtain:

$x$ | $y$ | $n$ | $m$ | pentagonal number | flag number |
---|---|---|---|---|---|

9 | 4 | 4 | 5 | 51 | 50 |

161 | 72 | 80 | 90 | 16,201 | 16,200 |

2,889 | 1,292 | 1,444 | 1,615 | 5,216,451 | 5,216,450 |

51,841 | 23,184 | 25,920 | 28,980 | 1,679,680,801 | 1,679,680,800 |

### Pell’s equations

This is not the end of the story! The equation $x^2-5y^2=1$ is an example of Diophantine equation, that is, a polynomial equation for which we seek integer solutions. More specifically, it is an instance of Pell’s equation, which comes up often enough that it was given it’s own name! In general, Pell’s equation refers to any Diophantine equation of the form $x^2-dy^2=1$.

To understand the structure of solutions to Pell’s equation, consider $\mathbb{Z}[\sqrt{5}]$, which is the set of numbers of the form $z = a+b\sqrt{5}$ where $a$ and $b$ are integers. Just like with complex numbers, we can define the conjugate by flipping the sign of the second term, so $\bar z=a-b\sqrt{5}$. Notice that if $z=x+y\sqrt{5}$, we have:

\[

z \bar z = \left(x+y\sqrt{5}\right)\left(x-y\sqrt{5}\right) = x^2-5y^2

\]So $(x,y)$ is a solution to Pell’s equation precisely when the number $z=x+y\sqrt{5}$ satisfies $z\bar z = 1$.

**Fact 1:** If $z$ is a solution to Pell’s equation, then $z^{-1} = \bar{z}$ is also a solution. This is a straightforward consequence of the fact that $z$ must satisfy $z\bar z = 1$.

**Fact 2:** If $z_1$ and $z_2$ are both solutions to Pell’s equation, then so is the product $z_1 z_2$. To see why this is the case, we use the fact that conjugation is distributive and multiplication is commutative:

\[

(z_1z_2)(\overline{z_1z_2}) = (z_1 \overline{z_1}) (z_2 \overline{z_2}) = 1

\]Now, let’s define the *fundamental unit* $e \in \mathbb{Z}[\sqrt{5}]$ to be the smallest solution to Pell’s equation with $x,y\gt 0$. In our case, $e = 9+4\sqrt{5}$, which is the first row in the table we generated above. Based on our observation that products of solutions are again solutions, it should be the case that $e^2$ is a solution. Let’s check!

\begin{align}

e^2 &= (9+4\sqrt{5})^2 \\

&= 81 + 2\cdot 9\cdot 4\sqrt{5} + 16\cdot 5 \\

&= 161 + 90\sqrt{5}

\end{align}And indeed, $(x,y)=(161,90)$ is also a solution; it’s the second one in our table above! But things get more interesting…

**Fact 3:** If a solution to Pell’s equation satisfies $x+y\sqrt{5}\gt 1$, then $x,y\gt 0$. To see why this is the case, use the fact that $(x+y\sqrt{5})(x-y\sqrt{5})=1$, from which we conclude that $0\lt x-y\sqrt{5}\lt 1$. We therefore have the inequalities:

\begin{align}

1&\lt x+y\sqrt{5} \\

0&\lt x-y\sqrt{5} \lt 1 \\

-1&\lt -x+y\sqrt{5}\lt 0

\end{align}Adding pairs of these inequalities together to eliminate $x$ or $y$, we conclude that $1\lt 2x$ and $0\lt 2\sqrt{5}y$. Therefore, $x,y\gt 0$, as required.

**Fact 4:** All positive integer solutions to the Pell equation $x^2-5y^2=1$ are given by $e^k$ for $k=\{1,2,3,\dots\}$. We will prove this surprising fact by contradiction. Suppose we are wrong and there is some other solution $z$ that is not of this form. Since $e\gt 1$, it must be the case that for some $k$, we have $e^k \lt z \lt e^{k+1}$. Rearranging, we obtain $1\lt z e^{-k} \lt e$. Since $z$ and $e^{-k}$ are both solutions (Fact 1), then $z e^{-k}$ must also be a solution (Fact 2). Moreover $z e^{-k} \gt 1$ so by Fact 3, this solution must also have $x,y\gt 0$. However, we also showed that $z e^{-k} \lt e$, which contradicts the definition of the fundamental unit; $e$ was defined as the smallest solution with $x,y\gt 0$. This contradiction means that our initial premise must have been false. So all solutions are of the form $e^k$.

The arguments we used for the case $d=5$ still hold true for any $d$ that is not a perfect square, so for example we could find solutions to $x^2-17y^2=1$ in the exact same way; by looking for fundamental unit and then raising it to any power. In the case where $d = h^2$ is a perfect square, then the equation becomes $x^2-(hy)^2=1$ and it is clear that the only solution is $(x,y) = (\pm 1, 0)$.

### All solutions

Based on our little Pell’s equation detour, we established that all solutions to the equation $x^2-5y^2=1$ are of the form:

\[

(9+4\sqrt{5})^k\qquad\text{for: }k=1,2,\dots

\]We can find explicit formulas for $x$ and $y$ by using the fact that $x = \tfrac{1}{2}(z+\bar z)$ and $y = \tfrac{1}{2}(z-\bar z)$, which produces:

\[

(x,y)\,=\,\left( \tfrac{(9+4\sqrt{5})^k+(9-4\sqrt{5})^k}{2}, \tfrac{(9+4\sqrt{5})^k-(9-4\sqrt{5})^k}{2}\right)\qquad\text{for: }k=1,2,\dots

\]This might remind you of the formula for generating Fibonacci numbers, which is another example of an integer sequence whose general formula involves irrational numbers.

Just like with the Fibonacci sequence, we can find a recursive formula. Starting with $k=0$ for simplicity, we have $(x_0,y_0)=(1,0)$. Then subsequent terms can be generated using:

\begin{align}

x_{k+1}+y_{k+1}\sqrt{5} &= \left( x_k+y_k\sqrt{5} \right)\left( 9+4\sqrt{5} \right)\\

&= (9x_k+20y_k) + (4x_k+9y_k)\sqrt{5}

\end{align}Or in other words, the recursive relationship:

\[

\begin{bmatrix}

x_{k+1} \\ y_{k+1}

\end{bmatrix}

=

\begin{bmatrix}

9 & 20 \\ 4 & 9

\end{bmatrix}

\begin{bmatrix}

x_{k} \\ y_{k}

\end{bmatrix}

\qquad\text{with: }

\begin{bmatrix}

x_{0} \\ y_{0}

\end{bmatrix}

=

\begin{bmatrix}

1 \\ 0

\end{bmatrix}

\]If you find this stuff interesting, it’s part of a branch of mathematics called algebraic number theory.

This is a great blog. Thanks for taking the time to provide all of this as a public service.

You’re welcome!