**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:*4*9*= 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* s*econd, 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=6*

The 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.*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.*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.*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.*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.*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.*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 > 1*

**Appendix 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#VALUE!

the output format pretty. Feel free to remove the content, if you

like looking at page full ofremarks.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)