experimental-projects/pseudoprimes/verify_new_carmichael.pl

#!/usr/bin/perl

# Partially verify the Carmichael numbers generated by Claude Goutier, using the various Carmichael numbers generated by myself in the range [2^64, 10^22].

# Source of Carmichael numbers <= 10^22:
#   http://www-labs.iro.umontreal.ca/~goutier/OEIS/A055553/
#   https://oeis.org/A002997/a002997.7z

use 5.036;
use Storable;
use Math::GMPz;
use ntheory qw(:all);

my $carmichael_file = "programs/cache/factors-carmichael.storable";
say STDERR ":: Reading Storable file of Carmichael numbers...";

my $min = Math::GMPz::Rmpz_init();
my $max = Math::GMPz::Rmpz_init();

Math::GMPz::Rmpz_ui_pow_ui($min, 2,  64);
Math::GMPz::Rmpz_ui_pow_ui($max, 10, 22);

my $z = Math::GMPz::Rmpz_init();

my @valid_carmichael;
{
    my $carmichael = retrieve($carmichael_file);

    while (my ($key, $value) = each %$carmichael) {
        Math::GMPz::Rmpz_set_str($z, $key, 10);
        if ($z > $min and $z < $max) {
            push @valid_carmichael, $key;
        }
    }

    undef $carmichael;
}

{
    my $t1 = Math::GMPz::Rmpz_init();
    my $t2 = Math::GMPz::Rmpz_init();

    sub compare ($n1, $n2) {
        Math::GMPz::Rmpz_set_str($t1, $n1, 10);
        Math::GMPz::Rmpz_set_str($t2, $n2, 10);
        $t1 <=> $t2;
    }
}

sub binary_search_file ($file, $word) {

    my $low  = 0;           # Guaranteed to be the start of a line.
    my $high = -s $file;    # Might not be the start of a line.

    my $line;
    while ($high != $low) {

        my $mid = ($high + $low) >> 1;
        seek($file, $mid, 0);

        # $mid is probably in the middle of a line, so read the rest
        # and set $mid2 to that new position.
        scalar <$file>;
        my $mid2 = tell($file);

        if ($mid2 < $high) {    # We're not near file's end, so read on.
            $mid  = $mid2;
            $line = <$file>;
        }
        else {                  # $mid plunked us in the last line, so linear search.
            seek($file, $low, 0);
            while (defined($line = <$file>)) {
                chomp $line;
                last if compare($line, $word) >= 0;
                $low = tell($file);
            }
            last;
        }

        compare($line, $word) == -1
          ? do { $low  = $mid }
          : do { $high = $mid };
    }

    compare($line, $word) == 0
      ? $low
      : undef;
}

my $input_file = $ARGV[0] // 'carm10e22.txt';

open my $file, '<:raw:crlf', $input_file
  or die "Can't open file <<$input_file>>: $!";

foreach my $n (@valid_carmichael) {
    my $pos = binary_search_file($file, $n);

    if (!defined($pos)) {
        die "Missing Carmichael: $n\n";
    }
    else {
        say "Found $n at position $pos";
    }
}

say STDERR ":: Done!";

__END__
...
Found 150296655073360091041 at position 207454961
Found 3437007031250330646529 at position 749347096
Found 55267646670479113921 at position 137945373
Found 213552710204860549801 at position 239845171
Found 8279200287270159984001 at position 1072707280
Found 328497680817369112897 at position 286122988
Found 7037389213489676764801 at position 1004136016
Found 187438692737021648161 at position 227293519
Found 9356343200621757918901 at position 1127295208
:: Done!
perl verify_new_carmichael.pl carm10e22.txt  75.94s user 33.41s system 69% cpu 2:37.50 total