I am trying to understand the following problem from Erdős and Surányi's Topics in the theory of numbers (Springer), chapter 1 ("Divisibility, the Fundamental Theorem of Number Theory"):
We can multiply two (positive integer) numbers together in the following way. Write the two numbers down next to each other. Divide the first in half, rounding down to an integer, and write the result below it. Double the second number, writing the result below it. We continue this halving / doubling until we are left with $1$ in the first column. Cross out all those numbers in the second column that are opposite an even number and add the remaining numbers in this column together to get the product. Prove that this works.
And this is an example, $73 \cdot 217$:
Then $73 \cdot 217 = 217+1736+13888 = 15841$, which is correct.
... and I really cannot visualize the reason why it works. My thoughts so far:
We are dividing by $2$ in the left column, so only those values that are odd are coming from a division of a previous even number in the left column, and that means that the previous division by $2$ was "perfect", meaning without decimals.
I can approximate the value of the product of two natural numbers $p \cdot q$ if I divide the first number by $2$ continuously until it arrives at $1$ and multiply the second by $2$ at the same time (so the final value of the second one is an approximation of the product).
But why do we remove some of them for the final sum? I would like to ask the following questions:
How does it work?
We are summing the numbers of the second column that are opposite an odd number. Then what does the sum of the numbers that we do not use from the second column represent?
This is all probably pretty obvious, but I cannot see the light.