my $n    = ...;
    my $b    = ...;
    my $b_m1 = $b-1;

    my $pat = qr/(1|((?-2))\g{-1}{$b_m1})/;

    print( "$n: ", ('1' x $n) =~ /^$pat\z/ ?1:0, "\n" );