Integer Factorization: The Least Ceiling Square LCS(r)


Let m be an odd positive integer.

Let c be the least positive integer for which c2 is greater than m, which is odd if (m+1)/2 is odd and even otherwise. c thus defined is the Ceiling Root of m, c2 is m’s Ceiling Square, and the difference between m’s Ceiling Square and m will be a non-negative integer Remainder congruent to 0 or 1 modulo 4. I have presented these principles and definitions in numerous earlier blog posts, and they appear here without the full reasoning behind them, for quick reference in what follows.

As I am spreading out sets of the odd positive integers to look at them, organized by their Ceiling Squares and corresponding Remainders, one particular detail occurs to me to need some further derivation, the answer to a question: Given a positive integer Remainder r (congruent, as above, to 0 or 1 modulo 4), what is the least Ceiling Square c2 for which r could appear in a properly derived expression of m=c2-r? Every odd positive integer m has a unique such expression, and I am interested in examining a large range of integers whose m=c2-r expression have a particular value of r, and need to know the lower bound. The “Zone Grid” approach I have taken needs this information in particular, I discovered, because if I choose a perfect square too small for a given remainder, even when the perfect square minus r is still a positive number, Grid-based calculations can go wrong.

The solution is relatively simple, but with some tricks. Knowing the smallest c2 for which r can be a remainder in a valid Ceiling Square/Remainder expression m=c2-r has to do with knowing when (c-2)2-r for the same r would still be a positive number, thus making c-2 closer to such an m’s actual Ceiling Root. Remember that c will be even when r is odd, and vice versa, since m is odd: this will be the “valid value” in the following statement. For a given r, we are looking for the least valid value of c for which c2-(c-2)2=4c-4 will be greater than r.

A few examples follow:

For r=40, 4c-4>40, c>11. As long as c is at least 13 (it must be odd here), m=c2-40 is a valid Ceiling Square/Remainder expression.

For r=41, 4c-4>41, c>45/4, and, due to the fraction and r being odd, c now must be at least 12.

For r=44, the next valid r as defined, 4c-4>44, c>12 and so must be at least 13.

For r=45, 4c-4>45, and c>49/4 must be at least 14.

Subsequent remainders produce successive values of c that follow the same zigzag pattern with a period of four for the zigzag behavior: for r congruent to 0 modulo 8, if c is the value, it will be followed by c-1 for r+1, c again for r+2, and c+1 for r+3.

The beginning of the sequences for r and the least possible c given r are:



Thus: For m=c2-r to be a valid Ceiling Square/Remainder expression resulting in an odd positive integer m, c must be at least (r+4)/4 and must be odd/even as r is even/odd.

Leave a ReplyCancel reply