Project Euler $420$

1.3k Views Asked by At

So the question is:

We define $F(N)$ as the number of the $2\times 2$ positive integer matrices which have a trace less than $N$ and which can be expressed as a square of a positive integer matrix in two different ways. We can verify that $F(50) = 7$ and $F(1000) = 1019$.

Find $F(107)$.

And the site gives the example $$\begin{pmatrix}40 & 12 \\ 48 & 40\end{pmatrix} = \begin{pmatrix}2 & 3 \\ 12 & 2\end{pmatrix}^2 = \begin{pmatrix}6 & 1 \\ 4 & 6\end{pmatrix}^2$$

After some quick googling around I found a page showing a general formula for finding the square root of a 2x2 matrix. After using the formula and the fact that all the numbers are positive integers, I came up with some simple restrictions that would help sort out which matrices have two positive square root matrices. With the information I wrote a function in python $H(N)$ to find the number of 2x2 matrices with a trace $N$ that have two positive square root matrices. I then defined the function asked for in the question as $$F(N) = \sum_{i=0}^{N-1}H(i)$$

But when I compute F(50) I get 8, when the problem description says it is only 7! I printed out the matrices I computed, they are $$\begin{pmatrix}5 & 4 \\ 4 & 5\end{pmatrix} = \begin{pmatrix}2&1\\1&2\end{pmatrix}^2 = \begin{pmatrix}1&2\\2&1\end{pmatrix}^2$$ $$\begin{pmatrix}10&6\\6&10\end{pmatrix} = \begin{pmatrix}3&1\\1&3\end{pmatrix}^2 = \begin{pmatrix}1&3\\3&1\end{pmatrix}^2$$ $$\begin{pmatrix}13&12\\12&13\end{pmatrix}=\begin{pmatrix}3&2\\2&3\end{pmatrix}^2=\begin{pmatrix}2&3\\3&2\end{pmatrix}^2$$ $$\begin{pmatrix}17&8\\8&17\end{pmatrix}=\begin{pmatrix}4&1\\1&4\end{pmatrix}^2=\begin{pmatrix}1&4\\4&1\end{pmatrix}^2$$ $$\begin{pmatrix}12&8\\24&28\end{pmatrix}=\begin{pmatrix}3&1\\3&5\end{pmatrix}^2=\begin{pmatrix}0&2\\6&4\end{pmatrix}^2$$ $$\begin{pmatrix}20&8\\32&20\end{pmatrix}=\begin{pmatrix}4&1\\4&4\end{pmatrix}^2=\begin{pmatrix}2&2\\8&2\end{pmatrix}^2$$ $$\begin{pmatrix}20&16\\16&20\end{pmatrix}=\begin{pmatrix}4&2\\2&4\end{pmatrix}^2=\begin{pmatrix}2&4\\4&2\end{pmatrix}^2$$ $$\begin{pmatrix}18&9\\18&27\end{pmatrix}=\begin{pmatrix}4&1\\2&5\end{pmatrix}^2=\begin{pmatrix}0&3\\6&3\end{pmatrix}^2$$

Are the square roots of those first few matrices really considered different? I get the feeling those matrices with swapped rows aren't actually 'different'. Wouldn't any 2x2 square root matrix square to the same thing if the rows are swapped? If those repeat matrices aren't really different, that means I actually only found 3 matrices, and not the 7 I was supposed to find!

1

There are 1 best solutions below

5
On BEST ANSWER

I think I found your answer by the way. One of these matrices does not fit the criteria.

$$\begin{pmatrix}0&3\\6&3\end{pmatrix}$$ does not fit the problem's definition of a positive integer matrix as $0$ is not positive.