Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw

check for power of a number with regex

by spx2 (Deacon)
on Oct 26, 2009 at 00:28 UTC ( #803186=perlquestion: print w/replies, xml ) Need Help??

spx2 has asked for the wisdom of the Perl Monks concerning the following question:

Is there any regex(without using ?{} or ??{} blocks, backreferences however are allowed)that can test if a number is a power of some other number ?

'1'x$number =~ /REGEX_GOES_HERE/

For example, given $number and b, to find if there is any c so that $number=bc(not explicitly finding c, merely proving it exists is enough)

'11111111' =~ /REGEX/ for b=2 would match since there are 8 ones in between quotes

Replies are listed 'Best First'.
Re: check for power of a number with regex
by ikegami (Pope) on Oct 26, 2009 at 01:25 UTC

    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" );

    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" );

    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;

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

Re: check for power of a number with regex
by JavaFan (Canon) on Oct 26, 2009 at 02:38 UTC
    A few days ago, there was a thread where it was asked if you could solve it for c == 2 (aka squares). You participated in the thread, so you should know that noone proved it possible, and the general feeling was that it is impossible for squares.

    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.

Re: check for power of a number with regex
by blokhead (Monsignor) on Oct 26, 2009 at 03:47 UTC
    There is no "plain" regex that correctly determines whether a string's length is a square, or one that determines whether a string's length is a power of some other fixed number. The corresponding languages are not regular, and these two examples are typical examples of standard homework problems in a first theory of computation course.

    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 {1n | n = bc, 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 ;)


Re: check for power of a number with regex
by ikegami (Pope) on Oct 26, 2009 at 00:55 UTC
    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" ); }
Re: check for power of a number with regex
by QM (Parson) on Oct 28, 2009 at 03:13 UTC
    It appears by the previous posts that the answer is no.

    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.

    Quantum Mechanics: The dreams stuff is made of

Log In?

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://803186]
Approved by Bloodnok
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (5)
As of 2021-10-24 00:35 GMT
Find Nodes?
    Voting Booth?
    My first memorable Perl project was:

    Results (88 votes). Check out past polls.