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.
-- Vernon, Jul 05 2017

Title change needed https://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]

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.
-- Vernon, Jul 08 2017



random, halfbakery