#!/afs/athena/contrib/perl5/p -w

# Problem:
#   Find the smallest number whose digits "roll" by one to the the
#   right when the number is multiplied by 9.

use integer;
use strict;
use Term::ReadKey;

use Math::BigInt;
sub big  ($)  { new Math::BigInt @_; }

# BigInt tends to throw a lot (and I mean a *lot*) "uninitialized value" msgs
my $uninit = 0;
my $outstr = 0;
$SIG{'__WARN__'} = sub {
  if (($_[0] =~ /^Use of uninitialized value /)
      && ((caller)[0] eq 'Math::BigInt')) { $uninit++; }    
  elsif (($_[0] =~ /^substr outside of string /)
	 && ((caller)[0] eq 'Math::BigInt')) { $outstr++; }    
  else { warn @_; }
};
sub p_uninit {
  print "[$uninit un-initialized value operations caught during execution]\n"
    if $uninit;
  $uninit = 0;
  print "[$outstr substr()s outside of strings caught during execution]\n"
    if $outstr;
  $outstr = 0;
}

my $k =    shift(@ARGV) ||  9;
my $base = shift(@ARGV) || 10;

my $min_leading_digit = 1;	# 0_______ is usually considered not valid

# Phase 1:
#   If the highest digit of the number is a0*10^N, then a0*(10^N-k) must be
#   divisible by (10k-1).  We start by finding all numbers R such that 10^N
#   === R implies a0*10^N === a0*k for some a0, ie. a0*(R-k) === 0 for some a0.

my $root = $base*$k - 1;
my $a0;

my @interesting = (undef) x $root;
# It can be shown that (R-k)<0 are never interesting. =)
for (0..($root-1-$k)) {		# $_ = R-k
  for $a0 ($min_leading_digit..9) {
    unless (($a0 * $_) % $root) {
      $interesting[$_ + $k] ||= [];
      push @{$interesting[$_ + $k]}, $a0;
    }
  }
}

print "Interesting: ", join(" ", grep($interesting[$_], 0..($root-1))), "\n";

# Phase 2:
#   We find powers od 10 which satisfy the above requirement.  We do modulo
#   arithmetic on normal integers, instead of using BigInt's right away,
#   'cause it's faster.

my ($exp, $mod) = (0, 1);

while (1) {
#  printf "10^%-2d === %3d === %3d (mod %d)\n", $exp, $mod, $mod-$root, $root;
  $interesting[$mod] && try_it( big($base) ** $exp - $k, $interesting[$mod] );
  $exp++;
  ($mod *= $base) %= $root;
}

# Phase 3:
#   OK, we have a viable candidate for N now.  We see what (10^N-9)/89 is,
#   since that number, multiplied by the ones digit of the number, should
#   yield all of the remaining digits.
sub try_it {
  my ($prod, $digits) = @_;
  my ($blurgh, $zero);
 DIGIT:
  for $a0 (@$digits) {
    ($blurgh, $zero) = ($prod * $a0)->bdiv($root);
    ($zero==0) || (warn("division failed [$zero] for $prod*$a0"), next DIGIT);
    check_it( big($blurgh), $a0 );	# NB: $blurgh is a *string*
  }
  p_uninit;
}

# Phase 4:
#   We have an alleged solution.  We check if it actually works.
sub check_it {
  my ($aREST, $a0) = @_;
  my ($result) = $aREST*$base + $a0;

  my $pow_base = big(1);
  $pow_base *= $base while ($pow_base < $aREST);
  my $roll = $pow_base * $a0 + $aREST;

  my $mult = $result * $k;

  if ($roll == $mult) {
    print "\nRESULT:         $result\n\n";
    printf  "(RESULT >>> 1:  %s)\n", $roll;
    printf  "(RESULT * %3d:  %s)\n\n", $k, $mult;
    p_uninit;
    print "\nContinue [y/n]?\n";

    my $c;
    ReadMode 3;
    while ($c = ReadKey 0) {
      (($c eq 'y') || ($c eq 'Y')) && last;
      (($c eq 'n') || ($c eq 'N')) && exit 0;
      print "\007";
    }
    ReadMode 0;
    print "Continuing.\n\n";
  } else {
    print "wrong: $result\n";
    p_uninit;
  }
}