Within the scope of this question, let us consider only strings which consist of the character x repeated arbitrary number of times.

For example:


(Well, actually it doesn't have to be x - any character is fine as long as the whole string only has 1 type of character)

Write a regex in any regex flavor of your choice to match all strings whose length is n4 for some non-negative integer n (n >= 0). For example, strings of length 0, 1, 16, 81, etc. are valid; the rest are invalid.

Due to technical limitations, values of n bigger than 128 are hard to test against. However, your regex should, at least in theory, work with all numbers up to infinity (assuming unlimited memory and computation time).

Note that you are not allowed to execute arbitrary code in your regex (to Perl users). Any other syntax (look-around, back-reference, etc.) is allowed.

Please also include a short explanation about your approach to the problem.

(Please don't paste auto generated regex syntax explanation, since they are useless)

This is . For each regex flavor, the regex compatible with that flavor having the shortest length in bytes wins in that category. The shortest of all of the answers wins overall.

Standard loopholes are disallowed.

Note that this challenge was originally posted as a puzzle, not code-golf. But the actual answers basically treated it as code-golf anyway, just without actually specifying their sizes in bytes. That has now been fixed, to give the challenge objective winning criteria and make it on-topic for CGCC.


Regex engine(s) Length in bytes / Winner(s)
ECMAScript 41DC.223051
ECMAScript / Python or better 43DC.223051
Boost 43DC.223051
Python 43DC.223051
Python (with regex) 43DC.223051
Ruby 43DC.223051
Perl 32DC.223048
Java 32DC.223048
PCRE 35DC.223129, DC.223048
Perl / PCRE 35DC.223129, DC.223048
PCRE1 / PCRE2 v10.33 or earlier 34DC.223129
PCRE2 v10.34 or later 32DC.223048
.NET 32DC.223048
Perl / Java / PCRE v10.34 or later / .NET 32DC.223048
Perl / Java / PCRE / .NET 35DC.223048
Perl / Java / PCRE / .NET, no lookarounds 39primo

7 Answers 7


Perl / Java / PCRE / .NET, 39 bytes

Another Solution

This is, in my opinion, one of the most interesting problems on the site. I need to thank deadcode for bumping it back up to the top.


39 bytes, without any conditionals or assertions... sort of. The alternations, as they're being used (^|), are a type of conditional in a way, to select between "first iteration," and "not first iteration."

This regex can be seen to work here: http://regex101.com/r/qA5pK3/1

PCRE interprets the regex correctly, and it has also been tested in Perl up to n = 128, including n4-1, and n4+1.


The general technique is the same as in the other solutions already posted: define a self-referencing expression which on each subsequent iteration matches a length equal to the next term of the forward difference function, Df, with an unlimited quantifier (*). A formal definition of the forward difference function:


Additionally, higher order difference functions may also be defined:


Or, more generally:

\$D_f^k(n)=D_f^{k-1}(n+1)-D_f^{k-1}(n)=\sum\limits_{i=0}^k{(-1)^i}{k\choose i}f(n+k-i)\$

The forward difference function has a lot of interesting properties; it is to sequences what the derivative is to continuous functions. For example, Df of an nth order polynomial will always be an n-1th order polynomial, and for any i, if Dfi = Dfi+1, then the function f is exponential, in much the same way that the derivative of ex is equal to itself. The simplest discrete function for which f = Df is 2n.

f(n) = n2

Before we examine the above solution, let's start with something a bit easier: a regex which matches strings whose lengths are a perfect square. Examining the forward difference function:


Meaning, the first iteration should match a string of length 1, the second a string of length 3, the third a string of length 5, etc., and in general, each iteration should match a string two longer than the previous. The corresponding regex follows almost directly from this statement:


It can be seen that the first iteration will match only one x, and each subsequent iteration will match a string two longer than the previous, exactly as specified. This also implies an amazingly short perfect square test in perl:


This regex can be further generalized to match any n-gonal length:

Triangular numbers:

Square numbers:

Pentagonal numbers:

Hexagonal numbers:


f(n) = n3

Moving on to n3, once again examining the forward difference function:


It might not be immediately apparent how to implement this, so we examine the second difference function as well:


So, the forwards difference function does not increase by a constant, but rather a linear value. It's nice that the initial ('-1th') value of Df2 is zero, which saves an initialization on the second iteration. The resulting regex is the following:


The first iteration will match 1, as before, the second will match a string 6 longer (7), the third will match a string 12 longer (19), etc.

f(n) = n4

The forward difference function for n4:


The second forward difference function:


The third forward difference function:


Now that's ugly. The initial values for Df2 and Df3 are both non-zero, 2 and 12 respectively, which will need to be accounted for. You've probably figured out by now that the regex will follow this pattern:


Because the Df3 must match a length of 12 on the second iteration, a is necessarily 12. But because it increases by 24 each term, the next deeper nesting must use its previous value twice, implying b = 2. The final thing to do is initialize the Df2. Because Df2 influences Df directly, which is ultimately what we want to match, its value can be initialized by inserting the appropriate atom directly into the regex, in this case (^|xx). The final regex then becomes:


Higher Orders

A fifth order polynomial can be matched in with the following regex:

f(n) = n5 is a fairly easy excercise, as the initial values for both the second and fourth forward difference functions are zero:


For six order polynomials:

For seventh order polynomials:


Note that not all polynomials can be matched in exactly this way, if any of the necessary coefficients are non-integer. For example, n6 requires that a = 60, b = 8, and c = 3/2. This can be worked around, in this instance:


Here I've changed b to 6, and c to 2, which have the same product as the above stated values. It's important that the product doesn't change, as a·b·c·… controls the constant difference function, which for a sixth order polynomial is Df6. There are two initialization atoms present: one to initialize Df to 2, as with n4, and the other to initialize the fifth difference function to 360, while at the same time adding in the missing two from b.

  • \$\begingroup\$ Which engines have you tested this on? \$\endgroup\$ Feb 25, 2014 at 11:08
  • \$\begingroup\$ I finally understand what is going on. Indeed the only thing needed is support for forward-reference. +1 \$\endgroup\$ Feb 25, 2014 at 11:39
  • \$\begingroup\$ @nhahtdh ahh, you're right. Forward-references aren't necessarily a universal feature either. \$\endgroup\$
    – primo
    Feb 25, 2014 at 13:23
  • 2
    \$\begingroup\$ Excellent! I love how short, simple and easy to understand this is. With its shallow nesting, it is easy to calculate by hand how it will behave. Also, it is equally as fast as Volatility's and nhahtdh's solutions. And I love your detailed explanation, including the demonstration that this can even be extended to polynomials. I'd give bonus points if I could. \$\endgroup\$
    – Deadcode
    Feb 26, 2014 at 18:17
  • 1
    \$\begingroup\$ I managed to match your answer's 39 byte length! \$\endgroup\$
    – Deadcode
    Apr 9, 2021 at 7:32

Perl / PCRE / .NET, 66 bytes

This (ir)regular expression seems to work.


This regex is compatible with PCRE, Perl, .NET flavors.

This basically follows a "difference tree" (not sure if there's a proper name for it), which tells the regex how many more x's to match for the next fourth power:

1     16    81    256   625   1296  2401 ...
   15    65    175   369   671   1105 ...
      50    110   194   302   434 ...
         60    84    108   132 ...
            24    24    24 ...  # the differences level out to 24 on the 4th iteration

\2, \3, \4 stores and updates the difference as shown on the 2nd, 3rd and 4th rows, respectively.

This construct can easily be extended for higher powers.

Certainly not an elegant solution, but it does work.

  • \$\begingroup\$ +1. Great answer. Although this answer is different from mine (it uses conditional regex, while mine does not), it has the same spirit as my solution (exploiting the difference tree and make use of the forward-declared back-reference of some regex engines). \$\endgroup\$ Jan 26, 2014 at 8:32
  • \$\begingroup\$ neat idea re difference tree. for squares the tree is 1 4 9 16 ... 3 5 7 ... 2 2 2, right? \$\endgroup\$
    – Sparr
    Feb 26, 2016 at 21:20
  • \$\begingroup\$ @Sparr thanks, and yes \$\endgroup\$
    – Volatility
    Feb 27, 2016 at 2:52

ECMAScript / Perl / Java / Python / Ruby / PCRE / .NET, 50 bytes

Here is a solution that does not use conditionals, forward-declared or nested backreferences, lookbehind, balancing groups, or regex recursion. It only uses lookahead and standard backreferences, which are very widely supported. I was inspired to operate under these limitations due to Regex Golf, which uses the ECMAScript regex engine.

The way this 50 byte regex works is conceptually rather simple, and completely different than all the other submitted solutions to this puzzle. It was surprising to discover that this kind of mathematical logic was expressible in a regex.

      \2                     \4  \5

(Capture groups are labeled above the regex)

The regex can be generalized to any power simply by replacing the 4 in {4} with the desired power.

Try it online! - ECMAScript (SpiderMonkey)
Try it online! - ECMAScript (Node.js - faster)
Try it online! - Perl (faster still)
Try it online! - Java
Try it online! - Python
Try it online! - Ruby
Try it online! - PCRE (fastest)
Try it online! - .NET

It works by repeatedly dividing away the smallest fourth power of a prime that the current value is divisible by. As such the quotient at each step is always a fourth power, iff the original value was a fourth power. A final quotient of 1 indicates that the original value was indeed a fourth power; this completes the match. Zero is also matched.

First it uses a lazy capture group \2 to capture the number's smallest factor larger than 1. As such, this factor is guaranteed to be prime. For example, with 1296 (6^4) it will initially capture \2 = 2.

Then, at the beginning of a loop that is repeated 4 times, it tests to see if the current number is divisible by \2, with (?=\2+$). The first time through this loop, this test is useless, but its purpose will become apparent later.

Next inside this inner loop, it uses the greedy capture group \4 to capture the number's largest factor smaller than itself: (?=(x+)(\4+)$). In effect this divides the number by its smallest prime factor, \2; for example, 1296 will initially be captured as \4 = 1296/2 = 648. Note that the division of the current number by \2 is implicit. While it is possible to explicitly divide the current number by a number contained in a capture group (which I only discovered four days after posting this answer), doing this would make for a slower and harder-to-understand regex, and it is not necessary, since a number's smallest factor larger than 1 will always match up with its largest factor smaller than itself (such that their product is equal to the number itself).

Since this kind of regex can only "eat away" from the string (making it smaller) by leaving a result at the end of the string, we need to "move" the result of the division to the end of the string. This is done by capturing the result of subtraction (the current number minus \4), into the capture group \5, and then, outside the lookahead, matching a portion of the beginning of the current number corresponding to \5. This leaves the remaining unprocessed string at the end matching \4 in length.

Now it loops back to the beginning of the inner loop, where it becomes apparent why there is a test for divisibility by the prime factor. We have just divided by the number's smallest prime factor; if the number is still divisible by that factor, it means the original number might be divisible by the fourth power of that factor. The first time this test is done it is useless, but the next 3 times, it determines if the result of implicitly dividing by \2 is still divisible by \2. If it is still divisible by \2 at the beginning of each iteration of the loop, then this proves that each iteration divided the number by \2.

In our example, with an input of 1296, this will loop through as follows:

\2 = 2
\4 = 1296/2 = 648
\4 = 648/2 = 324
\4 = 324/2 = 162
\4 = 162/2 = 81

Now the regex can loop back to the first step; this is what the final * does. In this example, 81 will become the new number; the next loop will go as follows:

\2 = 3
\4 = 81/3 = 27
\4 = 27/3 = 9
\4 = 9/3 = 3
\4 = 3/3 = 1

It will now loop back to the first step again, with 1 as the new number.

The number 1 cannot be divided by any prime, which would make it a non-match by (?=(xx+?)\2+$), so it exits the top-level loop (the one with * at the end). It now reaches the x?$. This can only match zero or one. The current number at this point will be 0 or 1 if and only if the original number was a perfect fourth power; if it is 0 at this point, it means that the top-level loop never matched anything, and if it is 1, it means the top-level loop divided a perfect fourth power down until it wasn't divisible by anything anymore (or it was 1 in the first place, meaning the top-level loop never matched anything).

It's also possible to solve this in 49 bytes by doing repeated explicit division (which is also generalized for all powers – replace the desired power minus one into the {3}), but this method is far, far slower, and an explanation of the algorithm it uses is beyond the scope of this Answer:


Try it online!

  • \$\begingroup\$ From my testing (up to length 1024), it seems that it is correct. However, the regex is too slow - it takes a lot of time just to match length 16^4, so it is very hard to verify for large number. But since performance is not required, I'll upvote when I understand your regex. \$\endgroup\$ Feb 24, 2014 at 12:50
  • 1
    \$\begingroup\$ Your regex and Volatility's are awesome. Their speed and brevity amaze me, both of them matching 100000000 in 7.5 seconds on my i7-2600k, much faster than I would have expected a regex to be. My solution here is on a totally different order of magnitude, as it takes 12 seconds to match 50625. But the goal with mine was not speed, but rather, accomplishing the job in minimal code length using a much more limited set of operations. \$\endgroup\$
    – Deadcode
    Feb 24, 2014 at 15:14
  • \$\begingroup\$ Our answers are fast, since they barely do any backtracking. Yours do a lot of backtracking in ((((x+)\5+)\4+)\3+)\2+$. Yours is also amazing in its own way, since I can't even think of how to match a square number without forward-declared backreference. \$\endgroup\$ Feb 24, 2014 at 15:14
  • \$\begingroup\$ By the way, this question is not code-golf, but a puzzle. I don't judge solution by code length. \$\endgroup\$ Feb 24, 2014 at 17:59
  • \$\begingroup\$ Oh. That explains why you used (?:). So should I edit my answer to make the optimized version the primary one? \$\endgroup\$
    – Deadcode
    Feb 24, 2014 at 18:42

Perl / Java / PCRE / .NET, 53 bytes



This regex is compatible with Java, Perl, PCRE and .NET flavors. This regex uses quite a range of features: look-ahead, look-behind and forward-declared back-reference. Forward-declared back-reference kinds of limits the compatibility of this regex to a few engines.


This solution makes use of the following derivation.

By fully expanding the summation, we can prove the following equality:

\sum\limits_{i=1}^n (i+1)^4 - \sum\limits_{i=1}^n i^4 = (n+1)^4 - 1
\sum\limits_{i=1}^n i^4 - \sum\limits_{i=1}^n (i-1)^4 = n^4

Let us combine the summation on the left-hand-side:

\sum\limits_{i=1}^n (4(i+1)^3 - 6(i+1)^2 + 4(i+1) - 1) = (n+1)^4 - 1
\sum\limits_{i=1}^n (4i^3 - 6i^2 + 4i - 1) = n^4

Subtract the 2 equations (top equation minus bottom equation) and then combine the summations on the left-hand-side, then simplify it:

\sum\limits_{i=1}^n (12i^2 + 2) = (n+1)^4 - n^4 - 1

We obtain the difference between consecutive fourth powers as power sum:

(n+1)^4 - n^4 = \sum\limits_{i=1}^n (12i^2 + 2) + 1

This means that the difference between consecutive fourth powers will increase by (12n2 + 2).

To make it easier to think, referring to the difference tree in Volatility's answer:

  • The right-hand-side of the final equation is the 2nd row in the difference tree.
  • The increment (12n2 + 2) is the 3rd row in the difference tree.

Enough mathematics. Back to the solution above:

  • The \2 capturing group maintains a series of odd number to calculate i2 as seen in the equation.

    Precisely speaking, the length of the \2 capturing group will be 0 (unused), 1, 3, 5, 7, ... as the loop iterates.

    (?<=^x)x sets the initial value for the odd number series. The ^ is just there to allow the look-ahead to be satisfied in the first iteration.

    xx\2 adds 2 and advance to the next odd number.

  • The \3 capturing group maintains the square number series for i2.

    Precisely speaking, the length of the \3 capturing group will be 0, 1, 4, 9, ... as the loop iterates.

    ^ in (^|\2\3) sets the initial value for the square number series. And \2\3 adds the odd number to the current square number to advance it to the next square number.

  • The \4 capturing group (outside any look-ahead and actually consume text) matches the whole right-hand-side of the equation we derived above.

    ^x in (^x|\4\3{12}xx) sets the initial value, which is + 1 the right-hand-side of the equation.

    \4\3{12}xx adds the increase in difference (12n2 + 2) using n2 from capturing group \3, and match the difference at the same time.

This arrangement is possible due to the amount of text matched in each iteration is more than or equal to the amount of text needed to execute the look-ahead to construct n2.


.NET, 39 37 bytes


Try it online!

Not only does this outgolf primo's amazing answer, but it runs at very close to exactly the same speed under .NET's regex engine.

This solution uses the .NET-specific feature of balanced groups, where every time a group is captured, it's pushed onto the stack for that particular group, and can then be popped off the same number of times. The popping is done in (?<-1>...) above.

This regex works by:

  1. Asserting that \$N/\2\$ is a perfect square, using a perfect analogy of the ^(\1xx|^x)*$ perfect square regex (which uses a nested backreference), and in so doing, pushing capture group \2 onto the stack the same number of times as \$\sqrt{N/\2}\$. This is done with capture group \$\2=1\$.
  2. Redefining capture group \$\2\$ to actually be \$\sqrt N\$ as found by the first main loop iteration, when we pop all copies of \1 off the stack at the beginning of the second iteration of the main loop. Then we assert \$N/\2\$ to be a perfect square using this new definition of \$\2\$.

So it's basically a double square root, like my two other recent answers to this challenge, but this time using .NET's balanced groups to take the square root. (Also, it doesn't return the fourth root in a capture group, just the square root in \2.)

And like my 41 byte ECMAScript answer, it can be modified to match \$8\$th powers, \$16\$th powers, etc., by changing the 2 in {2} to \$log_2 n\$ to match \$n\$th powers.

^   # tail = N = input number
# Main loop - Execute the following in an lookahead, so that on the second iteration
# we can start again from zero.
    # Capture group \1:
    # Run the following inner loop; for every iteration, push the captured contents
    # onto the balanced group stack for \1. This will later be used as a count.
    # And since this is a loop with a minimum iteration count of zero, regardless of
    # what is done inside, we're guaranteed to be able to match N=0.
        # Evaluate the following in an atomic group, because otherwise the regex engine
        # would backtrack into it, changing the value of \2.
            # Execute this if and only if we're on the first iteration of this inner loop.
            # The atomic group around it prevents the other alternative from being taken.
            # Define \2 to be one of the following two:
                # Pop all copies of \1 off the stack, asserting that at least one
                # was pushed. If this is the first iteration of the main loop, \1
                # has not yet captured anything, and this won't match (and thus will
                # go to the next alternative below). This also clears \1's value,
                # allowing the next iteration of the main loop to start off properly.
                # \2 = 1
            # If \1 has a value (which implies \2 also has a value), then \1 = \1 + \2*2;
            # tail -= \1. On the Kth iteration, this will give us head = K^2 * \2. This
            # uses the fact that (n+1)^2 - n^2 = 2n + 1. The 1 comes from \2's initial
            # value.
    )*      # Loop the above zero or more times
    $       # Assert tail == 0
){2}    # Loop the main loop above exactly twice

Perl / PCRE2 v10.34 or later, 41 40 38 37 35 33 bytes


Try it online! - Perl
Try it on regex101 / Attempt This Online! - PCRE2

This is a port of the .NET version, using group-building (with a nested backreference) instead of a balanced group. Thanks to the use of a branch reset group (?|...) to reset the value of \2 beteween iterations of the main loop, it too can be modified to match \$8\$th powers, \$16\$th powers, etc., by changing the 2 in {2} to \$log_2 n\$ to match \$n\$th powers. Commented version to come.

Perl / PCRE, 41 40 38 37 35 bytes


Try it online! - Perl
Try it online! - PCRE1
Try it online! / Attempt This Online! - PCRE2

PCRE1 and earlier versions of PCRE2 did not support quantifying a lookaround, automatically short-circuiting a loop count of \$2\$ or more to be \$1\$. So this version needs to wrap the lookaround in a dummy group in order to quantify it.

Not that it was necessary – but because this challenge and primo's answer talk about testing up to \$128^4\$, I decided to do a test run on this regex. I tested it on all integers from \$0\$ to \$130^4\$ inclusive (that's all integers in that range, not just \$n^4-1\$, \$n^4\$, and \$n^4+1\$) using RegexMathEngine, and there were no false positives or negatives. It took about 4 days of computing time, single-threaded.

PCRE1 / PCRE2 v10.33 and earlier, 36 34 bytes


Try it online! - PCRE1
Try it online! - PCRE2 v10.33

PCRE1 automatically forces capture groups with nested backreference(s) to be atomic, thus allowing us to save 1 byte by omitting the possessive quantifier. Early versions of PCRE2, like the one still on TIO, had the same behavior.

.NET, 38 36 bytes


Try it online!

This is the Perl / PCRE version backported to .NET, using its feature of recapturing numbered groups by using the number as a name, seen as (?<2>...) above.

Perl / Java / PCRE2 v10.34 or later, 41 39 37 bytes


Try it online! - Perl
Try it online! - Java
Try it on regex101 / Attempt This Online! - PCRE2

Unfortunately, without the branch reset group, it cannot be generalized by changing the {2} to anything higher, because the value of \3 is not reset from iteration to iteration. The only way I can think of to generalize in that way makes it much longer, at 55 53 bytes:


Try it online! - Java

Perl / Java / PCRE2 v10.34 or later / .NET, 40 bytes


Try it online! - Perl
Try it online! - Java
Try it on regex101 / Attempt This Online! - PCRE2
Try it online! - .NET

To make the regex fully general to all four of these engines (ignoring PCRE1, because it's an outdated version of the same engine), we must not use balanced groups, recaptured groups, branch reset groups, or possessive quantifiers.

It is possible shorten the regex, while still supporting this exact set of regex engines, by dropping the pretense of a 2-iteration loop and doing the two stages separately.

  • 2
    \$\begingroup\$ Very nice improvements! \$\endgroup\$
    – primo
    Apr 9, 2021 at 11:41

ECMAScript, 41 bytes


Try it online! - ECMAScript (SpiderMonkey)
Try it online! - ECMAScript (Node.js - faster)
Try it online! - .NET, in ECMAScript emulation mode

This uses a "higher technology" than my older 50 byte ECMAScript answer (which was my very first post on this site), and unlike its algorithm (which works individually on prime factors), does actual division (or multiplication, depending on how you look at it) in a way that works thanks to the Chinese remainder theorem, as explained in this post. The upshot of this is that it returns the \$n\$th root in a capture group when asserting a number is an \$n\$th power, whereas the prime-factoring algorithm is completely unaware of what the root was.

This regex takes the square root twice in a row, asserting each time that the input was a perfect square. The same square-testing regex is used in the second answer in this post. It could be modified to take \$8\$th powers, \$16\$th powers, etc., by changing the 2 in {2} to \$log_2 n\$ to match \$n\$th powers.

^                      # tail = N = input number
        (x(x*)|)       # \2 = potential square root; \3 = \2-1, or unset if \2==0, in
                       #      order to match N=0 using ECMAScript NPCG behavior;
                       # tail = N-\2
            (\2*)\3+$  # if \2*\2 == \2+tail, the first match here must result in \4==0
        (\2*$\4)       # assert \2 divides tail, and \4==0; \5 = tool to make tail = \2
    \5                 # tail = \2
){2}                   # Loop the above exactly 2 times

ECMAScript / Python or better, 43 bytes


This version is NPCG-independent, allowing it to work on a wide variety of regex engines:

Try it online! - ECMAScript (SpiderMonkey)
Try it online! - ECMAScript (Node.js - faster)
Try it online! - Perl
Try it online! - Java
Try it online! - Boost
Try it online! - Python
Try it online! - Python (with regex)
Try it online! - Ruby
Try it online! - PCRE (fastest)
Try it online! - .NET

^                      # tail = N = input number
        (x(x*))        # \2 = potential square root, which must be positive; \3 = \2-1;
                       # tail = N-\2
            (\2*)\3+$  # if \2*\2 == \2+tail, the first match here must result in \4==0
        (\2*$\4)       # assert \2 divides tail, and \4==0; \5 = tool to make tail = \2
    \5                 # tail = \2
){2}                   # Loop the above exactly 2 times
|^$                    # Allow us to match N=0, which can't be matched above

Perl / Java / PCRE / .NET, 35 bytes


This beats primo's solution by 4 bytes while supporting the exact same set of regex engines.

Try it online! - Perl
Try it online! - Java
Try it online! - PCRE1
Try it online! / Attempt This Online! - PCRE2
Try it online! - .NET

It works by first finding two consecutive triangular numbers whose sum is \$n\$ (using the equivalent of (\1x|^x)+ to find the smaller one), so that \$\sqrt n\$ will be the triangular root of the larger triangular number. Then it tries to match that root as itself being a perfect square, using the equivalent of (\1xx|^x)+$.

If it did not need to match \$0^4\$, the regex would be 34 bytes, and if it didn't need to match \$1^4\$ either, it would be 30 bytes.

                   # tail = N = input number
    (              # \1 = a triangular number T_0; tail -= \1;
                   # \2 = triangular root of \1
            \2x    # On iterations after the first, \2 = \2 + 1
            ^x     # On the first iteration,        \2 = 1
        )+         # Iterate the above any nonzero number of times
    # T_1, the next consecutive triangular number after \1, is \1 + \2 + 1.
    # N is a perfect square iff tail == T_1.
    \1             # tail -= \1
        \3xx       # On iterations after the first, \3 = \3 + 2
        x          # On iterations after the first, \3 = 1
        (?=\2$)    # Assert that this is the first iteration, while
                   # simultaneously asserting that N is a perfect square,
                   # because if tail == \2 here, it will have equalled \2+1
                   # before this loop began.
    )+             # Iterate the above any nonzero number of times
    $              # Assert tail == 0
    ^x?$           # Allow us to match N=0 or N=1, which can't be matched above

Alternative 35 bytes:


This avoids the special cases for \$n\in [0,1]\$ at the end, while working around PCRE1's atomic behavior, by hinting that the group 2 loop should only capture \$1\$ x in its initial iteration if there are more xs following it. This way we can get the same behavior as the 32 byte version below, where both \1 and \2 capture an empty string when \$n\in [0,1]\$ – but unlike that version, this happens for \$n=1\$ without any backtracking.

Perl / Java / PCRE2 v10.34 or later / .NET, 32 bytes


This drops 3 bytes at the cost of sacrificing support for PCRE1 and older versions of PCRE2, because they automatically force capture groups with nested backreference(s) to be atomic – which would prevent x? from ever matching \$0\$ instead of \$1\$, blocking \$1^4\$ from being matched.

If it did not need to match \$0^4\$, the regex would be 31 bytes.

Try it online! - Perl
Try it online! - Java
Attempt This Online! - PCRE2 v10.40+
Try it online! - .NET

Perl / Java / PCRE / .NET, 39 bytes


This was a stepping stone from 40 bytes to the 35 byte answer above.
Try it online! - Perl / Java / PCRE1 / PCRE2 v10.33 / PCRE2 v10.40+ / .NET
Alternative 39 bytes, slower in most of the regex engines:


Perl / Java / PCRE2 v10.34 or later / .NET, 38 bytes


This was a stepping stone from 40 bytes to the 32 byte answer above.
Try it online! - Perl / Java / PCRE2 v10.40+ / .NET
Alternative 38 bytes, slower in most of the regex engines:


Perl / Java / PCRE, 39 bytes


Try it online! - Perl
Try it online! - Java
Try it online! - PCRE1
Try it online! / Attempt This Online! - PCRE2

This is the same as the 40 byte regex below, but drops .NET support by using a possessive quantifier, x?+ instead of |^$, to match \$0^4\$. This works because x?+ will always consume 1 x if it can, and will only consume 0 xs if \$\it\text{tail}=0\$, which can happen in two ways:

  • If the input was \$0\$, in which case \1 and \2 will have both captured \$0\$, and the second half of the regex will match.
  • If the input was nonzero, in which case \2 will have captured the entire nonzero input value, making it impossible for the second half of the regex to match, as \2+ won't be able to match with \$\it\text{tail}=0\$.

Perl / Java / PCRE / .NET, 42 40 bytes


Try it online! - Perl
Try it online! - Java
Try it online! - PCRE1
Try it online! / Attempt This Online! - PCRE2
Try it online! - .NET

This uses the equivalent of ^(\1xx|^x)*$ to match a perfect square using a nested backreference (made more complicated by needing to capture that square minus \$1\$), and then uses a square-testing algorithm which works thanks to the Chinese remainder theorem (which only requires ECMAScript or better, and is the reason for needing to capture the square minus \$1\$), to assert that the captured perfect square is the square root of the inputted number. The latter algorithm is explained in this post, and this exact square-testing regex is used in the second answer in this post.

    ^                    # tail = N = input number
    (                    # \1 = the largest perfect square for which the
                         #      subsequent expression matches; tail -= \1
        (                # \2 = \1 - 1
            (            # \3 = nested backreference
                # On the first iteration,   \3 =  1 + 2 = 3;
                # on subsequent iterations, \3 = \3 + 2
            )*           # iterate \3 any number of times (may be zero); \2
                         # becomes the total of all these iterations
        x                # \1 = \2 + 1
    # Assert that N == \1^2
        (\1*)\2+$        # iff \1*\1 == N, the first match here must capture \5=0
    \1*$\5               # assert \1 divides N-\1, and \5==0
    ^$                   # Allow us to match N=0, which can't be matched above

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.