INTEGER NUMBER FAMILIES THE NEXT GENERATION
Part Four: Basics of Integer Factoring
Sometimes it is not what you see that is important,
It is what you do not see.
Foreword
Is there another level in the Integer Factoring Families? The answer is yes, but it is not what you might expect. Some intervals can be eliminated; however, the overhead calculations will grow proportionally. (Act surprised.) Please sit back and enjoy another journey into the realm of mathematical madness! (By the way, please excuse the pun in the title, I just could not resist.)
This article is part of the series called the Basics of Integer Factoring. If you view my About data, a list of all the other articles can be seen.
Chapter 1 — Background
The basics of Integer Factoring Families are discussed at:
A review of the material is presented here. (Quiz on Tuesday…)
The primary engine of iterative integer factoring is Fermat’s Factorization Method.
https://en.wikipedia.org/wiki/Fermat's_factorization_method
This method does not use a sieve and works off the equation: N = An² − Bn² = (An + Bn)(An − Bn), where (N) is the number under investigation. (See Appendix 1 for Mathematical Definitions) The initial value of (An) is √N rounded up. Calculating backwards: Bn = √[An² − N]; if (Bn) is not an integer, the next iteration will be required. Each iteration will be performed by incrementing (An) by one. This continues until either an integer is found or the value of (An − Bn) drops below 3, the smallest possible odd prime integer.
A typical family, where An = 25 looks like this:
An/Bn: N=Xn×Yn=An^2–Bn^2: Si+6Sn=(Sa+6Sx)(Sb+6Sy): Drop=625–N
--------------------------------------------------------------------
25/0: 625=25×25=625–0: 7+6×103=(7+6×3)(7+6×3): Drop=0
25/6: 589=19×31=625–36: 7+6×97=(7+6×2)(7+6×4): Drop=36
25/12: 481=13×37=625–144: 7+6×79=(7+6×1)(7+6×5): Drop=144
25/18: 301=7×43=625–324: 7+6×49=(7+6×0)(7+6×6): Drop=324
25/24: 49=1×49=625–576: 7+6×7=(7+6×(-1))(7+6×7): Drop=576The Drop is the difference between (N) and the Top Value of the family, which in this case is 625. The important aspect to the drop is that all factors in this family have drops that are divisible by 36, e.g. Drop at 576 mod 36 is 0. Therefore if the difference between any number and 625 is divisible by 36, that number might be in the Family=25. There are lots of exceptions though, the Drop must also follow the Drop Sequence. For Family=25, that sequence is 1×36, 4×36, 9×36, and 16×36. Since 72 is 2×36, it is excluded.
Each Family will only support one Series. The origin of the Factor Series is found in the observation that except for the prime numbers 2 and 3, all other prime numbers will be found adjacent to a number that is divisible by 6, e.g. prime numbers 5 and 7 are next to the number 6. There are two series that (N) can belong to. In Series = 5, Si = 5, N = 5+6×Sn and Sn = {0, 1, 2, 3, …} Examples of Series = 5 are N = 5, 11, and 17. In Series = 7, Si = 7, N = 7+6×Sn and Sn = {-1, 0, 1, 2, 3, …} Examples of Series = 7 are N = 1, 7, 13, and 19. (Series = 2 and Series = 3 exist, but will be excluded from this essay because they have their own genealogies.)
There are three possible products that can result from these two series.
(1) First, a Series = 5 times a Series = 7 yields a Series = 5.
There are two subsets:
(a) Series = 5 times a Series = 7 yields Series = 5A,
Example: 35 = 5×7 or
(b) Series = 7 times a Series = 5 yields Series = 5B,
Example: 77 = 7×11.
(2) Second, a Series = 7 times a Series = 7 yields a Series = 7,
Example: 49 = 7×7.
(3) And finally a Series = 5 times a Series = 5 yields a Series = 7,
Example: 25 = 5×5.There are three groups of families depending on the value of (An) where Group = An mod 3. They are Groups = 0, 1, and 2.
(1) If Group = 0 (An mod 3 = 0), then the entire family is
Series = 5 from the product of Series = 5 times Series = 7 or
Series = 7 times Series = 5.
(2) If Group = 1 (An mod 3 = 1), then the entire family is
Series = 7 from the product of Series = 7 times Series = 7.
(3) If Group = 2 (An mod 3 = 2), then the entire family is
Series = 7 from the product of Series = 5 times Series = 5.Returning to Family=25, we find that 25 mod 3 = 1, so it is Group=1 and will only support Series = 7, e.g. 7+6×103=(7+6×3)(7+6×3). The next family that supports Series = 7 is the Group=2 at An=An + 1 = 25 + 1; Family=26.
An/Bn: N=Xn×Yn=An^2–Bn^2: Si+6Sn=(Sa+6Sx)(Sb+6Sy): Drop=625–N
--------------------------------------------------------------------26/3: 667=23×29=676–9: 7+6×110=(5+6×3)(5+6×4): Drop=0
26/9: 595=17×35=676–81: 7+6×98=(5+6×2)(5+6×5): Drop=72
26/15: 451=11×41=676–225: 7+6×74=(5+6×1)(5+6×6): Drop=216
26/21: 235=5×47=676–441: 7+6×38=(5+6×0)(5+6×7): Drop=432The Series=7 remains the same, but the Common Factor has changed to 72. Admission to the new family is now determined by N mod 72 = 0. The lesson here is that if you are evaluating a Series=7 number, you must examine each family in Group=1 and each family in Group=2. We can skip An=An + 1 = 26 + 1; Family=27, because it is Group = 0 (An mod 3 = 0). The next family that supports Series = 7 is the Group=1 at An=An + 1 = 27 + 1; Family=28.
An/Bn: N=Xn×Yn=An^2–Bn^2: Si+6Sn=(Sa+6Sx)(Sb+6Sy): Drop=625–N
--------------------------------------------------------------------
28/3: 775=25×31=784–9: 7+6×128=(7+6×3)(7+6×4): Drop=0
28/9: 703=19×37=784–81: 7+6×116=(7+6×2)(7+6×5): Drop=72
28/15: 559=13×43=784–225: 7+6×92=(7+6×1)(7+6×6): Drop=216
28/21: 343=7×49=784–441: 7+6×56=(7+6×0)(7+6×7): Drop=432
28/27: 55=1×55=784–729: 7+6×8=(7+6×(-1))(7+6×8): Drop=720Now we have a Group=1 with a Common Factor of 72. It appears that there is an inversion between (An) is Odd and (An) is Even. This requires us to now have two flavors of each group based on whether the value of (An) is odd or even. The lesson here is that you must examine each Group=1 (Even), each Group=1 (Odd), each Group=2 (Even), and each Group=2 (Odd). If the benefits of this procedure are not very oblivious at this point, take a breath, you can not eat the cake when you are staring at the recipe. The best solution is to take separate paths and progress through all the Even and all the Odd groups separately. Statistically, you will find the solution 50% of the time without chasing the second group.
Chapter 2 — Basic Factoring Iteration
It is time to actually evaluate a number: N = 37×967 = 35779 where 35779 mod 6 = 1, so Series=7. The initial value of An = √[N] = √[35779] = 189.153 (Round Up) = 190. Since 190 mod 3 = 1 it supports Series=7 and needs no adjustment.
We have a choice between Group = 1 and Group = 2. When we synchronize the value of (An) for Group = 1, we will find that An = 214 is the best fit. In the process, we eliminate the path where An = Odd. (Since I have worked the problem out already, I know that we will find a solution in Group = 1, so we can ignore the Group = 2 solution this time.)
We now run increments of (An) with the increment equal to Common Factor divided by 2. In this case that is 72/2=36. Performing the iterations, we will not find the solution until our 9th try, where the result is An = 502.
Wouldn’t it be nice to skip some of these iterations? Well, actually, I just did. You just can not see the whole spread sheet from your angle, but I will attempt to explain. See the “+” signs in Column[U]? They are telling us we can skip these values of (An) entirely.
Perhaps you have noticed that this Fermat Iteration Block is different from previous renditions. This version is based on the Full Fermat Matrix. In this version the matrix backbone is Column[X] which contains the values of (Bn). In fact in long form Column[X] contains every value of (Bn) that we would find in the last family that contains (N). The last family has Xn=1 and Yn=N, so An=(Yn+Xn)/2 and Bn=(Yn-Xn)/2. In our example N=35779, so Xn=1; Yn=35779; An=17890; and Bn=17889. The Full Fermat Matrix starts with An=214 and has 17889 lines, one for each value of (Bn), and continues until the value An=17890 is reached. The values of (An) are incremented when Xn×Yn<=N; however, the values of (Bn) continue uninterrupted to the end. (I know… it would make a essay all in itself, but I just do not have the time.)
The Next column shows the adjustment for (Bn) if we choose to not display every single line. The equation is: Z= (X n-Y n)/12 ± √[(Y n-X n)²/4 + X nY n− N]/6. The subsequent Bn=Bn + 6×Z. If you prefer to see all of nearly 18K lines this can be omitted and Bn=Bn + 6.
Chapter 3 — Basic Factoring Alignment
It turns out that there is an alignment segment that will show which values of (An) can be skipped.
The interpretation is easy. If the line in the alignment block has an “X” in it, then the value of (An) associated with it can be skipped and there is no need to perform the validation of the square root. If no “X” is found, then the validation must be performed. As you can see, a fairly good number of lines can be skipped.
“What are the math demons up to?” you may ask. That will take a little more explanation.
Chapter 4 — Drop Alignment
Remember those drops in the Family Diagrams above. The drops can be readily calculated from the values of (Bn). The appropriate Drop = Bn² − Top Bn² where the value of (Bn) depends on whether (An) is odd or even.
Take those drops and normalize them by dividing by the Common Factor which is 72 for this example. The normalized sequence will be {0, 1, 3, 6, 10, …} Then perform various divisions on these, e.g. Cell[BA6]=10, so Cell[BH6]=Cell[BA6] mod Cell[BH1] = 10 mod 7=3. The whole thing looks something like this:
The most interesting aspect of this is the fact that the all the sequences repeat and the repeating block is the same depth as the divisor. Note that these divisors are just a few I put together for test purposes, there is no upper limit other than what you spreadsheet can deal with. The second most interesting aspect of this is that there are missing numbers in the sequences, e.g. under the divisor “3” we have the sequence “0:1:0.” There is no number “2.” “5” is missing “2” and “4.”
How do we identity the missing numbers?
This illustration is a little confusing. In order to find a missing number, the spreadsheet looks at the expected value in column “F” and searches for it in the Drop Normalization Block. If the number is found it shows up as a pointer, e.g. “0” is at “1” and “1” is at “2.” If the number is not located then an “X” is entered in the column, e.g. Cell[BV4] = IF($F4<BV$1), IFNA(MATCH($F4,BI$2:BI$33,0), “X”), “.”) = 5.
Now we do this all over using the actual drops that result from using (An) and (N).
This block resembles the Page Sheet Drop Normalization Block from above. Again, all the sequences repeat and the repeating block is the same depth as the divisor and we use the divisors from above. There are missing numbers in the sequences, but we are not interested in them this time. What we want to know is whether any of the numbers present are missing from the Page Sheet Missing Values Block. If they are then we can not align the data in the blocks. We can skip these values of (An).
Finally, the last data block. We swap out the values that have no match and replace them with “X”.
Look familiar? It is the original Alignment Block sans the red highlights. To be factually correct, what we were looking at originally is merely a looped table lookup of this block, e.g. Cell[AP11] =INDEX(CU$2:CU$6, IF(MOD($AE11, AP$1)=0, AP$1, MOD($AE11, AP$1))) = 3. By the way, Cell[AE11]=9. Column[AE] (not shown) is a modified counter that allows shifting, but that’s for another day.
For those of you that are actually understanding all this, you may be thinking, “Wouldn’t it be easier to just find the drop at each (An) and verify against the drop value at (Bn)?” That would be a valid procedure except as my chess puzzle website is constantly reminding me, “There is a better move.”
Chapter 5 — Prime Number Blackout
Oops, I almost forgot to include a snippet on prime numbers. Let’s stick a known prime number, 1013, into the spreadsheet.
Although the output is truncated for display purposes, the spreadsheet does indeed mark every value of (An) as “+” to indicate they can all be skipped. The highlighted value indicates that one factor was found, i.e. 1013 = 1×1013, exactly what we would expect.
To be honest, not all prime numbers will be so clean. Most will have a hiccup or two. This is because the initialization of the Alignment Blocks only runs out to “19.” My supposition at this time is that if we were to increase the range by a few more, that virtually all (small) prime numbers would be “blacked out.”
Chapter 6— To Be Continued …
Lest we get into a Fermat’s Disciple’s Last Theorem, let me clarify my thinking. With the Factoring Alignment Block we have repeating strings of numbers in a great loop. When they align correctly, you have a good chance of finding a factor. This is sort of like a slot machine, but with one big difference. We know the tumbler sequences! Now, my experience says, “Even though this looks easy, be ready for a magnificent struggle.” I already see a lot of divergence as there are many ways that the sequences can connect together. It may well wind up being a bathtub with far too many holes in it to hold water.
With a little luck, I will return with something really nice.
Update:
A discussion of Fast Fermat Integer Family Factoring can be found at:
A JavaScript Program that demonstrates how Fast Fermat Integer Family Factoring works is now available.
Appendix 1 — Standard Definitions and Equations
…^… — Raise to the Power of
√[…] — Square Root Function
An — Factor of Base Root Value: An = (Yn + Xn)/2
where An ≥ √[N]
Bn — Factor of Small Root Value: Bn = (Yn — Xn)/2
Ia — Unity Factor for Na: Ia = ± 1
Ib — Unity Factor for Nb: Ib = ± 1
N’ — Integer Prime Number: N’ = N’×1 ≠ N
N — Composite Integer Factorization: N = Xn×Yn ≠ N’
N — Fermat’s Factorization: N = An² — Bn²
= (An — Bn)(An + Bn)
N — Series Factorization: N = Si+6Sn
= (Sa + 6Sx)(Sb + 6Sy)
Ri — Fermat Remainder: Ri = An² — N
(Iterate until Ri=Bn²)
Si — Series Identifier for Composite N: Si = 5 or 7 = 6 + In
Sa — Series Identifier for Xn: Sa = 5 or 7 = 6 + Ia
Sb — Series Identifier for Yn: Sb = 5 or 7 = 6 + Ib
Sn — Series Expansion for Composite N: Sn = (N — Si)/6
Sx — Series Expansion for Xn: Sx = (Xn — Sa)/6
Sy — Series Expansion for Yn: Sy = (Yn — Sb)/6
Xn — Smaller Integer Factor of N: Xn = An — Bn
where 1 < Xn ≤ Yn
Xn — Smaller Integer Factor of N: Xn = Sa+ 6Sx
where 1<Xn≤Yn; Sa = 5 or 7
Yn — Larger Integer Factor of N: Yn = An + Bn
where Yn ≥ Xn > 1
Yn — Larger Integer Factor of N: Yn = Sb + 6Sy
where Yn≥Xn>1; Sb = 5 or 7
