A multiplication algorithm found in a book by Paul Erdős: how does it work?

This method is often called "Russian peasant multiplication".

It's often justified by thinking about writing the first number in binary. Here's another way to explain it. At each step, we're replacing a pair $(p,q)$ either by $(\frac{p}{2}, 2q)$ (when $p$ is even) or by $(\frac{p-1}{2},2q)$ (when $p$ is odd).

• In the first case, when $p$ is even, the product of the two numbers doesn't change: $p \cdot q = \frac{p}{2} \cdot 2q$.
• In the second case, when $p$ is odd, $\frac{p-1}{2} \cdot 2q = p \cdot q - q$. So the product has decreased by $q$, and we should set $q$ aside for later.

Eventually, we get to a pair $(1,r)$ whose product is easy to compute: it's just $r$. Because we've kept track of how the product of a pair has changed, we know that the original product is equal to this product, plus all the numbers we've set aside.

But we set aside $q$ from the pair $(p,q)$ whenever $p$ is odd. So adding the numbers we set aside to the final number just corresponds to adding up the second number in every pair whose first number is odd.

---

You also wanted to know what the sum of the numbers opposite an even number represents.

Given a $p$ and $q$ you want to multiply, choose $k$ such that $2^{k-1} - 1 < p \le 2^k - 1$. (In other words, $2^k$ is the next power of $2$ after $p$, not including $p$ itself.)

Then if we use this algorithm to find $(2^k-1)\cdot q$, we'll take the same number of steps to get to $1$ on the left-hand side, but all the left-hand numbers along the way are odd. This tells us that the sum of all the right-hand numbers should be the product $(2^k-1) \cdot q$.

Since the sum of all the right-hand numbers opposite an odd left-hand number is $p \cdot q$, the sum of all the right-hand numbers opposite an even left-hand number is their difference $(2^k-1-p) \cdot q$.

Write $75$ in binary: $\mathtt{1001011}$; now write down a table starting from the rightmost digit (I use $75$ to avoid undesired symmetry): $$ \begin{array}{lrr} \mathtt{1}=a_0 & 75 & 217 \\ \mathtt{1}=a_1 & 37 & 434 \\ \mathtt{0}=a_2 & 18 & 868 \\ \mathtt{1}=a_3 & 9 & 1736 \\ \mathtt{0}=a_4 & 4 & 3472 \\ \mathtt{0}=a_5 & 2 & 6944 \\ \mathtt{1}=a_6 & 1 & 13888 \end{array} $$ As you can see, odd numbers in the center column correspond to a digit $\mathtt{1}$ in the binary representation. This is not by chance: removing the rightmost digit from the binary representation is exactly dividing by $2$ (discarding the remainder) and a rightmost digit $\mathtt{1}$ means the number is odd.

The factor $m=75$ is written $$ m=2^0a_0+2^1a_1+2^2a_2+2^3a_3+2^4a_4+2^5a_5+2^6a_6 $$ Therefore, if $n=217$, the product is \begin{align} mn&=(2^0a_0+2^1a_1+2^2a_2+2^3a_3+2^4a_4+2^5a_5+2^6a_6)n \\ &=2^0a_0n+2^1a_1n+2^2a_2n+2^3a_3n+2^4a_4n+2^5a_5n+2^6a_6n \\ &=\begin{aligned}[t] &a_0\cdot (2^0n)+{}\\ &a_1\cdot (2^1n)+{}\\ &a_2\cdot (2^2n)+{}\\ &a_3\cdot (2^3n)+{}\\ &a_4\cdot (2^4n)+{}\\ &a_5\cdot (2^5n)+{}\\ &a_6\cdot (2^6n) \end{aligned} \end{align} Each number in parentheses in the final sum (written in column) is twice the preceding one (starting from $n$). Now, using the explicit data, we get $$ \begin{array}{r@{}rl} 1\cdot{}&217 &+ \\ 1\cdot{}&434 &+ \\ 0\cdot{}&868 &+ \\ 1\cdot{}&1736 &+ \\ 0\cdot{}&3472 &+ \\ 0\cdot{}&6944 &+ \\ 1\cdot{}&13888 &=\\ \hline &217 &+ \\ &434 &+ \\ &1736 &+ \\ &13888 &=\\ \hline &16275 \end{array} $$

If you use all terms in the final column of the first table, you are multiplying $217$ by the binary number $\mathtt{1111111}=2^7-1=127$.

So the sum of the numbers opposite the even digit corresponds to the product $217\cdot(127-75)$.

Another way of putting it for anyone else who comes by and reads this:

At first you have a bunch of $217$s. $73$ of them. That's $73 \cdot 217$. You divide on one side and double on the other so the product remains the same.

But you have to round down when you halve $73$. So instead of saying $73 \cdot 217$ you say $72 \cdot 217 + 1 \cdot 217$. Then you can say you have $36 \cdot 434 + 1 \cdot 217$.

You "left behind" a $217$ when you rounded down. Likewise you also end up "leaving behind" the $1736$. So at the end, before you can say you're done, you have to go back and account for the numbers you left behind.