#!/usr/bin/perl

use Bit::Vector;
use Time::HiRes 'time';
use TestGraham;
my $INFINITY = 10000;
my $BEST = 0;
my @SOLUTIONS;

sub Bit::Vector::rep {
  my ($self) = @_;
  my $h = $self->to_Hex;
  $h =~ s/^0+//;
  $h =~ s/0+$//;
  $h;
}

sub try {
  my ($set, $base, $max, $depth) = @_;
  if ($tried{$set->rep}++) {
      print "$ {prefix}Oh, I've tried this set already.\n" if $option{v};
      return;
  }
  my $prefix = '  ' x $depth;
#  print "$ {prefix}Trying {\$set}\n" if $option{v};
  if ($BEST && $max >= $BEST) {
    print "$ {prefix}  (Giving up immediately: max=$max; BEST=$BEST)\n" 
      if $option{v};
    return;
  }
  my @goal = modsquares($set);
  my $step = $goal[-1];
  print "$ {prefix}Goal items are (@goal)\n" if $option{v};
  my $n;
  if (@goal == 0) {
#    print "$ {prefix}  This one is a contender..." if $option{v};
    if ($BEST == 0 || $max < $BEST) {
      print "$ {prefix}Yes, we have a winner!\n" if $option{v};
      if ($option{r}) {
	local $" = ', ';
	my @set = $set->Index_List_Read;
	print "$ {prefix}Found a possible solution: {@set}.\n";
      }
      @SOLUTIONS = ($set);
      $BEST = $max;
      return 1;
    } elsif ($max == $BEST) {
#      print " A new tie for first place!\n" if $option{v};
#      push @SOLUTIONS, $set;
#      return 1;
    }
    print "$ {prefix}Nope, an also-ran.\n" if $option{v};
    return 0;
  }

  print "$ {prefix}Going to try multiples of $step from $base...\n"
    if $option{v};
  for ($n = $step*(1+int($base/$step)); $n < ($BEST || $INFINITY); $n+=$step) {
    if ($n % ($step * $step) == 0) {
      my ($nn, $pow);
      for ($nn = $n; $nn % $step == 0; $nn /= $step) {
	$pow++;
      }
      if ($pow % 2 == 0) {
	print "$ {prefix}$n is a multiple of an even power of $step -- useless.\n" if $option{v};
	next;
      }
    }
    if (member($set, $n)) {
      print "$ {prefix}$n is already in the set -- useless.\n" if $option{v};
      next;
    }
    my $new_max = ($n > $max ? $n : $max);
    my $new_set = $set->Clone;
    print "$ {prefix}Adding $n to the set...\n" if $option{v};
    $new_set->Bit_On($n);
    if ($tried{$new_set->rep}) {
      print "$ {prefix}No, tried that set already.\n" if $option{v};
      next;
    }
    my $success = try($new_set, $base, $new_max, $depth+1);
#    last if $success;
    if ($success && $BEST && $BEST <= $max) {
      print "$ {prefix}Bagging the rest of the multiples of $step.\n"
	if $option{v};
      return 1;
    }
  }
  print "$ {prefix}No more multiples of $step that are less than $BEST.\n"
    if $option{v};
}

sub member {
  my ($set, $n) = @_;
  return $set->contains($n);
}

sub max {
  my $m = -1;
  foreach my $e (@{$_[0]}) {
    $m = $e if $e > $m;
  }
  $m;
}

sub modsquares {
  my ($set) = @_;

#    print "  Checking {@$set} for squareness.\n";
  my %primes;
  foreach my $e ($set->Index_List_Read) {
    my @primes = factor($e);
    foreach $p (@primes) {
      $primes{$p} = 1-$primes{$p};
    }
  }
  grep $primes{$_}, sort {$a <=> $b} keys %primes;
}

{ my @primes = (2);
  my @factorization = ([0],[1],[2]);
  sub factor {
    my $n = shift;
    my $i = shift || 0;
    return @{$factorization[$n]} if defined $factorization[$n];
#    print "  Factoring $n.\n";
    if ($primes[-1] < sqrt($n)) {
      primes(sqrt($n));
    }
    while ($i < @primes) {
      my $p = $primes[$i];
      if ($n % $p == 0) {
	return @{$factorization[$n]} = ($p, factor($n/$p, $i));
      }
      $i++;
    }
    push @primes, $n;
    $factorization[$n] = [$n];
    ($n);
  }

  sub primes {
    my $top = shift;
#    print "(...Extending prime list to $top.)\n";
    my $i;
    for ($i = $primes[-1]+1; $i <= $top; $i++) {
      push @primes, $i if is_prime($i);
    }
  } 

  my @is_square ;
  sub is_square {
    my ($n) = @_;
    return $is_square[$n] if defined $is_square[$n];
    my $sq = sqrt($n);
    $is_square[$n] = 0 + ($sq == int($sq));
  }

  sub is_prime {
    my $p = shift;
    return $is_prime[$p] if defined $is_prime[$p];
    my @f = factor($p);
    return $is_prime[$p] = (0 + (@f == 1));
  }
}

sub search {
  my ($n) = shift;
  print "------------SEARCH FOR G($n)\n" if $option{v};
  $BEST = 0;
  undef @SOLUTIONS;
  undef %tried;
  my $set = Bit::Vector->new($INFINITY);
  $set->Bit_On($n);
  try($set, $n, $n)
}

while ($ARGV[0] =~ /^-(\w+)$/ ) {
  $option{$1}++;
  shift;
}
$| = 1;
my $N = shift || 3;
#for $i (2..10000) {
#  search($i);
#  printf "%03d %04d\n", $i, $BEST;
#}

sub Graham {
  return 1 if $_[0] == 1;
  $BEST = 0;
  search($_[0]);
  return $BEST;
}

