21
$\begingroup$

In his history of number theory, Dickson mentions an 18th century algorithm due to Matsunago [Sic --- he means, presumably, Matsunaga Ryohitsu a.k.a. Matsunaga Yoshisuke] for finding two numbers whose squares sum to a given integer $p$. Dickson's source Mikami can be found describing the Matsunaga method in entry 15 on page 233 here:

http://quod.lib.umich.edu/u/umhistmath/ACD4271.0008.001/244?rgn=full+text;view=pdf

Quoting:

``To solve the equation $x^2+y^2=k$, let $\tfrac{1}{2}k$ be $=r^2+R$, where $r^2$ is the greatest square contained in $k$. Form the quantities

$$ a_1 = 2r-1 \quad a_2 = a_1 - 2 \quad a_3 = a_2 -2 \ldots $$ $$ b_1 = 2r+1 \quad b_2 = b_1 + 2 \quad b_3 = b_2 + 2 \ldots $$

and from $2R=A$ successively subtract $b_1$, $b_2$, $\ldots$. When these subtractions are impossible, successively add $a_1$, $a_2$, $\ldots$ and carry out the subtractions. If we come at last to a remainder that vanishes, let the values of $a$ and $b$ employed in the last place be $a'$ and $b'$. Then $x = \tfrac{1}{2}(a'+1)$ and $y = \tfrac{1}{2}(b'-1)$ is a solution required."

I have a lot of questions about this, but I'll start with: Can you make this work? I've tried several different interpretations of the instructions but have been unable to make it work to produce the representations $5 = 1^2 + 2^2$, $10 = 1^2 + 3^2$, $13 = 2^2 + 3^2$, $17 = 4^2 + 1^2$, $41 = 4^2 + 5^2$, ... in a reliable manner. I desire a systematic way to follow these instructions that produces each of these representations (and others, if possible!). Or perhaps this does not work for all $k$ (i.e., the remainder 0 is not reached). But an exposition of how it works when it does work would be appreciated.

Incidentally, the wording differs slightly from that given by Dickson. I doubt he would include this result as stated if it didn't hold some merit. Perhaps his rewording of the instructions (p.229 of volume 2 of his "Number Theory") was clarifying exactly how the algorithm was to be performed?

$\endgroup$
  • $\begingroup$ I can't figure out what this bit is referring to at all (let alone much of the rest being rather unclear): "… and carry out the subtractions". Which subtractions? $\endgroup$ – horchler Jul 2 '13 at 23:06
  • $\begingroup$ What are your other questions about this? :-) $\endgroup$ – ShreevatsaR Jul 5 '13 at 9:36
11
$\begingroup$

I was able to reverse-engineer the method of Matsunaga Ryohitsu and find that it does work, modulo understanding the following two points about it, that are not necessarily clear from the wording (either Mikami's or Dickson's):

  • When it is impossible to subtract a $b_i$ from the current remainder $A$, what we must add to $A$ is the next unused $a_j$ (after the latest $a_{j-1}$ used), which is not necessarily the "corresponding" $a_i$ (i.e., $j$ may be a smaller index than $i$). Alternatively, instead of changing $a_{j+1} = a_j - 2$ at every step, we change it only when required. That is, the $a_i$'s and $b_i$'s aren't meant to be recalculated simultaneously at each step, but the next $a_i$ is only to be picked when necessary. This is clearer from Mikami's wording than Dickson's.

  • Mikami's wording "let the values of $a$ and $b$ employed in the last place be $a'$ and $b'$" (or Dickson's "$a', b'$ are the values last employed") are probably not what the original intended, which seems to be to take $a'$ and $b'$ to be the next ones after the ones last used in an addition or subtraction. This can be sort of coerced to fit the original wording, if we imagine that as soon as we use up an $a_j$ or a $b_i$, we write the next ones immediately, and so $a'$ and $b'$ are taken to be the last ones writen down.

With that in mind, the method can be viewed as follows. We want $x^2 + y^2 = k$, so we want to search over all pairs of positive integers $(x, y)$ until we find a pair satisfying the equation. We will organize the search as follows. Let $\frac{k}2 = r^2 + R$ (where $r^2$ is the largest square not greater than $\frac12k$, and $R$ is the "remainder") so that $k = 2r^2 + 2R$. If we assume wlog that $x \le y$, we see that we must have $\color{red}{y \ge r}$ (because if $x \le y < r$, then $x^2 + y^2 < 2r^2 \le k$) and that $\color{red}{x \le r}$ (because if $r < x \le y$, then $x^2 + y^2 \ge 2(r+1)^2 > k$).

So let's start with $x, y$ both equal to $r$, for which $x^2 + y^2 = 2r^2 \le k$. We will successively increment $y$ by $1$ at a time as long as $x^2 + y^2 \le k$, then when we have overshot $k$ we will decrement $x$ by $1$ and continue, and so on. It is clear that this method will always work and find a solution if one exists, as it's an exhaustive search over all potential solutions $(x,y)$: for every $y \ge r$, we try the largest $x$ such that $x^2 + y^2 \le k$.

The beauty of this method is that accomplishes the exhaustive search without any squaring or multiplications, just additions and subtractions, that too of relatively smaller numbers.

More concretely, for a fixed $x$, suppose we increase $y$ by $1$. When we replace $y$ with $y+1$, the left-hand side (namely $x^2 + y^2$) increases to $x^2 + (y+1)^2$, i.e., it increases by $2y + 1$: twice the current candidate value for $y$, plus $1$. Or, if we consider candidates for $2y$ instead, the left-hand-side increases by the current candidate (for $2y$) plus $2$. This is what the $b$'s are doing in the method. (As the final $y = \frac12(b' - 1)$, this means $b' = 2y + 1$.)

Similarly, when we increase $y$ by too much, the left-hand side $x^2 + y^2$ will overshoot the right-hand side, and to compensate, it is time for try the next lower value for $x$ (or equivalently, for $2x$). When we replace $x$ with $x-1$, the left-hand side changes from $x^2 + y^2$ to $(x-1)^2 + y^2$, decreasing by $2x-1$, or twice the current value minus $1$. Or, if we consider candidate values for $2x$, it decreases by the current value for $2x$ minus $2$. These are the $a_j$'s, shifted by $1$. (As the final $x = \frac12(a' + 1)$, this means that $a' = 2x - 1$.)


A complete description of the method

We maintain, at all times $t$, a pair of integers $(x_t, y_t)$ such that $x_t^2 + y_t^2 \le k$. However, we won't work directly with the numbers $(x_t, y_t, k)$ except to output a solution; instead we work with the numbers $$\begin{align} a_t &= 2x_t - 1 ,\\ b_t &= 2y_t + 1, \\ A_t &= k - (x_t^2 + y_t^2). \end{align}$$

  1. Initially, at $t = 1$, (with the idea that $x_t = y_t = r$) set $a_t = 2r - 1$, $b_t = 2r + 1$, and $A_t = k - 2r^2$, where $r^2$ is the largest square not greater than $\frac{k}2$.

  2. If $A_t = 0$, output the solution $x_t = \frac12(a_t + 1)$, $y_t = \frac12(b_t - 1)$.

  3. While $A_t < b_t$, [need to decrease $x_t$ to make room for $y_t + 1$]

    • Set $A_{t+1} = A_t + a_t$ and $a_{t+1} = a_t - 2$, keeping $b_{t+1} = b_t$.
    • Increase $t$ to $t+1$.
  4. [Now that $A_t \ge b_t$, can update $y_{t+1} = y_t + 1$.]
    Set $A_{t+1} = A_t - b_t$ and $b_{t+1} = b_t + 2$, keeping $a_{t+1} = a_t$.
    Update $t$ to $t+1$ and go back to step 2.

(Note that when we output a solution, we don't have to stop. If we keep going, we'll find all other solutions as well, if they exist. We can stop when $a_t < 0$.)


Some examples of the method (we don't have to restrict ourselves to even $k$), including all the ones in your question and more:

  • $k = 5$. In this case, $\frac12k = \frac52 = 1^2 + \frac32$, so $r = 1$ and $A_1 = 2R = 3$. Start with $a_1 = 2r - 1 = 1$, and $b_1 = 2r + 1 = 3$. Subtract, from $A = 3$, the current $b$: you already get $0$, so $a' = a_1 = 1$, and $b' = b_2 = b_1 + 2 = 5$. Now $x = \frac12 (a' + 1) = 1$ and $y = \frac12 (b' - 1) = 2$ is indeed a solution.

  • $k = 10$. In this case, $\frac12k = 5 = 2^2 + 1$, so $r = 2$ and $2R = 2$. Start with $a_1 = 2r - 1 = 3$ and $b_1 = 2r + 1 = 5$. It is already impossible to subtract $b_1$ from $A = 2R$, so add $a_1$ and carry out the subtraction: we get the new remainder $A$ to be $2R + a_1 - b_1 = 2 + 3 - 5 = 0$. So $a' = a_2 = a_1 -2 = 1$, and $b' = b_2 = b_1 + 2 = 7$. Now $x = \frac12(a' + 1) = 1$ and $y = \frac12(b' - 1) = 3$ is indeed a solution.

  • $k = 13$. We have $\frac12k = 2^2 + \frac52$, so $r = 2$ and $2R = 5$. $a_1 = 2r - 1 = 3$, $b_1 = 5$. Subtracing $b_1$ from $A=2R$ gives remainder $0$, so $a' = a_1 = 3$, and $b' = b_2 = 7$. This gives the solution $x' = \frac12(a' + 1) = 2$ and $y' = \frac12(b' - 1) = 3$.

  • $k = 17$. We have $\frac12k = 2^2 + \frac92$, so $r = 2$ and $2R = 9$. $a_1 = 2r - 1 = 3$, $b_1 = 5$. Update $A=2R$ to $A - b_1 = 4$. Next we cannot subtract $b_2 = 7$ from it, so add $a_1 = 3$ and subtract. Remainder is $0$, so $a' = a_2 = 1$, $b' = b_3 = 9$. This gives the solution $x' = \frac12(a' + 1) = 1$ and $y' = \frac12(b' - 1) = 4$.

  • $k = 41$. In this case, $\frac12k = 4^2 + \frac92$, so $r = 4$ and $2R = 9$. Start with $a_1 = 2r - 1 = 7$, and $b_1 = 2r + 1 = 9$. Subtracting $b_1$ from $A = 2R$ already gives remainder $0$, so $a' = a_1 = 7$ and $b' = b_2 = b_1 + 2 = 11$. Now $x' = \frac12(a' + 1) = 4$ and $y' = \frac12(b' - 1) = 5$ is indeed a solution.

  • For something less trivial, consider $k = 218$. In this case, $\frac12k = 109 = 10^2 + 9$, so $r = 10$ and $2R = 18$. Start with $a_1 = 2r - 1 = 19$, and $b_1 = 2r + 1 = 21$. Subtracting $b_1$ from $A = 2R$ is already impossible, so add $a_1$ and carry out the subtraction: the new value of $A$ is $2R + a_1 - b_1 = 16$, meanwhile we compute new values $a_2 = a_1 - 2 = 17$ and $b_2 = b_1 + 2 = 23$. Again, subtracting $b_2$ from $A$ is impossible, so we add $a_2$, thus setting $A$ now to $16 + a_2 - b_2 = 10$. Next compute $a_3 = a_2 - 2 = 15$, and $b_3 = b_2 + 2 = 25$. This time, subtracting $b_3$ is still not possible, but magically, it works if we add $a_3$, and indeed we get remainder $0$. So $a' = a_4 = a_3 -2 = 13$, and $b' = b_4 = b_3 + 2 = 27$. Now, $x' = \frac12(a' + 1) = 7$ and $y' = \frac12(b' - 1) = 13$ indeed a solution.

$\endgroup$
  • $\begingroup$ I've enjoyed watching your great answer grow into a fantastic answer! Thanks a lot. The main point I was missing was your second bullet at the top --- I never tried the next unused a and b. I'm not surprised since I was doing it all in my head, and as you said, it helps to interpret the wording as writing down the next a and b the instant you've used the prior ones. $\endgroup$ – Barry Smith Jul 5 '13 at 13:44
  • 1
    $\begingroup$ That helped. I put together a simple Matlab function to demonstrate the algorithm for everyone to view and download. I still found your "A complete description of the method" section not completely straightforward, so let me know if the code is lacking in any way. @BarrySmith, my code does output multiple solutions if found, e.g., k=50 or k=325. $\endgroup$ – horchler Jul 5 '13 at 22:55
  • $\begingroup$ @horchler: Nice, your code is exactly what I meant. Which part did you find not entirely straightforward, so that I can improve it? (One thing I did genuinely miss is the "&& a >= 0" condition on the inner loop, that we may have to stop the loop when there's no longer hope of termination / when the termination condition of the whole program is reached.) $\endgroup$ – ShreevatsaR Jul 6 '13 at 3:19
  • $\begingroup$ @ShreevatsaR: Following your steps 1–4, partly what confused me was your comments in square brackets, which I didn't realize were comments at the time. Also, in your examples you use 2*R (=A), which isn't in your method and which, despite being in the originals is unnecessary. And yes, the && a >= 0 was necessary to not lock up in some cases -I surmised that from your comment about stopping when a < 0. Finally, I'm not sure that it helps to use an iteration index t even though the original formulations use one. I find it superfluous and think that the method could be described with out it. $\endgroup$ – horchler Jul 6 '13 at 14:38
  • $\begingroup$ Great work!(+1) @horchler Nice code! $\endgroup$ – vesszabo Jul 10 '13 at 20:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.