This is the output of an exercise I attempted to complete in 2017 and again in 2018, both times to no avail. It turned out that the third time was indeed a charm: I successfully completed it in 2021.
Why had I wanted to complete this exercise in the first place? Again, out of curiosity. I knew it was a thing that sometimes the product of two numbers would have fewer digits than the sum of the digits of the original two numbers and sometimes the product would have the same number. But what was the rule?
The text below provides an answer to the question. I now present this for your reading pleasure. Enjoy!
Update 1 – 13 February 2023: I edited the last paragraph of the main post to make the logical path to the conclusion clearer to you the reader. I also edited the example in the postscript to better illustrate what the penultimate paragraph of the post was saying with respect to updating coefficients as one goes.
Hello there. And welcome. I trust this finds you well.
Now that you are here, let’s get started.
Statement
Let A and B be positive whole numbers (natural numbers), with AB being their product.
Let A have X digits and B have Y digits, where X and Y are both natural numbers.
Then AB has either X+Y-1 or X+Y digits, without exception.
Proof
We work in a base-N number system, where N is a natural number greater than 1.
(For clarity, a base-N number system is a number system in which every number is represented using a linear combination of powers of N and coefficients ranging from 0 to N-1. For example, in the base-10 (decimal) number system that we generally use around the world, 123,456,789 = 1 * 108 + 2 * 107 + 3 * 106 + 4 * 105 + 5 * 104 + 6 * 103 + 7 * 102 + 8 * 101 + 9 * 100.)
A has X digits. B has Y digits. Therefore C = AB has at least X+Y-1 digits.
Remember:
A = a0 + a1N + a2N2 + … + aX-1NX-1;
B = b0 + b1N + b2N2 + … + bY-1NY-1;
C = (a0 + a1N + a2N2 + … + aX-1NX-1)(b0 + b1N + b2N2 + … + bY-1NY-1) = g0 + g1N + g2N2 + … + gX+Y-2NX+Y-2.
Let K be a non-negative whole number (i.e. 0 [zero] or greater). Beginning with g0, replace each coefficient gK in the expression of C with cK = gK modulo N (the remainder from dividing gK by N). Then divide (gK – [gK modulo N]) by N and add it to gK+1. Then repeat what you have just done with gK+1 and with every coefficient thereafter, until you run out of coefficients to process.
Finally, look at gX+Y-2, the amended coefficient of NX+Y-2. If gX+Y-2 is less than N, then C has X+Y-1 digits (cX+Y-2 = gX+Y-2). Otherwise, repeat the process in the preceding paragraph one more time. In that case, C has X+Y digits (cX+Y-1 = (gX+Y-2 – [gX+Y-2 modulo N])/N).
QED
Hereunder lies an example to illustrate the method above. I will use 998,001 = 999 * 999, in the decimal (base-10) number system.
999 * 999 = (9 * 1 + 9 * 10 + 9 * 100) * (9 * 1 + 9 * 10 + 9 * 100)
= 81 * 1 + 162 * 10 + 243 * 100 + 162 * 1000 + 81 * 10,000
= 1 * 1 + 170 * 10 + 243 * 100 + 162 * 1000 + 81 * 10,000
= 1 * 1 + 0 * 10 + 260 * 100 + 162 * 1000 + 81 * 10,000
= 1 * 1 + 0 * 10 + 0 * 100 + 188 * 1000 + 81 * 10,000
= 1 * 1 + 0 * 10 + 0 * 100 + 8 * 1000 + 99 * 10,000
= 1 * 1 + 0 * 10 + 0 * 100 + 8 * 1000 + 9 * 10,000 + 9 * 100,000
= 998,001.