Here is a factoring algorithm that seems to me might not
take as many computation steps as most. Nevertheless,
it
is still impractical, as shall shortly be seen.

Consider some composite number (c) that we wish to
factor --find two numbers (a) and (b) such that when
multiplied together,
their product is (c). It is widely
known that if one computes the square root of (c), one
of
its factors will be smaller than that square-root, and one
will be larger (provided (c) was not a perfect square, of
course!).

Next, I happen to have a scientific calculator that has a
"factorial" button. I can specify a number like 50, and it
will compute 1 times 2 times 3 times 4 times 5 times 6
...
up to and including 50. The result is approximate, and I
THINK the calculator does not actually do all those
individual multiplications --some sort of shortcut like
adding logarithms is probably involved.

Here I will assume that the "shortcut", whatever it is, is
efficient enough to compute a quite-large factorial in a
reasonable time. This is where the impracticality of this
Idea begins to become apparent. We need a highly
accurate answer, not just an approximation!

What we need it for (I'll get back to the impracticality in
a
bit) is the last part of the algorithm, which invokes the
Greatest Common Divisor function. Let me provide an
example, using (c)=209.

The square root of 209 is 14.irrational, so that means one
of the factors of 209 is 14 or less (well, not 14 because
that is
an
even number, and 209 is odd). Let's therefore compute
the factorial of 13, which is 6227020800. When we plug
that number and 209 into the Greatest Common Divisor
function ... it works (pretty efficiently!) like this:

Divide 6227020800 by 209 to get 29794357 and a
remainder
of 187. Now divide 209 by 187 to get 1 and remainder
of
22. Now divide 187 by 22 to get 8 and a remainder of
11. (Every just-found remainder becomes the divisor
into the previous divisor.)
Now divide 22 by 11 to get 2, exactly. Therefore 11
must
be a common divisor --a factor!-- of both 209 and our
initial factorial. (When no new remainder is found, the
common divisor is always the last-found remainder, the
last divisor.
Note the function ALWAYS finds a
common divisor, even if it is simply the number 1.)

The impracticality is, when (c) is a large number, the
factorial we need will be a number so vast it literally
cannot be processed, having more digits than the total
number of atoms in the Universe. Being able to compute
the needed factorial in relatively few STEPS is not useful
if
the last step requires a computer that just plain can
never
be built!

Ah well. For the HalfBakery, though, this Idea could still
be worthy of posting. I hope you enjoyed it.

Title change neededhttps://duckduckgo....+math&t=ffsb&ia=web I suggest changing the name of the piece to "Research Grant Overstock Sale!" to get professional scientistists to view this? I like the thought though. [Sunstone, Jul 06 2017]

Please log in.
If you're not logged in,
you can see what this page
looks like, but you will
not be able to add anything.

Description (displayed with the short name and URL.)

There is another type of number, similar to a factorial,
but smaller (and probably has no shortcut for computing),
that could also be used in this factoring technique. I
don't know what mathematicians call this type of number,
but I'm sure they know all about it. Here, I will call it a
"shrunken factorial".

While an ordinary factorial is derived from multiplying
every number from 1 to (n), and therefore is exactly
divisible by every number from 1 to (n), a shrunken
factorial only
involves multiplying the bare minimum of numbers, such
that it is still exactly divisible by every number from 1 to
(n).

1*2*3*2, for example, equals 12 and is divisible by 1, 2, 3,
and 4. 1*2*3*2*5*1*7*2*3*1*11*1*13, for another example,
equals 360360, and is divisible by every number from 1 to
13. See how "shrunk" 360360 is, compared to
6227020800, factorial 13 used in the main text? (360360
is also
already divisible by 14 and 15.)

If we plugged 360360 along with 209 into the Greatest
Common Divisor function, we would get 1724 as the first
quotient, and a remainder of 44. 209 divided by 44 is 4
with a remainder of 33; 44 divided by 33 is 1 with a
remainder of 11, and 33 divided by 11 is 3, exactly, so
again we find 11 as factor of 209.