JCSBimp's Hexagonal Orthogonal

Here is what I have established now, and have used in forming the algorithm I shared this past week:

I have chosen to repeat a small set of definitions and concepts I have established in other posts and papers, for clarity.

Let m be an odd positive integer we wish to factor. Let c be the integer ceiling of the square root of m, and call it the Ceiling Root of m. c² is thus the least perfect square greater than m; define it as the Ceiling Square of m.

Now define a remainder r₀ as being the difference between the Ceiling Square of m and m itself: r₀=c²-m. Now we can express m as c²-r₀, and can take note of the special cases where m is a perfect square, and so r₀=0, or where r₀ is a perfect square, and the principle (used by Pierre de Fermat) that a²-b²=(a+b)(a-b) makes factorization immediate.

But what do we do if r₀ is not a perfect square? I came up with the idea of “raising the ceiling,” i.e., of increasing c by 1, 2, and so on, and looking at the remainders that result. What I know is that the factorization m=1*m gives an expression of m=a²-b² where a=(m+1)/2 and b=(m-1)/2. I call it the “trivial factorization” of m. But any x, y pair of integers, with x<y, that factor m will also give an expression of m=a²-b² by letting a=(x+y)/2 and b=(y-x)/2. Since we specify m to be odd, x and y will also be odd, and either a will be odd and b even, or vice versa. There are other interesting properties of this I have found and discussed elsewhere, but do not need to include here.

Consider the expression m=c²-r₀ when r₀ is not a perfect square. Now create a new remainder r₁ by “raising the ceiling” from c to c+1 and calculating r₁=(c+1)²-m. Since we have gone to the trouble of calculating this second remainder (it was necessary for steps which follow, though now I am going to start waving my hands a bit, i.e., presenting information without much explanation), we can check whether r₁ is a perfect square, thus yielding a simple Fermat factorization as before. But let us assume that is not the case.

Notice that r₀ and r₁ each have their own Ceiling Squares. Let us call them d₀ and d₁. Now we have it that (unless either of these are the special case allowing Fermat factorization already described):

m is between c²-d₀² and c²-(d₀-1)²; let a₀=c²-d₀²; let v₀=m-a₀;

m is between (c+1)²-d₁² and (c+1)²-(d₁-1)²; let a₁=(c+1)²-d₁²; let v₁=m-a₁.

My next step is to produce a third range, and thus a third pair of values a₂ and v₂, by stepping linearly: raising the ceiling to (c+2)² but setting d₂=2d₁-d₀. When I was exploring this, it seemed a peculiar choice because it usually seemed to violate the “betweenness” I had established: m would no longer lie within the range of values thus built.

But what happens when I make this choice is that the sequence of v₀, v₁, v₂ thus generated satisfy a quadratic polynomial, one that I have been calling the characteristic function associated with m, and denote as F(x). Those three values of v I take to be the x=0, 1, 2 values of F(x).

(Now I really am “hand-waving” because this is the part of the approach I am still figuring out.) Notice also that, due to my choices, the difference of the successive pairs of perfect squares in the ranges in which m falls, increases linearly. Also, the distance from the greater difference of squares to the *next* difference of squares in each of the ranges starts decreasing by 2, as we move from d_n² to (d_n-1)² to (d_n-2)², and so on. In other words, where the “perfect square points” fall differs linearly, both as we keep raising the ceiling linearly, and as we move from left to right on the number line examining the differences of the “raised ceiling” squares and successive perfect squares.

I realize I did not explain that very well, but it will take some effort – which I hope to make someday if this approach is successful – to explain it better.

And what I noticed is that, once I construct F(x) using v₀, v₁, v₂ to set the quadratic coefficients, whenever I get to a value of F(x) that gives me the equivalent of the value of v_n which is exactly the value of an integral point on a once-again-easy-to-construct “row polynomial” for the value of n, this will indicate that the difference between (c+n)² and m is a perfect square, allowing the Fermat method of factorization.

This at its core is practically no farther than I have figured out anything before. In fact, my first attempt at a program using this feature was much, much slower than my previous factorization routine. But the mathematical simplicity of finding these quadratic polynomials that characterize both where m falls in the ranges designed as above, and the “row polynomials” which are also quadratic and even simpler to derive … this leads me to believe that I could still be on the verge of a process that simplifies integer factorization greatly.

To use an earlier metaphor, I am not yet convinced this is a tree up which iit is worthless for me to bark.

I shall carry on.