upperlim

#!/opt/maths/bin/perl
use strict;
use warnings;
use Math::GMP;
use Math::Prime::Util qw{ is_prime next_prime divisors factor_exp };
use Algorithm::Loops qw{ NextPermuteNum NestedLoops };
use POSIX qw{ :sys_wait_h };
use Memoize;

use lib 'lib';
use Type;

use lib '../lib';
use H::Diag qw{ diag };

=head1 upperlim - constrain upper limit of f(n, k)

Initially aimed at n divisible by a single squared factor without
having a fix_power(). We try all permutations of nominated primes
as the squared factor in the various spots available.

=cut

use lib './lib';
use ModFunc qw/ gcd /;

sub MBI { return Math::GMP->new(@_) }

my($opt_n, $opt_x, $opt_c, $opt_cr, $opt_s, $opt_f, $opt_fq, $opt_e) = (0) x 8;
my($opt_p, $opt_t, $opt_cp) = (2, 100000, 0);
my($opt_m, $opt_q, $opt_i, $opt_z, $opt_nq) = ([], [], [], [], []);
my($opt_ts, $opt_fact);
my $sample = 0;
my $typename = 't';
my $maxproc = 6;

while (@ARGV && $ARGV[0] =~ /^-/) {
    my $arg = shift @ARGV;
    last if $arg eq '--';
    ($sample = 1), next if $arg eq '--sample';
    ($opt_f = 1), next if $arg eq '-f';
    ($opt_fq = 1), next if $arg eq '-fq';
    ($opt_fact = 1), next if $arg eq '-fact';
    ($opt_n = $arg || shift(@ARGV)), next if $arg =~ s{^-n}{};
    ($opt_x = $arg || shift(@ARGV)), next if $arg =~ s{^-x}{};
    ($opt_cr = $arg || shift(@ARGV)), next if $arg =~ s{^-cr}{};
    ($opt_cp = $arg || shift(@ARGV)), next if $arg =~ s{^-cp}{};
    ($opt_c = $arg || shift(@ARGV)), next if $arg =~ s{^-c}{};
    ($opt_e = $arg || shift(@ARGV)), next if $arg =~ s{^-e}{};
    ($opt_s = $arg || shift(@ARGV)), next if $arg =~ s{^-s}{};
    ($opt_p = $arg || shift(@ARGV)), next if $arg =~ s{^-p}{};
    ($opt_t = $arg || shift(@ARGV)), next if $arg =~ s{^-t(?!s)}{};
    ($opt_ts = $arg || shift(@ARGV)), next if $arg =~ s{^-ts}{};
    ($typename = $arg || shift(@ARGV)), next if $arg =~ s{^-y}{};
    ($maxproc = $arg || shift(@ARGV)), next if $arg =~ s{^-mp}{};
    push(@$opt_m, $arg || shift(@ARGV)), next if $arg =~ s{^-m}{};
    push(@$opt_q, $arg || shift(@ARGV)), next if $arg =~ s{^-q}{};
    push(@$opt_i, $arg || shift(@ARGV)), next if $arg =~ s{^-i}{};
    push(@$opt_z, $arg || shift(@ARGV)), next if $arg =~ s{^-z}{};
    die "Unknown option '$arg'\n";
}

$| = 1;
my($n, $f) = map MBI($_), @ARGV;
$0 = "upperlim($n $f)";
$_ = ston($_) for ($opt_n, $opt_x);
$opt_x = $opt_n if $sample;
my $type = Type->new($typename);

my $zone = MBI(1);
my @nf = factor_exp($n);
my $tn = tau($n, \@nf);

@$_ = map split(','), @$_ for ($opt_i, $opt_q);
s/^!// && (push @$opt_nq, $_) for @$opt_q;
@$_ = sort { $a <=> $b } @$_ for ($opt_i, $opt_q);
$_ = MBI($_) for @$opt_q;

my $opt_pp;
if ($opt_p =~ /;/) {
    $opt_pp = [ map [ split /,/ ], split /;/, $opt_p ];
    my %seen;
    for (@$opt_pp) {
        my %this;
        ++$this{$_} for @$_;
        for (keys %this) {
            $seen{$_} = $this{$_} if $this{$_} > ($seen{$_} // 0);
        }
    }
    $opt_p = [ map +($_) x $seen{$_}, sort { $a <=> $b } keys %seen ];
} else {
    $opt_p = [ split /,/, $opt_p ];
    $opt_pp = [ ($opt_p) x @$opt_i ];
}

my $mods = find_mods($type);
@$opt_q = do {
    my %disallow = map +($_ => 1), @$opt_nq;
    grep !$disallow{$_}, @$opt_q;
};
my $runlist = RunList->new($type, $opt_fq);
find_perms($runlist);
print $runlist->report;
$runlist->skipto($opt_s) if $opt_s;

print "kill -HUP $$\n";
my $drain = 0;
$SIG{'HUP'} = sub { $drain = 1 };
my(%pid, $min, $max);
while (1) {
    diag(sprintf '%s: %s..%s', $opt_x, $min // 0, $max // '');
    if ($drain) {
        printf "\nDraining %s processes\n", 0 + keys %pid;
        wait_for(\%pid) while keys %pid;
        last;
    }
    if ($runlist->more) {
        if (keys(%pid) >= $maxproc) {
            wait_for(\%pid);
        } else {
            my $this = $runlist->fetch;
            my $pid = $this->run;
            if ($pid) {
                $min = $this->id if !keys %pid;
                $max = $this->id;
                $pid{$pid} = $this;
            }
        }
    } else {
        $drain = 1;
    }
}
exit 0;

sub wait_for {
    my($pids) = @_;
    my $pid = waitpid(-1, 0);
    return 0 if $pid < 0;
    my $which = delete $pids->{$pid};
    if ($which->id == $min) {
        $min = undef;
        for (values %pid) {
            my $i = $_->id;
            $min //= $i;
            $min = $i if $min > $i;
        }
    }
    $which->finalize;
    return 1;
}

sub find_mods {
    my($type) = @_;
    my %suppress;
    for (@$opt_z) {
        my($px, $rest) = split /=/, $_;
        $suppress{$px}{$_} = 1 for split /,/, $rest;
    }
    my @power = do {
        my %power = map +($_ => 1), @$opt_p;
        sort { $a <=> $b } keys %power;
    };

    my @mods;
    for my $p (@$opt_q) {
        my @px = map $p ** $_, @power;
        if ($type->name eq 'tauseq') {
            for my $i (@$opt_i) {
                if (($i % $p) != 0) {
                    # to make a p^x factor we need d == -n/i (mod p^x)
                    for (0 .. $#power) {
                        my($x, $px) = ($power[$_], $px[$_]);
                        my $m = (-$n * modinv($i, $px)) % $px;
                        last if $suppress{$px}{$m};
                        $mods[$i]{$x}{$p} = "$m";
                    }
                }
            }
        } elsif ($type->name eq 'addseq') {
            for my $i (@$opt_i) {
                # to make a p^x factor we need d == -ni (mod p^x)
                for (0 .. $#power) {
                    my($x, $px) = ($power[$_], $px[$_]);
                    my $m = (-$n * $i) % $px;
                    last if $suppress{$px}{$m};
                    $mods[$i]{$x}{$p} = "$m";
                }
            }
        } elsif ($type->name eq 'oneseq') {
            for my $i (@$opt_i) {
                # to make a p^x factor we need d == -i (mod p^x)
                for (0 .. $#power) {
                    my($x, $px) = ($power[$_], $px[$_]);
                    my $m = (-$i) % $px;
                    last if $suppress{$px}{$m};
                    $mods[$i]{$x}{$p} = "$m";
                }
            }
        } else {
            # There are no forced squares for semip()
            die "No upperlim strategy for type @{[ $type->name ]}\n";
        }
    }
use Data::Dumper; warn Dumper(\@mods);
    \@mods;
}

sub fill_perms_r {
    my($perms, $order, $cur, $i, $offset, $seen, $spare) = @_;
    if ($offset == $order->[$i][2]) {
        ++$i;
        $offset = 0;
    }
    my @copy = @$cur;
    my($prev, @last);
    if ($offset) {
        @last = @{ pop @copy };
        $prev = $last[-1];
    }

    if ($i == @$order) {
        push @$perms, $cur unless $spare;
        return;
    }
    if ($spare && (!$offset || $prev == 0)) {
        fill_perms_r($perms, $order, [ @copy, [ @last, 0 ] ],
                $i, $offset + 1, $seen, $spare - 1);
    }
    for my $mod (@{ $order->[$i][3] }) {
        next if $seen->{$mod};
        next if $offset && $prev > $mod;
        local $seen->{$mod} = 1;
        fill_perms_r($perms, $order, [ @copy, [ @last, $mod ] ],
                $i, $offset + 1, $seen, $spare);
    }
    return;
}

sub find_perms {
    my($runlist) = @_;
    my @perms;

    my %powers;
    my $target = 0;
    for (0 .. $#$opt_i) {
        my $i = $opt_i->[$_];
        my $pp = $opt_pp->[$_];
        $powers{$i} = _group($pp);
        $target += @$pp;
    }

    my $source = @$opt_q;
    my @order = sort {
        comb(scalar @{ $a->[3] }, $a->[2])
        <=>
        comb(scalar @{ $b->[3] }, $b->[2])
    } map {
        my $i = $_;
        map {
            my($power, $count) = ($_, $powers{$i}{$_});
            [ $i, $power, $count, [ sort keys %{ $mods->[$i]{$power} } ] ];
        } sort { $a <=> $b } keys %{ $powers{$i} };
    } @$opt_i;

    my $spare = ($target > $source) ? $target - $source : 0;
    $spare = $opt_e if $spare < $opt_e;
    $spare = $target -1 if $sample;
    fill_perms_r(\@perms, \@order, [], 0, 0, {}, $spare);
    my $i = 0;
    for my $p (@perms) {
        my(%none, @mods, @powers);
        for (0 .. $#order) {
            my($i, $x, $count) = @{ $order[$_] };
            for my $mod (@{ $p->[$_] }) {
                if ($mod) {
                    push @mods, [ MBI($mod), $x, $mods->[$i]{$x}{$mod} ];
                    # FIXME: gtauseq won't cope if $x > 10
                    push @powers, $x;
                } else {
                    ++$none{$i};
                }
            }
        }
        my @none = sort { $none{$b} <=> $none{$a} } keys %none;
        my $mods = $opt_fq ? do {
            my $mm = sprintf '-mm%s/', join ',', 
                    map sprintf('%s=%s', $_->[0] ** $_->[1], $_->[2]), @mods;
            my $count = @mods;
            my $subindex = 0;
            sub {
                map [ $mm . $_ ], find_mm($count, \@powers, $sample);
            };
        } : [
            map sprintf('-m%s=%s', $_->[0] ** $_->[1], $_->[2]), @mods
        ];
        $runlist->add([ $i++, $mods, \@none ]);
    }
    return;
}

sub find_mm {
    my($count, $powers, $sample) = @_;
    return +("0" x $count) if $sample;
    return NestedLoops([ map [ 0 .. $_ - 1 ], @$powers ], sub {
        join '', @_;
    });
}

sub modinv {
    my($n, $m) = @_;
    return MBI($n)->bmodinv($m);
}

sub tau {
    my($n, $fact) = @_;
    $fact //= [ factor_exp($n) ];
    my $k = 1;
    $k *= $_->[1] + 1 for @$fact;
    return $k;
}

sub ston {
    my($s) = @_;
    $s =~ s/,//g;
    $s =~ s{e(\d+)}{"0" x $1}ie;
    return MBI($s);
}

sub ntos {
    my($n) = @_;
    $n =~ s{(0+)$}{"e" . length($1)}e;
    return $n;
}

sub _group {
    my($array) = @_;
    my %result;
    ++$result{$_} for @$array;
    return \%result;
}

BEGIN {
    memoize('comb');
    sub comb {
        my($n, $k) = @_;
        return ($k == 0) ? 1
                : ($k < 0 || $k > $n) ? 0
                : ($k == 1) ? $n
                : ($k + $k > $n) ? comb($n, $n - $k)
                : comb($n - 1, $k - 1) + comb($n - 1, $k);
    }
}

package Runnable {
    sub new {
        my($class, $type, $id, $sqmods, $none) = @_;

        # unconstrained elements should be tested first, overriding
        # requested test order
        my %none = map +($_ => 1), @$none;
        my(@early, @late);
        for (split /,/, $opt_ts // '') {
            push @{ defined(delete $none{$_}) ? \@early : \@late }, $_;
        }

        # unconstrained elements should disallow known mods of
        # disallowed primes
        for my $i (@$none) {
            for my $p (@$opt_nq) {
die "FIXME: \$mods no longer looks like this";
                my $mod = $mods->[$i]{$p} // next;
die "FIXME: \$opt_p no longer looks like this either";
                push @$sqmods, sprintf '-m%s!%s', $p ** $opt_p, $mod;
            }
        }
        return bless {
            type => $type,
            id => $id,
            mods => $sqmods,
# FIXME: we must retain @$none order
            #ts => join(',', @early, keys(%none), @late),
            ts => join(',', @early, (grep $none{$_}, @$none), @late),
        }, $class;
    }
    sub id { shift->{id} }
    sub type { shift->{type} }
    sub logpath {
        my($self) = @_;
        sprintf '%s/upperlim/%s.%s-%s', $self->type->logpath, $n, $f, $self->id;
    }
    sub command {
        my($self) = @_;
        return [
            '-n', '' . $opt_n,
            '-x', '' . $opt_x,
            ($opt_c ? ('-c', $opt_c) : ()),
            ($opt_cr ? ('-cr', $opt_cr) : ()),
            ($opt_cp ? ('-cp', $opt_cp) : ()),
            ($opt_fact ? ('-fact') : ()),
            ($opt_f ? ('-f') : ()),
            ($opt_t ? ('-t', $opt_t) : ()),
            ($self->{ts} ? ('-ts', $self->{ts}) : ()),
            (map "-m$_", @$opt_m),
            @{ $self->{mods} },
            $n,
            $f,
        ];
    }
    sub run {
        my($self) = @_;
        my $type = $self->type;
        my $named = sprintf 'u(%s,%s:%s)', $n, $f, $self->id;
        my $cmd = $self->command;
        my $log = $self->logpath;
        return $type->invoke('gtauseq', $named, $cmd, $log);
    }
    my %seen519;
    sub finalize {
        my($self) = @_;
        my $log = $self->logpath;
        my $fh;
        open($fh, '<', $log) or die "$log: $!";
        my %line;
        while (<$fh>) {
            chomp;
            my($rc) = /^(\d{3}) / or die "Can't parse log line '$_'";
            push @{ $line{$rc} }, $_;
        }
        close $fh;

        for (@{ $line{402} }) {
            # 402 Error: all values (mod 2) disallowed (1.780s)
            return;
        }
        for (@{ $line{404} }) {
            # 404 Error: 48 + 0d must be divisible by n (0.03s)
            return;
        }
        for (@{ $line{500} }) {
            # 500 f(132, 12) > 1e20 mod(8=7, 3=2, 11=10, 25=9)  (2.290s)
            return;
        }
        for (@{ $line{502} }) {
            # 502 Error: fixed 4 not available in tau 38
            return;
        }
        for (@{ $line{519} }) {
            # 519 Found only 0 of 1 values matching 813 (mod 841)
            unless ($seen519{$_}++) {
                ::diag("");
                print "$_\n";
            }
            return;
        }
        for (@{ $line{200} }) {
            ::diag("");
            # 200 f(132, 12) = 8077375161476199132962631959 mod(8=7, 3=2, 11=10, 25=9)  (0.120s)
            print "@{[ $self->id ]}: gtauseq @{ $self->command }\n$_\n";
            if (/= (\d+) /) {
                my $new = ::MBI($1);
                $opt_x = $new if $opt_x > $new;
            } else {
                die "Could not parse result";
            }
            return;
        }
        die "Failed to find answer in $log\n";
    }
};

package RunList {
    sub new {
        my($class, $type, $genmod) = @_;
        return bless {
            type => $type,
            list => [],
            genmod => $genmod,
        }, $class;
    }
    sub report {
        my($self) = @_;
        my $list = $self->{list};
        return sprintf "Found %d perms (%d .. %d)\n",
                0 + @$list,
                (@$list ? map($_->[0], @$list[0, -1]) : (0, -1));
    }
    sub skipto {
        my($self, $to) = @_;
        ($to, my $subto) = split /\./, $to;

        my $list = $self->{list};
        shift @$list while @$list && $list->[0][0] < $to;

        if ($self->{genmod} && @$list) {
            $self->unpack_mod;
            if ($subto) {
                splice @{ $self->{sublist} }, 0, $subto;
                $self->{suboff} += $subto;
            }
        }
        return;
    }
    sub unpack_mod {
        my($self) = @_;
        $self->{sublist} = [ $self->{list}[0][1]->() ];
        $self->{suboff} = 0;
        return;
    }
    sub add {
        my($self, $runargs) = @_;
        push @{ $self->{list} }, $runargs;
        return;
    }
    sub more {
        my($self) = @_;
        return @{ $self->{list} } ? 1 : 0;
    }
    sub fetch {
        my($self) = @_;
        my @args;
        if ($self->{genmod}) {
            $self->unpack_mod unless $self->{sublist};
            my $off = $self->{suboff}++;
            @args = @{ $self->{list}[0] };
            $args[0] .= ".$off";
            $args[1] = shift @{ $self->{sublist} };
            if (@{ $self->{sublist} } == 0) {
                delete $self->{sublist};
                shift @{ $self->{list} };
            }
        } else {
            @args = @{ shift @{ $self->{list} } };
        }
        return Runnable->new($self->{type}, @args);
    }
};