Skip to main content
Fix a comment and improve the explanation; remove obsolete versions
Source Link
Deadcode
  • 11.9k
  • 1
  • 66
  • 52

It works by first finding two consecutive triangular numbers whose sum is the input number \$n\$ (using the equivalent of (\1x|^x\2x|^x)+ to find the smaller one), soimplying that \$\sqrt n\$ will be the triangular root of the larger triangular number. Then it tries to match that root as itself being\$n\$ is a perfect square, using (i.e. \$\sqrt n \in \mathbb{N}\$). With \2 and \2\$+1\$ then being the equivalent oftwo consecutive triangular roots, (\1xx|^x)+$\2\$+1=\sqrt n\$.

Then it tries to match \$\sqrt n\$ as itself being a perfect square (i.e. \$\sqrt[4]n \in \mathbb{N}\$), using the equivalent of (\3xx|^x)+$ (using a different method than ^ to distinguish the first iteration, being in the middle of the string at that point).

                   # 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 at this point.
    \1             # tail -= \1
                   # Now iff N is a perfect square, tail == \2 + 1
    (
        \3xx       # On iterations after the first, \3 = \3 + 22; tail -= \3
    |
        x          # On iterations after the first iteration, \3 = 1; tail -= 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

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


Perl / Java / PCRE / .NET, 39 bytes

^(?=((\2x|^x)*)\1(\2?x)?)(\4\3\3|^\3)*$

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:

^(\1\4\4|^(?=((\3x|^x)*)\2(\3?x)$)\4)*$

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

^(\1\4\4|(?=((\3x|^x?)+)\2(\3x)$)\4)*$

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:

(?=((\2x|^x?)+)\1(\2x)?)(\4\3\3|^\3)*$

Perl / Java / PCRE, 39 bytes

^((((\3|^x)xx)*)x?+)(?=(\1*)\2+$)\1*$\5

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

^((((\3|^x)xx)*)x)(?=(\1*)\2+$)\1*$\5|^$

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
                (\3|^x)
                xx
            )*           # 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

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)+$.

                   # 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

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


Perl / Java / PCRE / .NET, 39 bytes

^(?=((\2x|^x)*)\1(\2?x)?)(\4\3\3|^\3)*$

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:

^(\1\4\4|^(?=((\3x|^x)*)\2(\3?x)$)\4)*$

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

^(\1\4\4|(?=((\3x|^x?)+)\2(\3x)$)\4)*$

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:

(?=((\2x|^x?)+)\1(\2x)?)(\4\3\3|^\3)*$

Perl / Java / PCRE, 39 bytes

^((((\3|^x)xx)*)x?+)(?=(\1*)\2+$)\1*$\5

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

^((((\3|^x)xx)*)x)(?=(\1*)\2+$)\1*$\5|^$

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
                (\3|^x)
                xx
            )*           # 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

It works by first finding two consecutive triangular numbers whose sum is the input number \$n\$ (using (\2x|^x)+ to find the smaller one), implying that \$n\$ is a perfect square (i.e. \$\sqrt n \in \mathbb{N}\$). With \2 and \2\$+1\$ then being the two consecutive triangular roots, \2\$+1=\sqrt n\$.

Then it tries to match \$\sqrt n\$ as itself being a perfect square (i.e. \$\sqrt[4]n \in \mathbb{N}\$), using the equivalent of (\3xx|^x)+$ (using a different method than ^ to distinguish the first iteration, being in the middle of the string at that point).

                   # 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 at this point.
    \1             # tail -= \1
                   # Now iff N is a perfect square, tail == \2 + 1
    (
        \3xx       # On iterations after the first, \3 = \3 + 2; tail -= \3
    |
        x          # On the first iteration, \3 = 1; tail -= 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

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

add alternative 35 byter
Source Link
Deadcode
  • 11.9k
  • 1
  • 66
  • 52

Alternative 35 bytes:

((\2x|^x\B|^)+)\1(\3xx|x?(?=\2$))+$

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.

Alternative 35 bytes:

((\2x|^x\B|^)+)\1(\3xx|x?(?=\2$))+$

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.

add intermediate 39 and 38 byte versions that I constructed before arriving at 35 and 32 bytes
Source Link
Deadcode
  • 11.9k
  • 1
  • 66
  • 52

Perl / Java / PCRE / .NET, 39 bytes

^(?=((\2x|^x)*)\1(\2?x)?)(\4\3\3|^\3)*$

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:

^(\1\4\4|^(?=((\3x|^x)*)\2(\3?x)$)\4)*$

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

^(\1\4\4|(?=((\3x|^x?)+)\2(\3x)$)\4)*$

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:

(?=((\2x|^x?)+)\1(\2x)?)(\4\3\3|^\3)*$


Perl / Java / PCRE / .NET, 39 bytes

^(?=((\2x|^x)*)\1(\2?x)?)(\4\3\3|^\3)*$

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:

^(\1\4\4|^(?=((\3x|^x)*)\2(\3?x)$)\4)*$

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

^(\1\4\4|(?=((\3x|^x?)+)\2(\3x)$)\4)*$

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:

(?=((\2x|^x?)+)\1(\2x)?)(\4\3\3|^\3)*$

-1 byte
Source Link
Deadcode
  • 11.9k
  • 1
  • 66
  • 52
Loading
add 33 byte version
Source Link
Deadcode
  • 11.9k
  • 1
  • 66
  • 52
Loading
-5 bytes, finally beating primo's solution in the exact same set of regex engines
Source Link
Deadcode
  • 11.9k
  • 1
  • 66
  • 52
Loading
improve explanation of 39 byte version
Source Link
Deadcode
  • 11.9k
  • 1
  • 66
  • 52
Loading
fix PCRE1 harness testing range to be consistent with the PCRE2 ones; add ATO harnesses for PCRE2
Source Link
Deadcode
  • 11.9k
  • 1
  • 66
  • 52
Loading
add PCRE1 test harnesses
Source Link
Deadcode
  • 11.9k
  • 1
  • 66
  • 52
Loading
-1 byte sacrificing .NET support
Source Link
Deadcode
  • 11.9k
  • 1
  • 66
  • 52
Loading
-2 bytes, and slight rewording of explanation
Source Link
Deadcode
  • 11.9k
  • 1
  • 66
  • 52
Loading
[Edit removed during grace period]
Source Link
Deadcode
  • 11.9k
  • 1
  • 66
  • 52
Loading
oops, don't need the "Regex (...)" in this question
Source Link
Deadcode
  • 11.9k
  • 1
  • 66
  • 52
Loading
Source Link
Deadcode
  • 11.9k
  • 1
  • 66
  • 52
Loading