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 x
s 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