#!/usr/bin/perl -w

use strict;
use integer;
use Memoize;

memoize ('productd');

my $k = 2;
my $c = 9;
while (1){
    $c++;
    if (persistence($c) == $k){
	print "Persistence $k: $c\n";
	$k++;
	last if $k==9;
    }
}


sub persistence {
    my $prod = shift;
    my $step = 0;
    do {
	$step++;
	$prod = productd($prod);
    }until( length($prod) ==1 );
    return $step;
}

sub productd {
    my $number = shift;
    my $p = 1;
    for (split "", $number){
	$p *= $_;
    }
    return $p;
}


__END__
   16) A number's persistence is the number of steps required to reduce it to a single digit by multiplying all its
  digits to obtain a second number, then multiplying all the digits of that number to obtain a third number, and so
  on until a one-digit number is obtained. For example, 77 has a persistence of four because it requires four steps
  to reduce it to one digit: 77-49-36-18-8. The smallest number of persistence one is 10, the smallest of persistence
  two is 25, the smallest of persistence three is 39, and the smaller of persistence four is 77.
  What is the smallest number of persistence five?
  
Persistence 2: 25
  Persistence 3: 39
  Persistence 4: 77
  Persistence 5: 679
  Persistence 6: 6788
  Persistence 7: 68889
  Persistence 8: 2677889
  Persistence 9: 26888999