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:
209+22+22+22+...
80+8+8+8+...
432+36+36+36+...
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!