This Idea takes my original Factoring Algorithm post (linked) and kicks it into a new direction. The result works, but it remains to be determined whether or not it can actually be useful/efficient when trying to factor large numbers.
The composite number that I'll pick, to explain this particular algorithm-variant, is 'c'=2581. Its square root is 50-and-an-irration, which I'll arbitrarily adjust to become 51, so that 'r' can be an odd number. The nodulus 'n' is therefore 2581-(51^2)=-20. But now, instead of computing some trial values with the original-algorithm equation '(r)(y-x)-n=(x)(y)', I will apply some algebraic manipulations to it, first.
It can easily become '(r)(y)-(r)(x)-(x)(y)=n', and from there, two similar but different results can quickly follow: '(r-x)(y)=(r)(x)+n' or '(r)(y)-n=(r+y)(x)'. From there, a modest additional manipulation yields either 'y=[(r)(x)+n]/(r-x)' or '[(r)(y)-n]/(r+y)=x'.
Either of those equations would let us pick arbitrary trial values for one variable ('x' or 'y'), and let us compute the value for the complementatry variable ('y' or 'x'). Now recall that it was previously deduced that if 'r' and 'c' are odd numbers, then 'x' and 'y' must be even numbers --and that 'x' is smaller than 'r'. Therefore, possible values for 'x' range from '0' to 'r-3', while possible values for 'y' range from '0' to about '(c/3)-r' --a much wider range than for 'x', since 'c' is roughly equal to the square of 'r'. The logical equation to use is therefore 'y=[(r)(x)+n]/(r-x)', since fewer trials need be done.
So, here are some initial trial results, when 'r'=51 and 'n'=-20: x=0; y= -20/51 x=2; y= 1 & 33/49 x=4; y= 3 & 43/47 x=6; y= 6 & 16/45 x=8; y= 9 & 1/43
It might be noted that since those fraction-denominators are computed from the expression 'r-x', each one is actually a trial value for 'a', in the original Factoring Problem equation '(a)(b)=c'. One can therefore immediatly wonder why we are bothering with this, when we might as well just directly attempt to divide 'c' by that sequence of denominators. But, since this is the HalfBakery...not to mention that there are Equations Ahead, theoretically allowing us to AVOID doing many more trial divisions than were just done....
None of those trial values for 'x' let us solve the factoring problem for 'c'=2581, because we most certainly need 'y' to be computed as a whole integer, not as something-and-a-fraction. But another way of saying that is to note that for SOME value of 'x', the numerator of the fractional part WILL be Zero. THAT's the thing we are going to look for, using Parallel Parabolas.
Note how those last three numerators form something of a series: 43, 16, 1, which descends toward Zero. Will the next trial for 'x' yield the desired integer for 'y'? x=10; y= 11 & 39/41 --nope. However, it is now time to mess around with the above fractions....
As presented, those fractions are in a "standard" form (well, I added the "&" symbols for clarity, not because they had to be there). But nonstandard fractions can still be perfectly valid representations of various quantities. For example, '1 & 33/49' could be written as '0 & 82/49', while '11 & 39/41' could be written as '12 & -2/41'. But why would we want to do that?
Well, that earlier-mentioned "series" of numerators now has FIVE descending terms: 82, 43, 16, 1, -2 --and it actually IS a TRUE series! Look what happens when we take the differences between those numbers a couple of times (ignore the underscores): 82 _ _ 39 43 _ _ _12 _ _ 27 16 _ _ _12 _ _ 15 1 _ _ _ 12 _ _ 3 -2 One way to prove it is a true series is to first assume it continues, and, second, use the series to figure the next value after the -2: 1 _ _ _ 12 _ _ 3 -2 _ _ _12 _ _-9 7 and, third, go back to the earlier equation 'y=[(r)(x)+n]/(r-x)' and try the next value for 'x': x=12; y= 15 & 7/39 --yes!, the numerator is 7. (For the doubtful, please recall that if 1-3= -2, then -2-(-9)= -2+9= 7.)
OK, well, there is a kind of "formula" which can take some numbers from the above, and can then be used to generate any number in the series. This formula is: (I)-(J)(d)+[(K)(d)(d-1)]/2
The values for 'I' and 'J' and 'K' can be any of several PARTICULAR groups of 3 numbers from the above tabulation, such as 82, 39, and 12 --or 43, 27, and 12 --or 16, 15, and 12 -- or 1, 3, and 12. After choosing a particular group as a kind of "starting point", variable 'd' is a "distance" away from 'I' (either positive or negative). When you pick a non-zero value for 'd' and do the computation, the result is some other number in the series (if you set 'd=0' the result is the value of variable 'I', of course).
As a demonstration, I'll pick the particular group 16, 15, and 12 as the values for 'I', 'J', and 'K', respectively. Therefore the formula becomes '16-(15)(d)+ [(12)(d)(d-1)]/2' --and it can be algebraically manipulated/simplified to become '16-(21)(d)+(6)(d^2)'.
So, if I set 'd=2' the formula computes 16-42+(6)(4)=-2, and if I set 'd=-2' the formula computes 16+42+(6)(4)=82. It happens that if you plotted the input values and the output values appropriately on graph paper, this formula generates various points of the geometric curve known as a "parabola".
It also happens that essentially the SAME parabola will be generated if you chose any other "particular" group-of-3-numbers from the above tabulation, for the 'I', 'J', and 'K' values of that formula. The parabola would be located in a slightly different place on the graph paper, and that's the only difference.
Now, what does all that have to do with factoring 'c=2581'? I'm getting there; I promise! Because the next thing to note is that that formula is malleable in another and highly relevant manner: It can be worked BACKWARD, if we plugged it into the well-known "Quadradic Formula".
You should recall that if some equation can be written in the form of '(A)(x^2)+(B)(x)+C=0', then the Quadratic Formula can be used to solve that equation for the value of 'x'. With respect to the 'I,J,K' formula above, no particular output value (such as Zero) was specified, but we could certainly specify something if we wanted to. And, wasn't it stated earlier that we had a series that descended toward Zero? And, wasn't Zero the actual goal-numerator that we desire? It therefore quite logically follows that we WANT an equation such as '16-(21)(d)+(6)(d^2)=0'....
On the other hand, we already know that that particular equation does not work to yield Zero, if 'd' is an integer value. It was obvious, after all, that our parabolic series of numbers went right past Zero into negative territory, and then climbed out of the hole and skipped right past Zero again!
What to do?
The Answer Is: Play With Those Numerators Some More!
Here's the logic: Because of the way we started working with values of 'x' for the equation 'y=[(r)(x)+n]/(r-x)', we know that the desired value of 'x', which lets us factor 'c', must be greater than any value so far tried. And from inspection of the way a couple of numerators were manipulated earlier, if we ADDED denominators to create new numerators, ALL the results would be greater than Zero (the whole associated parabola would fail to intersect the "zero line" on the graph paper). But if we subtracted denominators from the numerators, we could create a new series of mostly-negative numbers that, SOMEWHERE along the parabolic curve, must cross the Zero line.
Trying it (subtracting appropriate denominators from our previous series), we obtain: 82-49=33 43-47=-4 16-45=-29 1-43=-42 -2-41=-43 7-39=-32 --And, yes, we can see this new sequence of numbers certainly skips past Zero, bottoms out at -43, and starts up toward Zero again. Will it intersect AT Zero?
To find out, we will need the appropriate 'I,J,K' formula, which means we first have to tabulate some subtractions as before: 33 _ _ 37 -4 _ _ _12 _ _ 25 -29_ _ _12 _ _ 13 -42_ _ _12 _ _ 1 -43_ _ _12 _ _-11 -32
Well, actually, we could just manually continue this series, instead of figuring the 'I,J,K' formula, to find out what happens as the sequence approaches Zero from the negative side. However, when attempting to factor large numbers we will certainly prefer to use formulas and equations whenever possible, rather than grunt-work. So I'll choose the "same" triplet as before (third from the top): '-29-(13)(d)+ [(12)(d)(d-1)]/2', which after algebraic manipulation becomes '-29-(19)(d)+(6)(d^2)'. I will leave checking its ability to generate numbers in the series as an exercise for the reader.
It might be noted that the parabola associated with that series seems "larger" on the graph paper than the earlier parabola. Indeed, the first one could be smoothly nested inside this one, which is why the subtitle of this Idea mentions "Parallel Parabolas". Anyway, without showing the calculations here (for 'd=4' and 'd=5'), I'll simply say that NO, this new series does not include Zero. This means I can immediately go back and Play With Those Numerators Some More (please bear with me; I do have a reason for it!).
The next subtractions of appropriate denominators yield: 33-49=-16 -4-47=-51 -29-45=-74 -42-43=-85 -43-41=-84 -32-39=-71
And the next subtraction-tabulation yields: -16 _ _ 35 -51_ _ _12 _ _ 23 -74_ _ _12 _ _ 11 -85_ _ _12 _ _ -1 -84_ _ _12 _ _-13 -71
OK, we now have three subtraction-tabulations, and if you compare them, you will see that They Are Sequential. That means we can create a single modified generic 'I,J,K' formula that can generate ANY number in ALL those Parallel Parabolas! I will start with the first 'I,J,K' equation, '16-(15)(d)+ [(12)(d)(d-1)]/2', and modify it like this: '[16-(45)(p)]- [15-(2)(p)](d)+ [(12)(d)(d-1)]/2', where variable (p) refers to a parabolic series of numbers different from the original series, and by-default is obtained via subtraction, as was done with appropriate denominators above.
After appropriate algebraic manipulation, that new formula becomes: '[16-(45)(p)]- [21-(2)(p)](d)+ (6)(d^2)' --it should be obvious that if 'p=1', the second formula, found earlier, appears: '-29-(19)(d)+(6)(d^2)', so if 'p=2' we would get a formula for that latest tabulation above: '-74-(17)(d)+(6)(d^2)'. It happens that numbers generated by this formula, for various values of 'd', also do not include Zero....
One last manipulation of the generic formula is now in order: '(6)(d^2)- [21-(2)(p)](d)+ [16-(45)(p)]=0' --because THIS is what we want to feed into the well-known Quadratic Formula, in order to find the place where SOME parabola formula gives us the Zero we want!
Our values of 'A', 'B', and 'C', for the Quadratic Formula are: 'A=6' 'B=-[21-(2)(p)]' or [(2)(p)-21] 'C=[16-(45)(p)]' and 'd' replaces the Quadradic Formula's generic 'x', of course.
The result is: 'd= {[21-(2)(p)] +- SQR([(2)(p)-21]^2 -(4)(6)[16-(45)(p)])} / [(2)(6)]' (where "SQR" refers to a Square-Root function), and this can be algebraically manipulated/simplified to become: 'd= {[21-(2)(p)] +- SQR((4)(p^2)+(996)(p)+57)} / 12'.
WHEW! OK, just in case you got lost somewhere along the way, that last equation lets us associate variable 'p' with a series of nested parabolas. As long as 'p' is a positive number, each parabola should cross the Zero line somewhere relevant to factoring 'c=2581', and the place where it crosses is related to variable 'd' (if 'd' and 'p' were plugged into the equation that we fed into the Quadratic Formula, Zero would be produced).
It happens that because of the SQR() portion of that final equation, most values of 'p' will yield irrational results. However, this can be somewhat advantageous, because we only need to seek some value for 'p' such that the expression '(4)(p^2)+(996)(p)+57' is a perfect-square number. We can completely ignore the rest of the Quadratic Equation until after we find that square!
THAT is the essence of our search, for this Factoring Algorithm. At this writing I don't know (but somebody else might know) of a way to efficiently determine what value for 'p' can cause an expression like '(4)(p^2)+(996)(p)+57' to yield a square, when we can be quite certain in advance that at least one value for 'p' MUST yield a square. So, that's why this Factoring Algorithm is Half-Baked.
ONE way, not hugely efficient, but at least it is rather more efficient than computing square roots to find out if some number is a square, is, for the same computer program that processes sequential values for 'p' in the expression '(4)(p^2)+(996)(p)+57', to simultaneously process the series 1+8+16+24+32+..., which generates odd squares. (Note that inspection of the 'p' expression indicates that the result is always an odd number, although this might not be true for some other version of that expression, when trying to factor something other than 'c=2581'.) The results of the two sequences can be compared until a match is found.
As it happens, the value 'p=8' works, to yield the square of 91 (meaning that the 8th Parallel Parabola over from our first parabola is the one that will include an integer Zero in the sequence of modified numerators).
This lets the rest of the Quadratic Equation produce the result 'd=8'.
Now, please recall that that variable 'd' represented a "distance". Originally it was associated with the number 16 that I arbitrarily picked quite a while ago, when the first triplet of numbers was plugged into the 'I,J,K' formula. Now, however, 'd' is a distance from the equivalent location on that 8th parabola.
However, please recall that that original 16 is associated with a denominator of 45, and so also was each modified numerator in the equivalent place, on each of those 8 other Parallel Parabolas We don't actually care about the numerators, now, because they've done their job by letting us compute 'd'. After all, every sequence of numerators associatated with one of those Parallel Parabolas was ALSO associated with the same sequence of denominators --and each of those denominators was, as previously mentioned, actually a trial value for 'a', one of the defined factors of 'c'.
So, if 'd' tells us how far along a single parabola is the Zero numerator, it also tells us, by association, which denominator in the sequence should be an exact divisor of 'c'. And since the series of denominators was smoothly decrementing by 2 each time, it follows that 8 more decrements of 2 means that 45-16=29. THEREFORE 29 is one of the factors of 'c=2581'. And the other factor, of course, can be found by simple division: 2581/29=89.-- Vernon, Aug 17 2011 Factoring Algorithm Factoring_20AlgorithmAs mentioned in the main text; understanding it is very relevant to understanding this variation on the theme. [Vernon, Aug 17 2011] random, halfbakery