This is based on what you did, except it prints out a status bar for "time remaining." Well, actually not a status bar. Just something along the lines of

On 22000000. Minutes required: 0.718182
On 21000000. Minutes required: 0.683761
On 20000000. Minutes required: 0.645359
On 19000000. Minutes required: 0.611250
........
[download]

I think I liked yours the best because it was the closest in spirit to my, even slower, initial attempt. Cheers :)

use strict;
use warnings;

my $start = 98765432;

my $start_time = time;
my $div = 1000000;
my $max_tries = ( ( $start - ( $start % $div) ) / $div ); 
my $tries;

LOOP: for (my $i = $start; $i > 0; $i--) {
  if ( $i % $div == 0 ) {
        $tries++;
        my $tries_remaining = $max_tries - $tries;    #print "tries re
+maining: $tries_remaining\n";
        my $seconds_per_tries = ( time() - $start_time ) / $tries;
        my $estimated_minutes_to_completion = $seconds_per_tries * $tr
+ies_remaining / 60;
        
        $estimated_minutes_to_completion = sprintf ( "%2f", $estimated
+_minutes_to_completion );
        
        print "On $i. Minutes required: $estimated_minutes_to_completi
+on\n"; 
  }
  next if $i =~ /0/ or $i =~ /(\d)\d*\1/;
  $i % $_ and next LOOP for split '', $i;
  print "$i\n";
  exit;
}
[download]