Half a croissant, on a plate, with a sign in front of it saying '50c'
h a l f b a k e r y
We have a low common denominator: 2

idea: add, search, annotate, link, view, overview, recent, by name, random

meta: news, help, about, links, report a problem

account: browse anonymously, or get an account and write.



Fantastic Factoring Failure

Discovering an infinity of useless solutions
  [vote for,

I've mentioned elsewhere that I've put some time into playing with a math problem that is thousands of years old. Given the value (c), and told it equals (a)*(b), the problem is to efficiently discover (a) and (b). So far, all known solutions take a ridiculous amount of time to find (a) and (b) when (c) is a very large number (say, a thousand digits long). **

Some of the solutions are easy to understand, even if they are not efficient. One of the most famous is called "Fermat factoring", after the guy who discovered it. If you can find two numbers (m) and (n) such that (m^2) - (n^2) = (c), then (a) will equal (m)- (n) and (b) will equal (m)+(n). For example, if (c)=91, then it happens that 100-9 equals 91, and since 100=10^2 (pronounced "ten squared"), and 9=3^2, we can figure (a)=10-3=7 and (b)=10+3=13 --that is, 7*13=91.

In my own messing around I happened to notice that the above can also work for *any* *multiple* of (c). This means there are an infinite number of ways to find the factors (a) and (b). Only one additional step is needed, as explained in the following example:

Suppose (c)=91 again, but instead of finding the squares 100 and 9, we found the squares 7921 and 2916. Subtracting the smaller number from the larger yields 5005, which happens to equal 91*55 --that is, 5005 is a multiple of (c). Since 7921=89^2 and 2916=54^2, we can compute the factors 89+54=143 and 89-54=35 --and 143*35=5005.

That doesn't directly find a factor of (c), but the "additional step" previously mentioned is The Greatest Common Divisor Function. Plug our (c) of 91 and either 143 or 35 into that function, and it will discover that (c) and 143 have the number 13 as common divisors, or discover that (c) and (35) have the number 7 as common divisors. Which means numbers that actually divide exactly into (c) --the factors of (c)-- can indeed be found, an infinite number of ways.

Well!! Here's a little thing I happened to notice a while back:
15^2 - 4^2 = 209, 16^2 - 5^2 = 231, 17^2 - 6^2 = 253, 18^2 - 7^2 = 275
209 + 22 = 231, 231 + 22 = 253, 253 + 22 = 275
A sequence of pairs of numbers, each pair separated by a difference of 11, reveals a constant-growing sequence of differences between the squares of those numbers.

12^2 - 8^2 = 80, 13^2 - 9^2 = 88, 14^2 - 10^2 = 96, 15^2 - 11^2 = 104
80 + 8 = 88, 88 + 8 = 96, 9 + 8 = 104
Another sequence, difference of 4, reveals another constant- growth sequence of differences between their squares.

21^2 - 3^2 = 432, 22^2 - 4^2 = 468, 23^2 - 5^2 = 504, 24^2 - 6^2 = 540
432 + 36 = 468, 468 + 36 = 504, 504 + 36 = 540
Another sequence and another constant-growth situation.

We seem to have a generic thing, there. Now look at the constant-growth results written this way:

Next, remember that *any* multiple of (c) can be equal to the difference between two squares. So here's another sequence: (c)+(c)+(c)+(c)+...

Now look at the link below, another Idea I posted a while back (and which just happens to include the Greatest Common Divisor Function). It presents an easy way to find the place where two sequences intersect at a particular number, when one sequence can be written as A+B+B+B+... and the other can be written as C+C+C+...


It works, too! That is, it finds a number at which both series intersect *very* quickly (about as efficiently as if doing a "binary search").

BUT! It doesn't help us factor (c)! It turns out that there is a whole other infinity of ways that the difference between two squares can be a multiple of (c), and those two squares have no relationship to the actual factors of (c). They only relate to factoring the *multiple* of (c), into (c) and the multiplier!

Basically, any time we *arbitrarily* pick two squares, and try to use them as explained above, creating a sequence describe-able as A+B+B+B+... --the intersection of that series with the sequence of multiples of (c) will probably not help us factor (c). Alas!

Sometimes I think I gotta stop getting my hopes up, regarding finding an efficient solution to the ancient factoring problem. But I still hope you enjoyed this little excursion into two infinities of possibilities.


** Quantum computers are expected to be able to factor large values of (c) efficiently. But to me, that feels like "cheating" - -technically, the method brute-forces division by all possible divisors simultaneously. I want a good old-fashioned type of solving algorithm!

Vernon, Sep 06 2016

Finding the intersection of two series (A_2bxB)_2fC_20_3d_20y
As mentioned in the main text. [Vernon, Sep 06 2016]


       I'm inclined to suggest a Sieve of Eratosthenes, the one with the superconductivity kit, but that's what I always say.
not_morrison_rm, Sep 06 2016

       I am ignant about the maths. But I can do some excel. It seemed to me that one could solve for m^2 if you know C by picking a random n and then C - n^2 = m ^2. But no.   

       I take it the Fermat's deal works only if m^2 and n^2 are perfect squares and all numbers are whole numbers.
bungston, Sep 06 2016

       I think I might be able to follow this if it were presented on Khan Academy in some presentatuon form. But reading it here is downright work.
RayfordSteele, Sep 06 2016


back: main index

business  computer  culture  fashion  food  halfbakery  home  other  product  public  science  sport  vehicle