INTRODUCTION TO INTEGER FACTORING FAMILIES
Part Two: Basics of Integer Factoring
A person with everything can find none of it, and
A person with nothing can find all of it.Foreword
When studying integer factoring, I always thought that prime numbers were orphans. As it turns out, they each have a family tree. Sadly, the demons of mathematics ensured that every odd number also has a family tree, so there is no new insight into prime number differentiation. The families none-the-less are still fascinating in their own right and I will attempt to provide an introduction in this essay.
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 primary engine of iterative integer factoring is 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. The initial value of (An) is √N rounded up. Thus for N = 6649; An = 81.5414; round up to 82. Calculating backwards: Bn = √[An² − N] = 8.66; since (Bn) is not an integer, the next iteration will be required. Each iteration will be performed by incrementing (An) by one: An + 1= 83. This continues until either an integer is found or the value of (An − Bn) drops below 3, the smallest possible odd prime integer. (We will pretend negative prime numbers do not exist.) This will require 4 total iterations as seen in Table 1.
This spread sheet is fairly self explanatory. The [SQRT] column in the square root of the [An² - N] column. The [Bn] column only has values when the SQRT is an integer, i.e. [IF(SQRT = ROUND(SQRT), SQRT, “.”)]. The [Xn] and [Yn] columns use the formulas Xn = An - Bn; Yn = An + Bn, i.e. [IF(Bn = SQRT, An - Bn, “.”)] and [IF(Bn = SQRT, An+Bn, “.”)]. The [Verify] column allows the user to validate that [Xn] and [Yn] multiplied together do equal the initial target [N], i.e. [IF(Bn = SQRT, IF(Xn*Yn = N, Xn*Yn, “Error”), “.”)]
The biggest problem that this method has, is that it works from the smallest possible difference in the factors down to the largest difference in factors. What that means is if the factors are like 85×83 you will get an almost instant hit, whereas 85×5 may take significantly longer and require many more iterations. Any modification to the basic method that reduces the computation time and the iterations is considered beneficial. It must be noted that simply reducing iterations may inadvertently increase computation time. This is the typical problem with methods that use sieves. Consequently, there is a balance that must be maintained.
Chapter 2 — The Families
The concept of Integer Factoring Families, revolves around the creation of a table of all values of (An) and (Bn) for a limited range of numbers. There being no need to stretch the presentation past my bedtime, I present to you the family trees of the integer families between 0 and 26.
Families of FactorsAn/Bn: N=Xn×Yn=An^2–Bn^2: Factor Series: Drop from top
------------------------------------------------------------
0/0: 0=0×0=0-0: Factor by 3: Factor by 21/0: 1=1×1=1-0: 7+6×(-1)=(7+6×(-1))(7+6×(-1)): Drop=0
1/1: 0=0×2=1-1: Factor by 3: Factor by 22/0: 4=2×2=4-0: Factor by 2
2/1: 3=1×3=4-1: Factor by 3
2/2: 0=0×4=4-4: Factor by 3: Factor by 23/0: 9=3×3=9-0: Factor by 3
3/1: 8=2×4=9-1: Factor by 2
3/2: 5=1×5=9-4: 5+6×0=(7+6×(-1))(5+6×0): Drop=0
3/3: 0=0×6=9-9: Factor by 3: Factor by 24/0: 16=4×4=16-0: Factor by 2
4/1: 15=3×5=16-1: Factor by 3
4/2: 12=2×6=16-4: Factor by 3: Factor by 2
4/3: 7=1×7=16-9: 7+6×0=(7+6×(-1))(7+6×0): Drop=0
4/4: 0=0×8=16-16: Factor by 3: Factor by 25/0: 25=5×5=25-0: 7+6×3=(5+6×0)(5+6×0): Drop=0
5/1: 24=4×6=25-1: Factor by 3: Factor by 2
5/2: 21=3×7=25-4: Factor by 3
5/3: 16=2×8=25-9: Factor by 2
5/4: 9=1×9=25-16: Factor by 3
5/5: 0=0×10=25-25: Factor by 3: Factor by 26/0: 36=6×6=36-0: Factor by 3: Factor by 2
6/1: 35=5×7=36-1: 5+6×5=(5+6×0)(7+6×0): Drop=0
6/2: 32=4×8=36-4: Factor by 2
6/3: 27=3×9=36-9: Factor by 3
6/4: 20=2×10=36-16: Factor by 2
6/5: 11=1×11=36-25: 5+6×1=(7+6×(-1))(5+6×1): Drop=24
6/6: 0=0×12=36-36: Factor by 3: Factor by 27/0: 49=7×7=49-0: 7+6×7=(7+6×0)(7+6×0): Drop=0
7/1: 48=6×8=49-1: Factor by 3: Factor by 2
7/2: 45=5×9=49-4: Factor by 3
7/3: 40=4×10=49-9: Factor by 2
7/4: 33=3×11=49-16: Factor by 3
7/5: 24=2×12=49-25: Factor by 3: Factor by 2
7/6: 13=1×13=49-36: 7+6×1=(7+6×(-1))(7+6×1): Drop=36
7/7: 0=0×14=49-49: Factor by 3: Factor by 28/0: 64=8×8=64-0: Factor by 2
8/1: 63=7×9=64-1: Factor by 3
8/2: 60=6×10=64-4: Factor by 3: Factor by 2
8/3: 55=5×11=64-9: 7+6×8=(5+6×0)(5+6×1): Drop=0
8/4: 48=4×12=64-16: Factor by 3: Factor by 2
8/5: 39=3×13=64-25: Factor by 3
8/6: 28=2×14=64-36: Factor by 2
8/7: 15=1×15=64-49: Factor by 3
8/8: 0=0×16=64-64: Factor by 3: Factor by 2{From this point the division by 2 and 3 has been turned off.}9/2: 77=7×11=81-4: 5+6×12=(7+6×0)(5+6×1): Drop=0
9/4: 65=5×13=81-16: 5+6×10=(5+6×0)(7+6×1): Drop=0
9/8: 17=1×17=81-64: 5+6×2=(7+6×(-1))(5+6×2): Drop=6010/3: 91=7×13=100-9: 7+6×14=(7+6×0)(7+6×1): Drop=0
10/9: 19=1×19=100-81: 7+6×2=(7+6×(-1))(7+6×2): Drop=7211/0: 121=11×11=121-0: 7+6×19=(5+6×1)(5+6×1): Drop=0
11/6: 85=5×17=121-36: 7+6×13=(5+6×0)(5+6×2): Drop=3612/1: 143=11×13=144-1: 5+6×23=(5+6×1)(7+6×1): Drop=0
12/5: 119=7×17=144-25: 5+6×19=(7+6×0)(5+6×2): Drop=0
12/7: 95=5×19=144-49: 5+6×15=(5+6×0)(7+6×2): Drop=48
12/11: 23=1×23=144-121: 5+6×3=(7+6×(-1))(5+6×3): Drop=9613/0: 169=13×13=169-0: 7+6×27=(7+6×1)(7+6×1): Drop=0
13/6: 133=7×19=169-36: 7+6×21=(7+6×0)(7+6×2): Drop=36
13/12: 25=1×25=169-144: 7+6×3=(7+6×(-1))(7+6×3): Drop=14414/3: 187=11×17=196-9: 7+6×30=(5+6×1)(5+6×2): Drop=0
14/9: 115=5×23=196-81: 7+6×18=(5+6×0)(5+6×3): Drop=7215/2: 221=13×17=225-4: 5+6×36=(7+6×1)(5+6×2): Drop=0
15/4: 209=11×19=225-16: 5+6×34=(5+6×1)(7+6×2): Drop=0
15/8: 161=7×23=225-64: 5+6×26=(7+6×0)(5+6×3): Drop=60
15/10: 125=5×25=225-100: 5+6×20=(5+6×0)(7+6×3): Drop=84
15/14: 29=1×29=225-196: 5+6×4=(7+6×(-1))(5+6×4): Drop=19216/3: 247=13×19=256-9: 7+6×40=(7+6×1)(7+6×2): Drop=0
16/9: 175=7×25=256-81: 7+6×28=(7+6×0)(7+6×3): Drop=72
16/15: 31=1×31=256-225: 7+6×4=(7+6×(-1))(7+6×4): Drop=21617/0: 289=17×17=289-0: 7+6×47=(5+6×2)(5+6×2): Drop=0
17/6: 253=11×23=289-36: 7+6×41=(5+6×1)(5+6×3): Drop=36
17/12: 145=5×29=289-144: 7+6×23=(5+6×0)(5+6×4): Drop=14418/1: 323=17×19=324-1: 5+6×53=(5+6×2)(7+6×2): Drop=0
18/5: 299=13×23=324-25: 5+6×49=(7+6×1)(5+6×3): Drop=0
18/7: 275=11×25=324-49: 5+6×45=(5+6×1)(7+6×3): Drop=48
18/11: 203=7×29=324-121: 5+6×33=(7+6×0)(5+6×4): Drop=96
18/13: 155=5×31=324-169: 5+6×25=(5+6×0)(7+6×4): Drop=168
18/17: 35=1×35=324-289: 5+6×5=(7+6×(-1))(5+6×5): Drop=26419/0: 361=19×19=361-0: 7+6×59=(7+6×2)(7+6×2): Drop=0
19/6: 325=13×25=361-36: 7+6×53=(7+6×1)(7+6×3): Drop=36
19/12: 217=7×31=361-144: 7+6×35=(7+6×0)(7+6×4): Drop=144
19/18: 37=1×37=361-324: 7+6×5=(7+6×(-1))(7+6×5): Drop=32420/3: 391=17×23=400-9: 7+6×64=(5+6×2)(5+6×3): Drop=0
20/9: 319=11×29=400-81: 7+6×52=(5+6×1)(5+6×4): Drop=72
20/15: 175=5×35=400-225: 7+6×28=(5+6×0)(5+6×5): Drop=21621/2: 437=19×23=441-4: 5+6×72=(7+6×2)(5+6×3): Drop=0
21/4: 425=17×25=441-16: 5+6×70=(5+6×2)(7+6×3): Drop=0
21/8: 377=13×29=441-64: 5+6×62=(7+6×1)(5+6×4): Drop=60
21/10: 341=11×31=441-100: 5+6×56=(5+6×1)(7+6×4): Drop=84
21/14: 245=7×35=441-196: 5+6×40=(7+6×0)(5+6×5): Drop=192
21/16: 185=5×37=441-256: 5+6×30=(5+6×0)(7+6×5): Drop=240
21/20: 41=1×41=441-400: 5+6×6=(7+6×(-1))(5+6×6): Drop=39622/3: 475=19×25=484-9: 7+6×78=(7+6×2)(7+6×3): Drop=0
22/9: 403=13×31=484-81: 7+6×66=(7+6×1)(7+6×4): Drop=72
22/15: 259=7×37=484-225: 7+6×42=(7+6×0)(7+6×5): Drop=216
22/21: 43=1×43=484-441: 7+6×6=(7+6×(-1))(7+6×6): Drop=43223/0: 529=23×23=529-0: 7+6×87=(5+6×3)(5+6×3): Drop=0
23/6: 493=17×29=529-36: 7+6×81=(5+6×2)(5+6×4): Drop=36
23/12: 385=11×35=529-144: 7+6×63=(5+6×1)(5+6×5): Drop=144
23/18: 205=5×41=529-324: 7+6×33=(5+6×0)(5+6×6): Drop=32424/1: 575=23×25=576-1: 5+6×95=(5+6×3)(7+6×3): Drop=0
24/5: 551=19×29=576-25: 5+6×91=(7+6×2)(5+6×4): Drop=24
24/7: 527=17×31=576-49: 5+6×87=(5+6×2)(7+6×4): Drop=48
24/11: 455=13×35=576-121: 5+6×75=(7+6×1)(5+6×5): Drop=120
24/13: 407=11×37=576-169: 5+6×67=(5+6×1)(7+6×5): Drop=168
24/17: 287=7×41=576-289: 5+6×47=(7+6×0)(5+6×6): Drop=288
24/19: 215=5×43=576-361: 5+6×35=(5+6×0)(7+6×6): Drop=360
24/23: 47=1×47=576-529: 5+6×7=(7+6×(-1))(5+6×7): Drop=52825/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=57626/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=432
Chapter 3 — Explanation of Table
The table layout is a line by line reverse analysis of all values across a given range that might be used to calculate Fermat Factors. The first column is [An/Bn:] and contains the base value used to calculate the major square An² and the incremental value used to calculate the minor square Bn². The initial value of (An) is picked as required to analyze a given range. The initial value of (Bn) is set to 0 and is incremented until it reaches the value of (An.) At that time (An) is incremented and (Bn) is reset to 0 to explore a new family.
The next column [N=Xn × Yn = An² - Bn²:] performs the calculations to show what values would be associated with this factorization. The value (N) is the value that would normally be the target of the factorization. This value is derived from the equation N= An² - Bn² using the values in the first column. The value of Xn = An - Bn; Yn = An + Bn; An²; and Bn² are likewise from the first column. The formal equations can be summarized as N = Xn × Yn = (An - Bn)(An + Bn) = An² - Bn².
The third column [Factor Series:] provides enhanced information which will be discussed in the observations section. The Factor Series Transform Formulas are N = Sa + 6 × Sb where Sa is usually 5 or 7 and Sb = (N - Sa)/6. Note that Sb must be an integer value. Generally when N is divisible by 2 or 3 there will be no valid Sb.
The final column [Drop from top] is also enhanced information to be discussed later. The first Factor Series value in each family is assigned the baseline (N) and has a drop value of 0. Each Factor Series thereafter will show the drop value as the separation of the current (N) from the baseline (N).
Chapter 4 — Observations
The first thing that catches the eye is the even numbers in the table. Although Fermat’s factoring method can support even numbers, this only occurs when N mod 4 = 0. If there is no control of the input selection, then it is suggested that (N) be prescreened to insure N mod 2 = 1. (Or multiply the input by two and divide one of the results by two.) This results in the number set: {2, 6, 10, 14, 18, …} not being represented. These are the true orphans.
Probably the most interesting aspect of this essay is the jigsaw puzzle way that the composite integers are found in nature. It has always been a frustration for folks (or with me anyway) working with integer factors that there was no way to interpolate results because there was no linear structure. If this essay does any good, it does show graphically exactly how this nonlinear phenomena works.
Prime numbers are identified when a value can only be represented by one times a given value, e.g. 23=1×23, and this instance is the only time the value has appeared in the table. Note that composite numbers will appear in this format as well, but they will also appear higher up in the table, e.g. 11/10: 21=1×21=121–100 is also found higher up at 5/2: 21=3×7=25–4. To my knowledge, prime numbers are never duplicated and composite numbers are always duplicated at least once. The numbers in a family will typically intermix with numbers in other families and occasionally are duplicated if they have more than two factors. For example 23/12: 385=11×35=529–144 and 31/24: 385=7×55=961–576 and 41/36: 385=5×77=1681–1296. The prime numbers live at the bottom of the families, being the smallest numbers in the family. That is also where every odd number lives eventually. The bottom family number is always N = An×2–1. Once a number reaches the bottom of a family, it will never show up in the table again.
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, Sa = 5, N = 5+6×Sb and Sb = {0, 1, 2, 3, …} Examples of Series = 5 are N = 5, 11, and 17. In Series = 7, Sa = 7, N = 7+6×Sb and Sb = {-1, 0, 1, 2, 3, …} Examples of Series = 7 are N = 1, 7, 13, and 19.
There are three possible products that can result from these two series.
- First, a Series = 5 times a Series = 7 yields a Series = 5. There are two subsets:
- Series = 5 times a Series = 7 yields Series = 5A, Example: 35 = 5×7 or Series = 7 times a Series = 5 yields Series = 5B, Example: 77 = 7×11.
- Second, a Series = 7 times a Series = 7 yields a Series = 7, Example: 49 = 7×7.
- And finally a Series = 5 times a Series = 5 yields a Series = 7, Example: 25 = 5×5.
If you noticed 25 is classified as a Series = 7 and think it should be a Series = 5, here is what is happening: 25 = 7 + 6×3. (I don’t make the rules. Talk to the demons.) Seriously, 20 is not evenly divisible by 6, so it can not create the necessary factor for 25 = 5+6×Sb. I guess I should have mentioned, that if N mod 6 = 5 then (N) is Series = 5 and if N mod 6 = 1 then (N) is Series = 7. So, 25 mod 6 = 1 and must therefore be Series = 7.
The reason we have Series = 5A and Series = 5B is because there are two separate lineages embedded in the tables that govern Series = 5. Series = 5A follows the lineage where the top value is (5+6×Sx) × (7+6×Sy) and Series = 5B follows the lineage where the top value is (7+6×Sx) × (5+6×Sy).
12/1: 143=11×13=144-1: 5+6×23=(5+6×1)(7+6×1): Drop=0 – A Series
12/5: 119=7×17=144-25: 5+6×19=(7+6×0)(5+6×2): Drop=24 – B Series
12/7: 95=5×19=144-49: 5+6×15=(5+6×0)(7+6×2): Drop=48 – A Series
12/11: 23=1×23=144-121: 5+6×3=(7+6×(-1))(5+6×3): Drop=120 – B Series15/2: 221=13×17=225-4: 5+6×36=(7+6×1)(5+6×2): Drop=0 – B Series
15/4: 209=11×19=225-16: 5+6×34=(5+6×1)(7+6×2): Drop= 0 – A Series
15/8: 161=7×23=225-64: 5+6×26=(7+6×0)(5+6×3): Drop=60 – B Series
15/10: 125=5×25=225-100: 5+6×20=(5+6×0)(7+6×3): Drop=84 – A Series
15/14: 29=1×29=225-196: 5+6×4=(7+6×(-1))(5+6×4): Drop=192 – B Series
If N mod 6 = 3, then the number is divisible by 3 and there is no need to proceed further. This essay will concentrate on factoring candidates that are odd integers and are greater than 3. Even numbers are always divisible by 2 and are easy to screen. There are two methods to screen for 3. First you can check to verify that N mod 3 = 0. Or second, add the digits in the number and divide by 3. If the result is an integer then the number is divisible by 3, i.e. 123 digitally summed = 1+2+3 = 6 and 6/3 = 2. (It works for the number 9 as well, but that discussion is unnecessary at this time. Not convinced? Try 63 → (6+3) mod 9 = 0 or try 2763 → (2+7+6+3) mod 9 = 0. Ok then, you doubters, look this up.)
One would think that composite numbers with multiple factors might produce ambiguous results. The number 2275 is Series = 7 because 2275 mod 6 = 1 and because (2275–7)/6 = 378 which is an integer, but it is also easily seen as divisible by 5. It, however, is not Series = 5 because (2275–5)/6 = 378.333… which is not an integer. It actually does follow the rules with factors 35×65 and 5×455 as Series = 5 factors yielding Series =7 products and 25×91; 13×175; 7×325; and 1×2275 as Series = 7 factors yielding Series = 7 products. Yes, the number one is technically a Series = 7 where 1 mod 6 = 1, which is why prime numbers are pretty much indistinguishable from non-prime numbers.
The Factor Series Transform Formulas also provide information embedded in the (Sb) element, i.e. the transform 25 = 7 + 6×3 has Sb = 3. The sum of the (Sb) elements of the (Xn) and (Yn) terms is the same for all family members. It is essentially family DNA.
25/0: 625=25×25=625-0: 7+6×103=(7+6×3)(7+6×3): Sum Sb=3+3=6
25/6: 589=19×31=625-36: 7+6×97=(7+6×2)(7+6×4): Sum Sb=2+4= 6
25/12: 481=13×37=625-144: 7+6×79=(7+6×1)(7+6×5): Sum Sb=1+5=6
25/18: 301=7×43=625-324: 7+6×49=(7+6×0)(7+6×6): Sum Sb =0+6=6
25/24: 49=1×49=625-576: 7+6×7=(7+6×(-1))(7+6×7): Sum Sb =-1+7=6The top of a given family starts with the largest values on (N) and works down to smaller values at the bottom.
- The top number for even values of (An) is N = An² − 9 for Series = 7 and N = An² − 1 for Series = 5A and N = An² − 25 for Series = 5B.
- The top number for odd values of (An) is N = An² for Series = 7 and N = An² − 16 for Series = 5A and N = An² − 4 for Series = 5B.
- The bottom family number is always N = An×2–1.
Ignore cases where N = An² − 1 is the result of values divisible by 3. Example: 4/1: 15=3×5=16–1. These are Series = 3 and unsuitable for this discussion.
If you are running an iteration process to find a Fermat Factor, then you will note that you no longer need to increment through every value. Some values of (An) can be skipped! There are three groups of families depending on the value of (An) where Group = An mod 3. They are (act surprised) Groups = 0, 1, and 2.
- 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.
- If Group = 1 (An mod 3 = 1), then the entire family is Series = 7 from the product of Series = 7 times Series = 7.
- If Group = 2 (An mod 3 = 2), then the entire family is Series = 7 from the product of Series = 5 times Series = 5.
The first estimate of (An) may not be the correct Group. In our example above on Trial 1, N = 6649 and An = 82. So, 6649 mod 6 = 1 thus Series = 7 and 82 mod 3 = 1 thus Group = 1, so this is a match and everything is alright. Had it not been correct, then (An) would have needed to be incremented until it supported Series = 7. In addition, the Group and Series that (N) starts in must be the same Series and support Group that (N) ends in. Remember, both Group = 1 and 2 support Series = 7, but Group = 0 only supports Series = 5. In the example again on Trial 2, 83 mod 3 = 2, so it is usable for a Series = 7, but on Trial 3, 84 mod 3 = 0, so it should be skipped. Finally on Trial 4, 85 mod 3 = 1 works and yields the final answer.
The Drop is how far down the number (N) is from the top. The Drop is always divisible by 12, but can under certain circumstances be more. If we find the top value we can check the Drop. Testing from the example again, An = 82, so the top for (An = even) and Series = 7 is at An² − 9 = 6715 and (6715–6649) mod 12 = 6, thus (An) can not be 82. At An = 83, the top is at An² = 6889 and (6889–6649) mod 12 = 0, thus (An) at 83 is fine. At An = 85, the top is at An² = 7225 and (7225–6649) mod 12 = 0, thus (An) at 85 is fine. In effect, we could have skipped both trials at 82 and 84.
Some of you are probably ahead of me at this point. Is there a Drop Signature? Yes, there is! If the absolute drop has a certain value, then the value of (An) will be a family member and the amount of the drop can be decoded to reveal the value of (Bn). For example: 10/3: 91=7×13=100–9: 7+6×14=(7+6×0)(7+6×1): Drop=0; is the top number for Family = 10. The first drop is measured at: 10/9: 19=1×19=100–81: 7+6×2=(7+6×(-1))(7+6×2): Drop=72. This first drop will be the same for all (An is even/ Group = 1/Series = 7) values and will always result in Bn = 9.
16/3: 247=13×19=256-9: 7+6×40=(7+6×1)(7+6×2): Drop=0
16/9: 175=7×25=256-81: 7+6×28=(7+6×0)(7+6×3): Drop=7222/3: 475=19×25=484-9: 7+6×78=(7+6×2)(7+6×3): Drop=0
22/9: 403=13×31=484-81: 7+6×66=(7+6×1)(7+6×4): Drop=72
22/15: 259=7×37=484-225: 7+6×42=(7+6×0)(7+6×5): Drop=21628/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
And of course the second Drop will be 216 with Bn = 15 and the third Drop will be 432 with Bn = 21. The formula for the progression is New Drop = Previous Drop + (Sequence Number × 72), i.e. 0+(1×72) = 72; 72+(2×72) = 216; and 216+(3×72) = 432. The (Bn) progression is much easier: New Bn = Bn+6.
Sadly each new (An) will require a different progression depending on whether it is odd or even; what the group is; and which series is being evaluated. That means there are 8 progressions needed to make a complete categorization of the Drop Signatures. Wait you say, there are only 6? Not true. Examine 12/5: 119=7×17=144–25: 5+6×19=(7+6×0)(5+6×2): Drop=24 and 12/7: 95=5×19=144–49: 5+6×15=(5+6×0)(7+6×2): Drop=48. There is a subtle difference in the separation of the Xn and Yn Factor Series. Remember, the first factor is always the smaller factor. If you look at 5×7 the separation of Xn and Yn is 2. If you look at 7×11 the separation of Xn and Yn is 4. This makes a difference for some reason. (Talk to the demons…) Actually, we catch a break, both Series = 7 have the same profiles, so there are only 6 progressions after all. To differentiate, we now have Series = 5A (5×7) and Series = 5B (7×11).
- If Group = 1 or 2 (An mod 3 = 1 or 2) and (An = even), then Drop Progression = {72, 216, 432, 720, 1080, … } = 72 × {1, 3, 6, 10, 15, … } where the New Drop = Previous Drop + (New Sequence Number × 72), e.g. the Drop 4 = 432 + 4 × 72 = 720.
- If Group = 1 or 2 (An mod 3 = 1 or 2) and (An = odd,) then Drop Progression = {36, 144, 324, 576, 900, 1296,… } = 36 × {1, 4, 9, 16, 25, … } where the New Drop = 36 × Sequence Number², e.g. the Drop 4 = 4² × 36 = 576.
- If Group = 0 (An mod 3 = 0) and (An = even) and Series = 5A, then Drop Progression = {48, 168, 360, 624, 960, … } = 24 × {2, 5, 8, 11, 14, … } where the New Drop = Previous Drop + (3 × Sequence Number − 1) × 24, e.g. the Drop 4 = 360 + (3 × 4 −1) × 24 = 624.
- If Group = 0 (An mod 3 = 0) and (An = odd) and Series = 5A, then Drop Progression = {84, 240, 468, 768, 1140, … } = 12 × {7, 20, 39, 64, 95, … } where the New Drop = Previous Drop + (6 × Sequence Number + 1) × 12, e.g. the Drop 4 = 468 + (6 × 4 + 1) × 12 = 768.
- If Group = 0 (An mod 3 = 0) and (An = even) and Series = 5B, then Drop Progression = {96, 264, 504, 816, 1200, … } = 24 × {4, 7, 10, 13, 16, … } where the New Drop = Previous Drop + (3 × Sequence Number + 1) × 24, e.g. the Drop 4 = 504 + (3 × 4 + 1) × 24 = 816.
- If Group = 0 (An mod 3 = 0) and (An = odd) and Series = 5B, then Drop Progression = {60, 192, 396, 672, 1020, … } = 12 × {5, 16, 33, 56, 85, … } where the New Drop = Previous Drop + (6 × Sequence Number − 1) × 12, e.g. the Drop 4 = 396 + (6 × 4 −1) × 12 = 672.
Remember that I did not say it was easy. On the bright side, we get to skip a lot more trials! Why is this? Because we simply do not get a match on every acceptable value of (An), e.g. 70/57: 1651 = 13×127 = 4900–3249: could in theory use An = 46, 52, 58, or 64; however the top of Family = 46 is 2107 and (2107–1651) mod 72 = 24. The other values of (An) yield 36, 48, 60 respectively. Finally at Family = 70 the value 0 is found and the process is synchronized. See Appendix 2 — Synchronization for a sample spread sheet that shows how all this fits together.
The synchronization works like a clock. For example, a value of 6 is like a clock being fast or slow by 6 hours and never being synchronized; however, a value of 12 is like a clock being fast or slow by 12 hours and always being synchronized. The time is incorrect for both, but when the time is off by 12 hours you may not notice it until you look at the AM/PM indicator. (What a weird coincidence this factoring algorithm is also synchronized at intervals of 12.)
After an initial screening, there is no need to continue looking at the incremental values of (An). The checks will continue to repeat the sequence {12, 24, 36, 48, 60, and 0.} At this point just increment An = An + 36. Yes, you get to skip 36 increments! (Be mindful that this is the optimum outcome. The Series = 5 targets will bring you back to earth fast.)
Increment Values for (An) Summary
- If Group = 0 (An mod 3 = 0); (An = even); Series = 5A or 5B (5×7 or 7×5), Next An = An + 12.
- If Group = 0 (An mod 3 = 0); (An = odd); Series = 5A or 5B (5×13 or 7×11), Next An = An + 6.
- If Group = 1 or 2 (An mod 3 = 1 or 2); (An = even); Series = 7 (5×11 or 7×13), Next An = An + 36.
- If Group = 1 or 2 (An mod 3 = 1 or 2); (An = odd); Series = 7 (5×5 or 7×7), Next An = An + 18.
Chapter 5 — JavaScript Code
The JavaScript source code for creating Integer Factoring Families Tables can be found here:
Chapter 6— Summary
When this enhanced Fermat Factoring routine is put into a spread sheet, it creates a huge file due to the tables required for the progressions. It also has a severe cap on the top number it can process, but it will work on a select range of values. By the way, it resolves 6649 in one line of active code, after spending a couple of dozen lines synchronizing the initial value of (An). See Appendix 3 — Evaluation of Value: 6649.
Supposing that the optimum reduction of trials could be reduced by a factor of 36 without significantly slowing the routine down, does reducing a calculation that takes 36 million years down to 1 million years really matter much?
I wish I had a good idea that I could share, but I doubt this essay will really impress anyone. It is after all basically just an introduction to a classification system for integer families. I do have some ideas related to finding other family members that just might allow some novel iterative routines. How does factoring with integer family DNA sound?
Update
Actually, the DNA thing did not pan out. It works, but provides no real benefit in reduced calculations or increased speed. I have found something else that might be more interesting.
It turns out that many of the steps can be eliminated by using a set of non-intuitive comparisons that occur in repeating series. Yeah, I could call it a sort of magic, but in this case it is more a matter of I do not completely understand why it works, but you can check the math out yourself. Warning, the overhead is significantly more complex than what you see here, but I think it has the potential to really accelerate the factoring process. To quote one of my fave TV programs, “All magic comes with a price!”
A discussion of Fast Fermat Integer Family Factoring can be found at:
Appendix 1 — Standard Definitions and Equations
…^… - Raise to the Power of
√[…] - Square Root Function
An - Factor of Base Value: An = (Yn + Xn)/2 where An ≥ √[N]
Bn - Factor of Separation Value: Bn = (Yn − Xn)/2
N' - Integer Prime Number: N' = N'×1 ≠ N
N - Composite Integer & Factors: N = Xn×Yn ≠ N'
N - Expanded Integer Format: N = Sa + 6×Sb
N - Fermat's Factorization: N = An^2 − Bn^2
= (An − Bn)(An + Bn)
Sa - Series Identifier: Sa = 5 or 7; same for Sa and Sb
Sb - Series Expansion: Sb = (N - Sa)/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
Yn - Larger Integer Factor of N: Yn = An + Bn where Yn ≥ Xn > 1Appendix 2 — Synchronization
The Imaginary Spread Sheet
B4: (Value to be Evaluated – If Broadcasting to All Pages)
B5: (Enter Y or N to Toggle Broadcast to Calculation Sheets)
A8: =IF(B8="","","ERROR")
B8: =IF(MOD(B4,2)=0,"Factor of 2","")
A9: =IF(B9="","","ERROR")
B9: =IF(MOD(B4,3)=0,"Factor of 3","")
A10: =IF(B10="","","ERROR")
B10: =IF(B4<5,"TOO LOW","")
B13: =$'Page I'.B$3
C13: =$'Page I'.B$4
D13: =$'Page I'.C$11
E13: =$'Page I'.O$2+1-$'Page I'.F1+IF($'Page I'.F1>0,1,0)
G13: =IF($E13<2,".",INDEX($'Page I'.G:$'Page I'.G,$E13))
H13: =IF($E13<2,".",INDEX($'Page I'.J:$'Page I'.J,$E13))
I13: =IF($E13<2,".",INDEX($'Page I'.K:$'Page I'.K,$E13))
J13: =IF($E13<2,".",INDEX($'Page I'.L:$'Page I'.L,$E13))
– Copy Cells B13–J13; Paste in Cells B14–J14;
and Change ‘Page I’ to ‘Page II’
– Copy Cells B13–J13; Paste in Cells B15–J15;
and Change ‘Page I’ to ‘Page III’
– Copy Cells B13–J13; Paste in Cells B16–J16;
and Change ‘Page I’ to ‘Page IV’
– Note there are 4 Page Sheets: I, II, III, and IV
– Each Sheet has 3 Blocks: Setup, Synchronization,
and Fermat IterationA1: (The Page Number)
B2: (Value to be Evaluated – If only using this page)
B3: =IF($Summary.B6="ON",$Summary.B4,B2) (Check for Broadcast)
B4: =$Summary.B6 (Broadcast Status)
B5: =IF(MOD(B3,6)=1,7,MOD(B3,6))
A7: =IF(B7="","","ERROR")
B7: =IF(MOD(B3,2)=0,"Factor of 2","")
C7: =IF(A7="ERROR",1,0)
A8: =IF(B8="","","ERROR")
B8: =IF(MOD(B3,3)=0,"Factor of 3","")
C8: =IF(A8="ERROR",1,0)
A9: =IF(B9="","","ERROR")
B9: =IF(B3<5,"TOO LOW","")
C9: =IF(A9="ERROR",1,0)
A10: =IF(B10="","","ERROR")
B10: =IF(B5=B13,"","Wrong Series")
C10: =IF(A10="ERROR",1,0)
C11: =SUM(C7:C10)Each Page is the same except for elements between B13 – B21
Note: @1 refers to Page 1, @2 Page 2, etc.B13: @1: 5 @2: 5 @3: 7 @4: 7
B14: @1: (5+6Z)(7+6Z) @2: (7+6Z)(5+6Z)
@3: (7+6Z)(7+6Z) @4: (5+6Z)(5+6Z)
B15: @1: 0 @2: 0 @3: 1 @4: 2
B17: @1: 1 @2: 5 @3: 3 @4: 3 (First Bn found on Even An)
B18: @1: 4 @2: 2 @3: 0 @4: 0 (First Bn found on Odd An)
B20: @1: 24 @2: 24 @3: 72 @4: 72 (Interval for Even An)
B21: @1: 12 @2: 12 @3: 36 @4: 36 (Interval for Odd An)Everything else is the same for all pages
B23: =ROUNDUP(SQRT(B$3)) (Initial An)
C23: =IF(MOD(B23,2)=0,"Even","Odd")
B24: =MOD(INT(B$23),3) (Find Group)
C24: =IF(B24=B$15,"Ok","No") (Does Group support Series?)
B26: =B$23+IF(B$24=B$15,0,IF(MOD(INT(B$23)+1,3)=B$15,1,2))
(If needed, Increment An to change Group)
C26: =IF(MOD(B26,2)=0,"Even","Odd")
B27: =MOD(INT(B$26),3) (Find New Group)
C27: =IF(B27=B$15,"Ok","No") (Group is correct now)
C29: =B20 (Interval for Even An)
D29: 0
A30: =B$26+IF(MOD(B$26,2)=0,0,3) (Next Even An Value)
B30: =A30*A30-B$17*B$17 (Top N for Family)
C30: =MOD((B30-B$3),C$29) (Is Drop a multiple of C29?)
D30: =IF(D29>0,D29,IF(C30=0,A30,D29)) (Save Value when Good)
A31: =A30+6 (Next An Value in Group B15)
– Copy Cells B30-D30 and Paste to Cells B31-D31
– Copy Cells A31-D31 and Paste to Cells A32-D32; A33-D33; A34-D34;
and A35-D35
D36: =D35 (Either 0 or Best Even An)
– Note that in this example no Even An values are synchronizedC38: =B21 (Interval for Odd An)
C38: 0
A39: =B$26+IF(MOD(B$26,2)=1,0,3) (Next Odd An Value)
B39: =A39*A39-B$18*B$18 (Top N for Family)
C39: =MOD((B39-B$3),C$38) (Is Drop a multiple of C38?)
D39: =IF(D38>0,D38,IF(C39=0,A39,D38)) (Save Value when Good)
A40: =A39+6 (Next An Value in Group B15)
– Copy Cells B39-D39 and Paste to Cells B40-D40
– Copy Cells A40-D40 and Paste to Cells A41-D41
D42: =D41 (Either 0 or Best Odd An)
– Note that in this example the Odd An value of 85 synchronizedB44: =MAX(D36,D42) (Just a Cheesy way to Pick Best)
– This is the starting value of An for the Fermat Iteration
B45: =IF(MOD(B44,2)=0,C29,C38)/2 (Half of the Interval)
B46: =IF(MOD(B44,2)=0,C29,C38) (The Interval … Repeated)
– Be aware that the bulk in the following equations is there to make
the output format pretty. Feel free to remove the content, if you
like looking at page full of #VALUE! remarks.F1: (Normally 0, but can be set to any value to scroll the table)
F2: =IF(F1>0,F1,1) (Iteration Count)
F3: =F2+1 (Next Iteration Count)
G2: =IF(B$44=0,".",B$44+(F2-1)*B$45) (Initial Value of An = B44)
G3: =IF(G2=".",".",IF(G2-I2<=1,".",IF(B$44=0,".",B$44+(F3-1)*B$45)))
(Next An = G2+B45)
H2: =IF(G2=".",".",G2*G2-$B$3) (An^2-N = G2*G2-$B$3)
I2: =IF(G2=".",".",IF(H2>0,SQRT(H2))) (Root = SQRT(H2))
J2: =IF(G2=".",".",IF(I2=INT(I2),I2,".")) (When I2=INT(I2); Bn=I2)
K2: =IF(J2=".",".",G2-J2) (Xn = G2-J2)
L2: =IF(J2=".",".",G2+J2) (Yn = G2+J2)
M2: =IF(J2=".",".",K2*L2) (Recalculate N)
N2: =IF(J2=".",".",IF($B$3=M2,"*",".")) (Does it match?)
O2: =IF(N2=".",O3,IF(O3=0,F2,IF(F2<O3,F2,O3))) (Mark the Iteration)
– Copy Cells H2-O2 and Paste to Cells H3-O3
– Copy Cells F3-O3 and Paste to Cells F4-O4
– Do this for the depth that you want to see. I keep mine around
100 lines.
Appendix 3 — Evaluation of Value: 6649
Spread Sheet Data
1 What is Fermat's Factorization Method?Fermat's factorization method, named after Pierre de Fermat, is based on the representation of an odd integer as the difference of two squares:N = a^2 − b^2That difference is algebraically factorable as (a + b)(a − b); if neither factor equals one, it is a proper factorization of N.Source: https://en.wikipedia.org/wiki/Fermat's_factorization_method
Author: Unknown
Page Date Stamp: 7 June 2021, at 07:44 (UTC)
