#!/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 Math::BigInt;
sub big ($) { new Math::BigInt $_[0]; }

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

my $k =	   9;
my $base = 10;

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

# Phase 1:
#   If the highest digit of the number is 10^N's, then 10^N mod 89 = 9.
#   (In general,  10^N mod (10k-1) = k.)  We find the smallest such N.
#   We do modulo arithmetic on normal integers, 'cause it's faster.

my $root = 10*$k - 1;
my ($exp, $mod) = (0, 1);

while ($mod != 9) {
#  printf "10^%-2d === %3d === %3d (mod %d)\n", $exp, $mod, $mod-$root, $root;
  $exp++;
  ($mod *= $base) %= $root;
}

printf "\n10^%-2d === %3d (mod %d)     <---\n\n", $exp, $mod, $root;

# Phase 2:
#   OK, we have N now.  See what (10^N-9)/89 is, since that number,
#   multiplied by the ones digit of the number, yields all of the
#   remaining digits.

my $pow = big($base) ** $exp;
my $sum = ($pow - 9) / $root;

print "(10^$exp - 9)/$root = $sum\n";
p_uninit;
print "\n";

# Phase 3:
#   Since the ones digit will become 10^N's digit after the number is
#   multiplied by 9, we want to use the lowest possible value (but not
#   zero) because it will minimize 9*A and thus A.  From this, we can
#   calculate the original number.

my $result = ($sum * $min_leading_digit) * $base + $min_leading_digit;

print "RESULT:        $result\n";
p_uninit;
print "\n";

# Phase 4:
#   Check the result.

my $rcp = "$result";
$rcp =~ s/^[+-]//;
my $roll = substr($rcp, -1);
substr($rcp, -1) = '';
$roll .= $rcp;

print "RESULT >>> 1:  $roll\n";
p_uninit;

my $mult = $result * $k;
$mult = "$mult";
$mult =~ s/^[+-]//;

print "RESULT * k:    $mult\n";
p_uninit;
print "\n";