Well, this works:

    my $n = ...;
    my $b = ...;

    my @possibles;

    my $p = '1';
    while ($p <= $n) {
        push @possibles, ('1' x $p);
        $p *= $b;
    }

    my ($pat) =
        map qr/$_/,
        join '|',
        @possibles;

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

You can do almost all of the above inside the pattern, except for the $n <= $number check:

    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" );
[download]

Without that check, the regex engine preemptively (and sometimes accurately) throws "Infinite recursion in regex".

Back to the drawing board.

Update: As best as I can tell, you'd need to be able to change the topic as follows:

    local our $pat;
    $pat = qr/
        1
    |
        (1+)
        \g{-1}{$b_m1}
        (?(?{ $^N =~ $pat })(?=)|(?!))
    /x;
[download]

But that deosn't even work *with* (?{})!

I would focus on solving the square question before asking the more general question.

Having said that, there's a trivial answer: /^/ - which always matches. As there are always a b and a c: b == $number and c == 1. But I guess you aren't interested in that.

Thus under your constraints, the key to such a regex must be in clever use of backreferences. But it's not clear how backrefs be useful. Backrefs can only really handle linear relations in the length of strings, while exponentiation is highly non-linear.

Because 5.10 regular expressions have named captures you can use as rules, languages not being regular doesn't mean they cannot be matched by a Perl regexp. With named captures and rules, Perl regexes can match any context-free grammar. With backreferences, even more.

Now, I don't think the language {1ⁿ | n = b^c, c > 1} is context-free, but that's harder to prove than it being non-regular. And it's still not sufficient to prove it cannot be matched by a Perl regexp without the use of (?{ }) or (??{ }).

Any context-free language over a single-character alphabet is also regular (which can be shown using, for example, Parikh's theorem). So since this "language of exponentials" is non-regular, it is also non-context-free. Another way to look at it is that the pumping lemma for CFLs essentially collapses into the pumping lemma for regular languages when applied to single-character alphabets, because the concatenation operator is commutative on strings over a single-character alphabet.

I do stand by my intuition that backrefs alone (i.e., classical regexes + backrefs) won't help. But you are right, I am not able to prove it -- there is just no formal model that I'm aware of that exactly captures the expressivity of those operations, that would be amenable to impossibility proofs. I admit I hadn't thought of the new named captures & rules from 5.10 (I'm a bit behind the times). Clearly the named captures alone won't get you the regex desired in this case, but maybe some clever combination of both named rules & backrefs? I remain slightly skeptical but open-minded ;)

blokhead

Thinking out loud...the solution would have to dynamically invoke the length of a submatch as a quantifier, or count its occurrences, neither of which seems to be allowed.

Or you could cheat and check for every power less than n, in a massive alternation, by building a custom regex before the match.