Advertisements

I believe this is running correctly. I’ll certainly correct it if it is not. EDIT: I have indeed updated the code. I suspect it’s almost if not entirely in its final form. A couple of small values in the entire set of discrete semiprimes whose primes are less than 100 showed negative discriminants, but I do not know whether I should even worry about that infrequent occurrence.

```
#!/usr/bin/perl
use strict;
use warnings;
use POSIX qw/ceil/;
my $m = $ARGV[0];
my $twopow = 0;
my ( $f1, $f2, $f3 );
while ( ( $m % 2 ) == 0 ) {
$twopow++;
$m /= 2;
}
if ( $twopow ) {
print "$m has a factor of 2 to the power of $twopow.\n";
if ( $m == 1 ) {
print "$m has no other factors.\n";
exit;
}
else {
print "Proceeding with characterization of $m.\n";
}
}
my $c0 = ceil( sqrt( $m ) ); # ceiling square of m
print "The Ceiling Square of $m is ${c0}^2.\n";
my $mm4 = $m % 4;
my $cc2 = $c0 % 2;
print "$m is congruent to $mm4 modulo 4, and the ceiling square is ";
if ( $cc2 ) {
print "odd";
}
else {
print "even";
}
print ".\nAll expressions of $m as the difference of two squares will have\n";
print " the form s^2 - t^2 where s is ";
if ( $mm4 == 1 ) {
print "odd and t is even.\n";
}
else {
print "even and t is odd.\n";
}
my $add1 = 0;
if ( ( ( $mm4 == 1 ) && ( $cc2 == 0 ) )
|| ( ( $mm4 == 3 ) && ( $cc2 == 1 ) ) ) {
print "This means we must adjust the initial ceiling square from $c0 to ";
$c0++;
$add1 = 1;
print "$c0.\n";
}
my $r0 = $c0 * $c0 - $m;
if ( $r0 == 0 ) {
print "$m is a perfect square: $c0 times $c0.\n";
print "For further characterization, resubmit with argument of $c0.\n";
exit;
}
my $d0 = ceil( sqrt( $r0 ) );
if ( ( $d0 * $d0 ) == $r0 ) {
print "$m = $c0", "^2 - ", $d0, "^2.\n";
print " Factorization into ", $c0 - $d0, " times ", $c0 + $d0;
print " immediately follows.\n";
exit;
}
my $a0 = $c0 * $c0 - $d0 * $d0;
my $b0 = $c0 * $c0 - ( $d0 - 1 ) ** 2;
my $v0 = $m - $a0;
print "$m = $c0", "^2 - $r0, putting it between\n";
print " A0 = $a0 = $c0", "^2 - $d0", "^2 and\n";
print " B0 = $b0 = $c0", "^2 - ", $d0 - 1, "^2.\n";
print " M - A0 = $v0. Span of this range is ", $b0 - $a0, ".\n";
my $c1 = $c0 + 2;
my $r1 = $c1 * $c1 - $m;
my $d1 = ceil( sqrt( $r1 ) );
if ( ( $d1 * $d1 ) == $r1 ) {
print "$m = $c1", "^2 - ", $d1, "^2.\n";
print " Factorization into ", $c1 - $d1, " times ", $c1 + $d1;
print " immediately follows.\n";
exit;
}
my $a1 = $c1 * $c1 - $d1 * $d1;
my $b1 = $c1 * $c1 - ( $d1 - 1 ) ** 2;
my $v1 = $m - $a1;
print "$m = $c1", "^2 - $r1, putting it between\n";
print " A1 = $a1 = $c1", "^2 - $d1", "^2 and\n";
print " B1 = $b1 = $c1", "^2 - ", $d1 - 1, "^2.\n";
print " M - A1 = $v1. Span of this range is ", $b1 - $a1, ".\n";
my $c2 = $c1 + 2;
my $r2 = $c2 * $c2 - $m;
my $d2 = ceil( sqrt( $r2 ) ); # *** not the actual d2 value we will use ***
if ( ( $d2 * $d2 ) == $r2 ) {
print "$m = $c2", "^2 - ", $d2, "^2.\n";
print " Factorization into ", $c2 - $d2, " times ", $c2 + $d2;
print " immediately follows.\n";
exit;
}
$d2 = 2 * $d1 - $d0;
my $a2 = $c2 * $c2 - $d2 * $d2;
my $b2 = $c2 * $c2 - ( $d2 - 1 ) ** 2;
my $v2 = $m - $a2;
print "$m = $c2", "^2 - $r2, and the linear progression of range gives:\n";
print " A2 = $a2 = $c2", "^2 - $d2", "^2 and\n";
print " B2 = $b2 = $c2", "^2 - ", $d2 - 1, "^2.\n";
print " M - A2 = $v2. Span of this range is ", $b2 - $a2, ".\n";
if ( $b2 < $m ) {
print " (Note that this time, M falls to the right of B2.)\n";
}
print "\n This gives the x=";
print $add1, ", ", $add1 + 2, ", ", $add1 + 4;
print " values of the characteristic";
print " polynomial as:\n";
print " $v0, $v1, and $v2, leading to characteristic polynomial:\n";
$f1 = ($v0 - 2 * $v1 + $v2) / 8;
if ( $add1 ) {
$f2 = ( 3 * $v1 - $v2 ) / 2 - $v0;
$f3 = ( 15 * $v0 - 10 * $v1 + 3 * $v2 ) / 8;
}
else {
$f2 = $v1 - ( 3 * $v0 + $v2 ) / 4;
$f3 = $v0;
}
print " F(X) = $f1", "X^2 + $f2", "X + $f3.\n";
my $discrim = $f2 * $f2 - 4 * $f1 * $f3;
print " The Discriminant of F(x) is $discrim.\n";
```

# Sample Run:

```
➜ Programs characterize.pl 3589
The Ceiling Square of 3589 is 60^2.
3589 is congruent to 1 modulo 4, and the ceiling square is even.
All expressions of 3589 as the difference of two squares will have
the form s^2 - t^2 where s is odd and t is even.
This means we must adjust the initial ceiling square from 60 to 61.
3589 = 61^2 - 132, putting it between
A0 = 3577 = 61^2 - 12^2 and
B0 = 3600 = 61^2 - 11^2.
M - A0 = 12. Span of this range is 23.
3589 = 63^2 - 380, putting it between
A1 = 3569 = 63^2 - 20^2 and
B1 = 3608 = 63^2 - 19^2.
M - A1 = 20. Span of this range is 39.
3589 = 65^2 - 636, and the linear progression of range gives:
A2 = 3441 = 65^2 - 28^2 and
B2 = 3496 = 65^2 - 27^2.
M - A2 = 148. Span of this range is 55.
(Note that this time, M falls to the right of B2.)
This gives the x=1, 3, 5 values of the characteristic polynomial as:
12, 20, and 148, leading to characteristic polynomial:
F(X) = 15X^2 + -56X + 53.
The Discriminant of F(x) is -44.
```

## Leave a Reply to Integer Factorization: “characterize” Script Updated – JCSBimp’s Hexagonal Orthogonal Cancel reply