# 
# Handling large numbers is Wrong. Using floating point in a search for
# perfect squares is also Wrong. So I use the basic concept that a perfect
# square, expressed as a product of prime factors, will only contain even
# powers.
# 
# First of all, handle special cases 1-3 - it's not worth coding around
# these, so I just put them in manually. After that, any perfect square
# has G(n)==n; and any prime has G(n)=2*n (since another prime factor is
# needed, giving powers 2, n, n; and there will be sufficient numbers
# within the range n..2n to remove the remaining factor (either an
# odd-numbered power of two, or a number with odd factors 2,3 and another
# with odd factor 3, or...).
# 
# If none of those works, it's time for the brute-force search. Start with
# the list ($base+1..$try-1). Convert each of these numbers to
# odd-numbered-prime-factors form (since the even factors are irrelevant
# to us). Strip out any primes (because there'll only be one number with
# that factor in the range, so we know we don't want it) or perfect 
# squares. Then use a binary counter to generate every possible 
# combination; "multiply" numbers by combining powers and retaining only 
# the odd-numbered ones.
# 
# This means that I don't know what actual "sequence" I'm generating. In
# theory this isn't a problem, though it makes checking harder; I used a
# slower (but more "standard") program for that.
# 
# This isn't especially fast, but gives consistent results outside the
# range where a naive approach would run into integer overflow problems.
# Unfortunately, if it doesn't get lucky fairly early on in the search,
# it tends to run out of memory. I like this approach - this is my fifth
# pass at a solution, and the fastest and most correct yet - but it needs
# more work.
# 
# Very oddly, slightly faster for me without Memoize. Perhaps the
# memory-overhead is taking more CPU than the calculations...?
# 
# 
#! /usr/bin/perl -w

use strict;
use integer;
#use Memoize;
#memoize('OddFactor');
#memoize('Multiply');

# foreach my $n (1..20,63,128,204,364,432,517,605,726,868,918,1000) {
#   my $g=&Graham($n);
#   printf("%4d  %5d\n",$n,$g);
# }

sub Graham {
  my $base=shift;
  if ($base<4) {
    return [0,1,6,8]->[$base];
  }
  my $of=&OddFactor($base);
  if (@{$of}==0) {
    return $base;
  } elsif (@{$of}==3 && $of->[2]==1) {
    return 2*$base;
  }
  my $try=$base;
  while (1) {
    $try++;
    my @list;
    foreach my $n ($base+1..$try-1) {
      my $j=&OddFactor($n);
      if (@{$j} &&
          (@{$of}!=3 || $of->[1]!=1)) {
        push @list,$j;
      }
    }
    my $max=(scalar @list);
    if ($max<0) {
      $max=0;
    }
    $max=1 << $max;
    foreach my $index (1..$max-1) {
      my $l=&Multiply(&OddFactor($base),&OddFactor($try));
      if (@{$l}==0) {
        return $try;
      }
      my $j=$index;
      my $k=0;
      while ($j) {
        if ($j & 1) {
          $l=&Multiply($l,$list[$k]);
        }
        $j >>= 1;
        $k++;
      }
      unless (@{$l}) {
        #print join(' ',@l),"\n";
        return $try;
      }
    }
  }
}

sub OddFactor {
  my $base=shift;
  my %pf;
  my $j=$base;
  my $n=2;
  while ($j>1) {
    if ($j % $n == 0) {
      $pf{$n}++;
      $j/=$n;
    } else {
      $n++;
    }
  }
  if (keys %pf == 1 && (values %pf)[0]==1) {
    return [$base,1,1];
  }
  my @out;
  foreach (keys %pf) {
    if ($pf{$_}%2 == 1) {
      push @out,$_;
    }
  }
  return [@out];
}

sub Multiply {
  my %f;
  foreach my $f (@_) {
    foreach my $pf (@{$f}) {
      if (exists($f{$pf})) {
        delete $f{$pf};
      } else {
        $f{$pf}=1;
      }
    }
  }
  return [keys %f];
}
