use strict;
use warnings;

for (
   [ 2, 2**5   ],
   [ 3, 3**9   ],
   [ 3, 3**9-1 ],
) {
    my ($b, $n) = @$_;
    my $b_m1 = $b-1;
    my $pat = map qr/1|(1+)\g{-1}{$b_m1}/;
    print( "$n: ", ('1' x $n) =~ /^$pat\z/ ?1:0, "\n" );
}