our $ZERO = Math::BigInt->new(0);
our $ONE = $ZERO + 1;

# Convert a bitstring (only 1s and 0s) to a number,
# as if it were a representation of the given base.
sub bitstring_to_base {
    my $result = $ZERO;
    my $pow    = $ONE;

    for my $bit (reverse split '', $_[0]) {
        $result += $pow if $bit;
        $pow *= $_[1];
    }
    return $result;
}

# Skips over 0 and 1.
sub make_iter {
   my ($base) = @_;

   my $num = Math::BigInt->new(1);

   return sub {
      $num->binc;
      return Math::BigInt->new(
          bitstring_to_base($num->as_bin() =~ s/^0?b//r,
                            $base)
      );
   };
}
[download]

Also, the line in make_iter could take a value other than 1, as a power-of-ten starting point in a search:

my $num = Math::BigInt->new("1" . ("0" x (ARGV[1] // 0)));
[download]

I currently have a function that does the work directly in base N, so why would I want one that increments in base 2 then converts to base N? Actually, you suggest one that increments in base 2, then converts to base 10, then converts to base N!

And yes, it's quite easy to change make_iter to accept a starting position. Even the original version. This would allow work to be done in parallel.