devRant - A fun community for developers to connect over code, tech & life as a programmer

Managed to derive an inverse to karatsuba's multiplication method, converting it into a factorization technique.

Offers a really elegant reason for why non-trivial semiprimes (square free products) are square free.

For a demonstration of karatsubas method, check out:
https://getpocket.com/explore/item/...

Now for the reverse, like I said something elegant emerges.

So we can start by taking the largest digit in our product. Lets say our product is 697.

We find all the digits that produce 6 when summed, along with their order.

thats (1,5), (5,1), (2,4), (4,2), and (3,3)

That means for one of our factors, its largest digit can ONLY be 1, 5, 2, 4, or 3.

Lets take karatsubas method at step f (in the link) and reverse it. Instead of subtracting, we're adding.

If we assume (3,3)

Then we take our middle digit of our product p, in this case the middle digit of 697. is 9, and we munge it with 3.

Then we add our remaining 3, and our remaining unit digit, to get 3+39+7 = 49.

Now, because karatsuba's method ONLY deals with multiplication in single digits, we only need to consider *at most* two digit products.
And interestingly, the only factors of 49 are 7.
49 is a square!

And the only sums that produce 7, are (2,5), (5,2), (3,4), and (4,3)

These would be the possible digits of the factors of 697 if we initially chose (3,3) as our starting point for calculating karatsubas inverse f step.
But you see, 25 can't be a factor of p=697, because 25 is a square, and ends in a 5, so its clearly not prime. 52 can't be either because it ends in 2, likewise 34 ending in 4.
Only 43 could be our possible factor of p.

And we *only* get one factor because our starting point has two of the same digit. Which would mean p would have to equal 43 (a prime) or 1. And because p DOESNT (it equals 697), we can therefore say (3,3) is the wrong starting point, as are ALL starting points that share only one digit, or end in a square.

Ergo we can say the products of non-squares, are specifically non-prime precisely because if they *were* prime, their only factors would HAVE to be themselves, and 1.

For an even BETTER explanation go try karatsuba's method with any prime as the first factor, and 1 as the second factor (just multiply the tens column by zero). And you can see why the inverse, where you might try a starting point that has two matching digits (like 3,3), would obviously fail, because the values it produces could only have two factors; some prime thats not our product, or the value one, which is also not our product.

It's elegant almost to the level of a tautology.

random