JCSBimp's Hexagonal Orthogonal

I posted a chart a little after midnight last night, with no explanation, except that it had to do with my integer factorization study. After more study and thought today about what the entries in the chart mean and imply, I am ready to share and explain. But the chart has CHANGED.

The chart is a simple place for me to organize and place the output of a Perl script I wrote to do the following: Given positive integers A and B, with A even, and starting with x=0, it evaluates the value of y=x²+Ax+B, and increases the value of x by 1 unless and until y is a perfect square. Well, if it does not find such a value after a long while, it bails out. “A long while” in the Perl script as written is x=500000.

But how this chart relates to integer factorization is the reason I made it, and so I should explain that now. This explanation will also show why certain squares and regions of squares are blacked out, while others are blue or yellow, and some of the numbers are red.

As I explained in my past few math-y posts, I saw that there was a relationship between discrete semiprimes – products of two distinct prime numbers – and quadratic polynomials as follows: Given a positive integer m, let c be the least positive integer for which m is less than or equal to c². I call c the Ceiling Root of m, and c² the Ceiling Square of m. If m is a perfect square, its difference to c² is zero. Otherwise, there is a remainder r so that m=c²-r. If m is a discrete semiprime, and r is itself a perfect square, Fermat’s two-square method of factorization, by expressing m as (c+sqrt(r)) times (c-sqrt(r)), finds a factorization of m easily; factorization programs consider this a special case that saves lots of work.

I have shared elsewhere that whether or not m is a prime number, s=(m+1)/2 and t=(m-1)/2 satisfy s²-t²=m. This is the trivial case that only gives the factorization m = m times 1 using Fermat’s method. But if m is composite, and can be expressed m=ab for integers a and b each greater than 1, with a less than or equal to b for convenience (and only equal when m is a perfect square: another easy condition for factorization), then a different s and t are available to give a non-trivial factorization: Let s=(a+b)/2 and t=(b-a)/2. These also satisfy m=s²-t² and give non-trivial factors.

I’m getting to where the quadratic polynomials fit in, don’t worry. It’s taking a little more explanation than I thought. But I want it to be as plain to the reader as this chart is becoming to me.

So to find factors of a composite positive integer m, it turns out that one needs to find the least perfect square greater than or equal to m’s Ceiling Square that, when m is subtracted from it, will yield another perfect square. If the s we discover by the property above is equal to c, the ceiling square, factorization is easy. if s is greater, then we’ve had to do a bit more work to find it, and the term I give to s-c is the ascent of the corresponding factorization of m.

I found that ascent in a place I did not expect, and it relates to the Ceiling Root and Remainder of m:

Consider the generalized monic quadratic equation y=x²+Ax+B I discussed above. Choose the coefficient A to be 2 times the Ceiling Root of m, the c value above. Choose B to be the remainder, r. When m=c²-r, the smallest non-negative integer value of x that makes the corresponding equation y=x²+2cx+r produce a perfect square is the ascent corresponding to a factorization of m.

So my chart gives consecutive values of 2c down the rows, and values of r across the columns, and the cells of the chart are the ascent values for the different values of m=c²-r thus produced. Since my study confines its attention mainly to odd discrete semiprimes, I black out squares beyond r=2c-2, and I confine my attention to c odd and r even, or vice versa. These restrictions black out all but a triangular-ish checkerboard area that you see. The blue cells correspond to odd prime numbers which do, in fact, have ceiling squares and remainders, but their ascent gives only the trivial factorization, and is thus about as large as an ascent can be. It’s kind of an integer ceiling for the entries in the table. The blue squares increase in value with an observed regularity – I will probably be able to characterize it with a simple equation with a little study.

What will take more study – and I hope enough study can actually make it happen – is discovering a formula/equation/method for the odd composite numbers in the table.

I’ve not explained everything crystally clearly, I know. The bold red numbers (corresponding to discrete semiprimes among the composite integers) and the fact that the odd integers are in BACKWARDS order to see their ascents in the table, … these are explanations I did not think added much to this report on my progress. I even left out why the cells for the first two odd primes are green, not blue. Again, interesting, but really just extra info. Just wanted, as I do in these blog entries, to share an accurate picture of the work going on… in this case and others, with actual pictures.