JCSBimp's Hexagonal Orthogonal

DISCLAIMER: The factorization method described here is not complete. This algorithm sets up a quadratic polynomial which produces points for a later comparison step. I will describe the comparison yet to be done, but it is not yet part of the existing algorithm I have written.

I have decided to formulate, and will later write, test, and provide in Perl code, a new algorithm to begin a process of integer factorization of a positive integer m, based on what I call the Ceiling Square of m, which is the square of the integer ceiling of the square root of m, and the Ceiling Square of the remainder when m is subtracted from its Ceiling Square.

I have based the approach I am using here on the fact that if c² is the least perfect square greater than m, any factorization of m, including the trivial factorization m equals one times m, corresponds to an expression:

m=s²-t²=(s+t)(s-t)

for some pair of positive integers s and t, and that s in this case will be greater than c, the Ceiling Root of m. My intention is eventually to arrive at a formulaic determination of s, and therefore t, based on the known values m, c, and r in the expression of m in terms of its Ceiling Square and remainder: m=c²-r. I use in my approach a method I call “raising the ceiling,” which is simply using further remainders after subtracting m from (c+1)² and (c+2)² – thus raising the ceiling, so to speak. These further remainders help me determine a characteristic polynomial for where the series of “raised ceiling” remainders fall between certain values of differences of perfect squares. I construct these differences starting with values of c²-d² and c²-(d-1)² which bound m, and then, when I raise the ceiling, I modify the ranges in a linearly-progressing fashion. I have done this as an attempt to get rid of, or at least to tame, some of the jumpy randomness of how I have observed remainders modulo ceiling squares to behave for consecutive values of m.

Steps I have not yet completed then follow: I use the characteristic polynomial thus obtained, along with the linearly-changing distribution of differences of perfect squares corresponding to values of (c-n)² for n = 0, 1, 2, …, to determine the value of n at which the characteristic polynomial will place its value directly onto a (c-n)²-d² value, which, if I have conceived this correctly, will lead to a non-trivial factorization of m, if such exists. It is in these all-important subsequent steps that I hope to increase algorithmic efficiency compared to known methods. However, I freely admit that is work yet to be done, and I do not guarantee my own success in that regard.

Here are the algorithmic steps for what I have done so far.

1. Input positive integer m.
2. If m is even, divide out factors of 2 and exit. Alternately, if further and/or complete factorization is what we want, divide out by 2, keep track of the power of 2 thus obtained as a factor, set m to the odd value >1 that remains, if any, and continue if that is the case.
3. Set c₀ to the integer ceiling of the square root of m.
4. Assign r₀=c₀²-m.
5. Set d₀ to the integer ceiling of the square root of r₀.
6. If r₀=d₀² exactly, output factorization of m as (c₀+sqrt(r₀)) times (c₀-sqrt(r₀)) and exit.
7. Set a₀=c₀²-d₀².
8. Set v₀= a₀-m. This will be the value at x=0 of the characteristic polynomial, a quadratic polynomial produced in a later step.
9. Set c₁=c₀+1.
10. Assign r₁=c₁²-m.
11. Set d₁ to the integer ceiling of the square root of r₁, and if r₁=d₁² exactly, proceed in a manner corresponding to that in Step 6 and exit.
12. Set a₁=c₁²-d₁².
13. Set v₁= a₁-m. This will be the value at x=1 of the characteristic polynomial.
14. Set c₂=c₁+1.
15. Set d₂=d₁+(d₁-d₀). This is different from the d₀ and d₁ calculations and provides a linear progression for the terms in the calculation of a₂ in the next step.
16. Set a₂=c₂²-d₂².
17. Set v₂=a₂-m. This will be the value at x=2 of the characteristic polynomial.
18. Set f₂, the coefficient of the x² term of the characteristic polynomial, to (v₀+v₂)/2-v₁.
19. Set f₁, the coefficient of the x term of the characteristic polynomial, to 2v₁-(3v₀+v₂)/2.
20. Set the constant term of the characteristic polynomial to v₀.

This produced a characteristic polynomial of the form F(x)=f₂x²+f₁x+v₀ which will correspond to the distance between c_n²-d_n² for successive values of the “raised ceiling”. Since distances between values which are differences between the raised ceiling squares perfect squares and the next greater perfect squares increase linearly, it is my hope that this approach may eventually produce a formulaic shortcut to find which value of n produces the correct “raised ceiling” square that leads to factorization.

At the worst, this could be no slower than previous factorization algorithms I have shared which calculate n (I in the past have called this value the Ascent above the Ceiling Root). Frankly, it could be improbable that this leads to anything better. I am still exploring its properties, of course, to obtain a better idea of whether or not that is the case.