## Integer Factorization: Series of Ceiling Squares, Take 3 (or 4)

I embarrassed myself twice this week, having to take down insufficiently debugged algorithms and Perl code for not testing thoroughly enough. However, I now have an algorithm I’ve once again tested, and will test some more (yes, opening the possibility that a bug will require me to correct/retract), and this one has a symmetric quality that my previous strategy lacked. The error – and the asymmetry – was in how I handled the case of remainders that were multiples of 4.

The algorithm:

``````Here are instructions to derive the Ceiling Square for a positive integer m
in such a way that a Series of Ceiling Squares formed from successive remainders
will terminate.

If m is a perfect square, it is equal to its Ceiling Square.

Otherwise:

m = c^2 - r, where

c is either ceil(sqrt(m)) or ceil(sqrt(m))+1 as follows:

Case 1: m is odd.

Choose c to be the even or odd one of those two choices when (m+1/2) is even or odd,
respectively.

This corresponds to whether m is congruent to 3 or 1 modulo 4.

m is congruent to 3 modulo 4:
c is even, c^2 is congruent to 0 modulo 4, and therefore
r will be congruent to 1 modulo 4.

m is congruent to 1 modulo 4:
c is odd, c^2 is congruent to 1 modulo 4, and therefore
r will be congruent to 0 modulo 4.

Case 2: m is even.

c is either ceil(sqrt(m)) or ceil(sqrt(m))+1 as follows:

Select which value of c as follows, according to whether m is congruent to 0 or 2 modulo 4.

m is congruent to 0 modulo 4:
c is always ceil(sqrt(m)).

m is congruent to 2 modulo 4:
If c is even, add 1 to make c odd.
``````

The Perl script:

``````#!/usr/bin/perl
use strict;
use warnings;
use POSIX qw/ceil/;

my \$remain = \$ARGV;
my ( \$croot, \$csquare );

print "The Series of Ceiling Roots of \$remain:\n  ";
while ( \$remain > 0 ) {
\$croot = ceiling_root( \$remain );
print "\$croot ";
\$csquare = \$croot * \$croot;
\$remain = \$csquare - \$remain;
}
print "\$remain\n";

sub ceiling_root {
my \$the_int = \$_;
my ( \$the_root, \$crit_bit );

if ( ( \$the_int % 2 ) == 1 ) {
\$the_root = ceil( sqrt( \$the_int ) );
\$crit_bit = ( ( \$the_int + 1 ) / 2 ) % 2;
if ( ( \$the_root % 2 ) != \$crit_bit ) {
\$the_root++;
}
}
else {
\$the_root = ceil( sqrt( \$the_int ) );
if ( ( \$the_int % 4 ) != 0 ) {
if ( ( \$the_root % 2 ) == 0 ) {
\$the_root++;
}
}
}
return \$the_root;
}
``````