Revision 0b140ccd-26f5-4edd-bcd9-c7a69b22f8d8 - Code Golf Stack Exchange
# Regex (ECMAScript+`(?*)`), <s>1169</s> <s>929</s> <s>887</s> <s>853</s> <s>849</s> 840 bytes
*-9 bytes by using the second form of shortened division, where \$A^2 > C \ge A\$*
Regex was never designed to do mathematics. It has no concept of arithmetic. However, when input is taken in the form of [bijective unary](https://en.wikipedia.org/wiki/Unary_numeral_system), as a sequence of identical characters in which the length represents a natural number, it is possible to do a wide range of operations, building up from the simple primitives available, which basically amount to addition, comparison, multiplication by a constant, and modulo. Everything must fit inside the input; it isn't possible to directly operate on numbers larger than that.
In ECMAScript regex, it's especially difficult (and therefore interesting) to do even some of the simplest of operations, because of the limitation that all backrefs captured in a loop are reset to empty at the beginning of each iteration – which makes it impossible to count anything directly. It's nevertheless possible to match prime numbers, powers of N, Nth powers, arbitrary multiplication and exponentiation, Fibonacci numbers, factorial numbers, abundant numbers, and more, much of which is demonstrated in my other answers.
One of the operations that turns out to be far more verbose than the rest is to "calculate an irrational number". I initially discussed this with teukon [back in 2014](https://gist.github.com/Davidebyzero/9735222#gistcomment-1209356). The only known way to do this is to *emulate* operations on numbers larger than the input, and probably the simplest way to do this is by working in a number base chosen based on what can fit into the input.
It wasn't until late 2018 that I finally set about to implementing the theory I had sketched in 2014. Implementing it involved adapting the multiplication algorithm to work with factors of 0, which turned out to golf rather elegantly. (The underlying multiplication algorithm is explained [in this post](https://codegolf.stackexchange.com/questions/110708/an-abundance-of-integers/178952#178952).) The basic algorithm is this:
For input \$N\,ドル we want to calculate \$M=\lfloor{N\over\sqrt2}\rfloor\$. So we want the largest \$M\$ such that \2ドルM^2\le N^2\$.
If we take the "number base" to be \$k=\lceil\sqrt N\rceil\$ or \$\lfloor\sqrt N\rfloor\!+\!1\,ドル all multiplication operations \$m\cdot n\$ on \0ドル\leq m,n<k\$ are guaranteed to fit in the available space.
So if \$N=A k+B\,ドル where \0ドル\leq A,B\lt k\,ドル we can calculate \$N^2\$:
$$N^2=(A k+B)^2=A^2 k^2+2 A B k+B^2$$
We must then do division, modulo, and carry to bring \$A^2\,ドル \2ドル A B\,ドル and \$B^2\$ back into the range of a base \$k\$ "digit". A similar operation is then done to calculate \2ドル M^2\$ iterated over the decreasing consecutive possible values of \$M\,ドル using digit-by-digit comparison to test for \2ドルM^2\le N^2\,ドル until the first \$M\$ is found that passes the test.
So while the basic concept is simple enough, it adds up to a lot of calculations, and the regex is huge! And this is probably the *simplest* calculation of an irrational number that can be done in ECMAScript regex. (It is still unknown whether it's possible to calculate a transcendental number to arbitrary precision in regex.)
This regex uses **molecular lookahead**, a.k.a. non-atomic lookahead, represented as `(?*`...`)`. Without this feature, it would be much harder (or at least much more verbose) to implement.
A choice I made early on, to depart from pure code golf by going for mathematical aesthetics, turned out to be a very interesting. I chose to use \$k=\lceil\sqrt N\rceil\$ because it has the very neat property of making the calculations fit perfectly into \$N\$ if \$N\$ is a perfect square, whereas \$k=\lfloor\sqrt N\rfloor\!+\!1\$ is basically chaotic for all inputs. They both yield the same final outputs, but the former is just cleaner. A few golfs later, this choice ended up net increasing the total length of the regex by **8 bytes**, so I figured it was worth it. (This change is [in the git version history](https://github.com/Davidebyzero/RegexGolf/commit/b005d2f3713900212c0b2451c4912e3c2c1b605b).) But another golf later that day, unbeknownst to me, was actually dependent on that decision! The [skipping of a divisibility check in a division calculation](https://github.com/Davidebyzero/RegexGolf/commit/711a514cd6034ab099ce24870afbe82b09ea9c2a) makes \$N=25\$ return the incorrect output of \$M=11\$ instead of \$M=17\$ if \$k=\lfloor\sqrt N\rfloor\!+\!1\,ドル but works perfectly for all inputs if \$k=\lceil\sqrt N\rceil\$. So the *actual* net change in byte length was zero! It was a purely aesthetic decision for over two years.
At the time I did not understand why that division optimization worked, but [this is now fully explained thanks to H.PWiz](https://codegolf.stackexchange.com/questions/114003/division-and-remainder/222932#222932). The shortened form of division used at the beginning of the calculation of \$M^2\$ gives the correct quotient \$B\$ when \$A+2 < 4B\,ドル where \$C\$ is the dividend and \$A\$ is the divisor. Previously I believed that it was only guaranteed to work when \$A \le B\$.
And now, with the discovery of a second shortened form of division that gives the correct quotient when \$A^2 > C \ge A\,ドル I found an opportunity to use it in this regex. It *only* works when \$k=\lfloor\sqrt N\rfloor\!+\!1\,ドル so now I've switched back to that number base! Currently it's saving 9 bytes, but I haven't gone through the entire regex yet, so there may be more places it can be used.
`(?=(x(x*)).*(?=1円*$)2円+$)(?=(x1円)+(x?(x*)))(?=4円(x(x*?))1円+$)(?=.*(?=(?=4円*$)4円5円+$)(x*?)(?=3円*$)(x?(x*))(?=9円*$)((?=1円+$)1円10円*$|$9円))(?=.*(?=(?=4円*$)(?=6円*$)(?=4円7円+$)6円5円+$|$4円)(x*?)(?=3円*$)(x?(x*))(?=13円*$)((?=1円+$)1円14円*$|$13円))(?=.*(?=12円12円9円$)(x*?)(?=3円*$)(x?(x*))(?=17円*$)((?=1円+$)1円18円*$|$17円))(?*.*?(?=((?=3円*(x?(x*)))21円(x(x*))(?=23円*$)(?=1円*$)1円24円*$)))(?=.*(?=23円*$)(23円24円+$))(?=.*(?=(?=21円*$)21円22円+$)(x*?)(?=3円*$)(x?(x*))(?=27円*$)((?=1円+$)1円28円*$|$27円))(?=.*(?=(?=21円*$)(?=23円*$)(?=21円24円+$)23円22円+$|$21円)(x*?)(?=3円*$)(x?(x*))(?=31円*$)((?=1円+$)1円32円*$|$31円))(?=.*(?=30円30円27円$)(x*?)(?=3円*$)(x?(x*))(?=35円*$)((?=1円+$)1円36円*$|$35円))(?=.*(?=26円26円)(?=3円*(x*))(1円(x)|))(?=.*(?=34円34円40円)(?=3円*(x*))(1円(x)|))(?=(?=(.*)13円13円17円(?=6円*$)6円7円+$)44円(x+|(?=.*(?!16円)41円|(?!.*(?!38円)8円).*(?=16円$)41円$))(25円31円31円35円){2}43円$)20円|xx?\B|`
[Try it on repl.it](https://repl.it/@Davidebyzero/regex-Shift-left-half-a-bit-ECMAScript)
This regex is [on GitHub](https://github.com/Davidebyzero/RegexGolf/blob/master/regex%20for%20dividing%20by%20sqrt2%2C%20with%20molecular%20lookahead.txt) with a [full version history](https://github.com/Davidebyzero/RegexGolf/commits/master/regex%20for%20dividing%20by%20sqrt2%2C%20with%20molecular%20lookahead.txt).
```
# Given an input number N in the domain ^x*,ドル this regex returns floor(N / sqrt(2))
(?=
(x(x*)) # 1円 = will be the square root of the main number, rounded down; 2円 = 1円 - 1
.*(?=1円*$)
2円+$
)
# Step 1: Calculate N*N in base floor(sqrt(N))+1
(?=(x1円)+(x?(x*))) # 3円 = 1円 + 1, the number base to work in; 4円 = N % 3円; 5円 = 4円-1, or 0 if 4円==0
(?=
4円
(x(x*?)) # 6円 = floor(N / 3円); 7円 = 6円-1; Use the second shortened form of division, because we're
1円+$ # guaranteed that 6円 < 3円 thanks to using floor(sqrt(N))+1 as our number base.
)
(?=
.*
(?=
(?=4円*$) # tail = 4円 * 4円
4円5円+$
)
(x*?)(?=3円*$) # 8円 = (4円 * 4円) % 3,円 the base-3円 digit in place 0 of the result for N*N
(x?(x*)) # 9円 = floor((4円 * 4円) / 3円); 10円 = 9円-1, or 0 if 9円==0
(?=9円*$)
(
(?=1円+$)
1円10円*$
|
$9円 # must make a special case for 9円==0, because 1円 is nonzero
)
)
(?=
.*
(?=
(?=4円*$) # tail = 4円 * 6円; must do symmetric multiplication, because 4円 is occasionally 1 larger than 6円
(?=6円*$)
(?=4円7円+$)
6円5円+$
|
$4円 # must make a special case for 4円==0, because 6円 might not be 0
)
(x*?)(?=3円*$) # 12円 = (4円 * 6円) % 3円
(x?(x*)) # 13円 = floor((4円 * 6円) / 3円); 14円 = 13円-1, or 0 if 13円==0
(?=13円*$)
(
(?=1円+$)
1円14円*$
|
$13円 # must make a special case for 13円==0, because 1円 is nonzero
)
)
(?=
.*(?=12円12円9円$) # tail = 2 * 12円 + 9円
(x*?)(?=3円*$) # 16円 = (2 * 12円 + 9円) % 3,円 the base-3円 digit in place 1 of the result for N*N
(x?(x*)) # 17円 = floor((2 * 12円 + 9円) / 3円); 18円 = 17円-1, or 0 if 17円==0
(?=17円*$)
(
(?=1円+$)
1円18円*$
|
$17円 # must make a special case for 17円==0, because 1円 is nonzero
)
) # {6円*6円 + 2*13円 + 17円} = the base-3円 digit in place 2 of the result for N*N, which is allowed to exceed 3円 and will always do so;
# Note that it will be equal to N iff N is a perfect square, because of the choice of number base.
# Step 2: Find the largest M such that 2*M*M is not greater than N*N
# Step 2a: Calculate M*M in base 3円
(?*
.*? # Determine value of M with backtracking, starting with largest values first
(?=
( # 20円 = M
(?=3円*(x?(x*)))21円 # 21円 = M % 3円; 22円 = 21円-1, or 0 if 21円==0
(x(x*)) # 23円 = floor(M / 3円); 24円 = 23円-1
(?=23円*$)
(?=1円*$)
1円24円*$
)
)
)
(?=
.*
(?=23円*$)
(23円24円+$) # 25円 = 23円 * 23円
)
(?=
.*
(?=
(?=21円*$) # tail = 21円 * 21円
21円22円+$
)
(x*?)(?=3円*$) # 26円 = (21円 * 21円) % 3,円 the base-3円 digit in place 0 of the result for M*M
(x?(x*)) # 27円 = floor((21円 * 21円) / 3円); 28円 = 27円-1, or 0 if 27円==0
(?=27円*$)
(
(?=1円+$)
1円28円*$
|
$27円 # must make a special case for 27円==0, because 1円 is nonzero
)
)
(?=
.*
(?=
(?=21円*$) # tail = 21円 * 23円; must do symmetric multiplication, because 21円 is occasionally 1 larger than 23円
(?=23円*$)
(?=21円24円+$)
23円22円+$
|
$21円 # must make a special case for 21円==0, because 23円 might not be 0
)
(x*?)(?=3円*$) # 30円 = (21円 * 23円) % 3円
(x?(x*)) # 31円 = floor((21円 * 23円) / 3円); 32円 = 31円-1, or 0 if 31円==0
(?=31円*$)
(
(?=1円+$)
1円32円*$
|
$31円 # must make a special case for 31円==0, because 1円 is nonzero
)
)
(?=
.*(?=30円30円27円$) # tail = 2 * 30円 + 27円
(x*?)(?=3円*$) # 34円 = (2 * 30円 + 27円) % 3,円 the base-3円 digit in place 1 of the result for M*M
(x?(x*)) # 35円 = floor((2 * 30円 + 27円) / 3円); 36円 = 35円-1, or 0 if 35円==0
(?=35円*$)
(
(?=1円+$)
1円36円*$
|
$35円 # must make a special case for 35円==0, because 1円 is nonzero
)
) # {25円 + 2*31円 + 35円} = the base-3円 digit in place 2 of the result for M*M, which is allowed to exceed 3円 and will always do so
# Step 2b: Calculate 2*M*M in base 3円
(?=
.*
(?=26円26円) # tail = 2*26円
(?=3円*(x*)) # 38円 = (2*26円) % 3,円 the base-3円 digit in place 0 of the result for 2*M*M
(1円(x)|) # 40円 = floor((2*26円) / 3円) == +1 carry if {2*26円} does not fit in a base 3円 digit
)
(?=
.*
(?=34円34円40円) # tail = 2*34円 + 40円
(?=3円*(x*)) # 41円 = (2*34円 + 40円) % 3,円 the base-3円 digit in place 1 of the result for 2*M*M
(1円(x)|) # 43円 = floor((2*34円 + 40円) / 3円) == +1 carry if {2*34円 + 40円} does not fit in a base 3円 digit
) # 2*(25円 + 2*31円 + 35円) + 43円 = the base-3円 digit in place 2 of the result for 2*M*M, which is allowed to exceed 3円 and will always do so
# Step 2c: Require that 2*M*M <= N*N
(?=
(?=
(.*) # 44円
13円13円17円
(?=6円*$) # tail = 6円 * 6円
6円7円+$
)
44円 # tail = {6円*6円 + 2*13円 + 17円}; we can do this unconditionally because our digits in place 2 are always greater than those in places 0..1
(
x+
|
(?=
.*(?!16円)41円 # 41円 < 16円
|
(?!.*(?!38円)8円) # 38円 <= 8円
.*(?=16円$)41円$ # 41円 == 16円
)
)
(25円31円31円35円){2}43円$ # 2*(25円 + 2*31円 + 35円) + 43円
)
20円
|xx?\B| # handle inputs in the domain ^x{0,4}$
```
---
# Regex (ECMAScript 2018), <s>861</s> 852 bytes
This is a direct port of the <s>849</s> 840 byte molecular lookahead version, using variable length lookbehind.
`(?=(x(x*)).*(?=1円*$)2円+$)(?=(x1円)+(x?(x*)))(?=4円(x(x*?))1円+$)(?=.*(?=(?=4円*$)4円5円+$)(x*?)(?=3円*$)(x?(x*))(?=9円*$)((?=1円+$)1円10円*$|$9円))(?=.*(?=(?=4円*$)(?=6円*$)(?=4円7円+$)6円5円+$|$4円)(x*?)(?=3円*$)(x?(x*))(?=13円*$)((?=1円+$)1円14円*$|$13円))(?=.*(?=12円12円9円$)(x*?)(?=3円*$)(x?(x*))(?=17円*$)((?=1円+$)1円18円*$|$17円))(?=.*?(?=((?=3円*(x?(x*)))21円(x(x*))(?=23円*$)(?=1円*$)1円24円*$))(?<=(?=(?=.*(?=23円*$)(23円24円+$))(?=.*(?=(?=21円*$)21円22円+$)(x*?)(?=3円*$)(x?(x*))(?=27円*$)((?=1円+$)1円28円*$|$27円))(?=.*(?=(?=21円*$)(?=23円*$)(?=21円24円+$)23円22円+$|$21円)(x*?)(?=3円*$)(x?(x*))(?=31円*$)((?=1円+$)1円32円*$|$31円))(?=.*(?=30円30円27円$)(x*?)(?=3円*$)(x?(x*))(?=35円*$)((?=1円+$)1円36円*$|$35円))(?=.*(?=26円26円)(?=3円*(x*))(1円(x)|))(?=.*(?=34円34円40円)(?=3円*(x*))(1円(x)|))(?=(?=(.*)13円13円17円(?=6円*$)6円7円+$)44円(x+|(?=.*(?!16円)41円|(?!.*(?!38円)8円).*(?=16円$)41円$))(25円31円31円35円){2}43円$))^.*))20円|xx?\B|`
[Try it online!](https://tio.run/##fVTBbtswDL33K9IgqKW4MSzZTpq6boABO/TSw3acNtRIVEeDq3iy2hqIc90H7BP3IxkpJ1uatQUISCIf3yNpWd/zp7yeG1XZkV4t5La2ubFykYWpyT7J4mNTkc/WKF0EJn@@25JZRhrSDCkNhrAXbDiggvsD6gKCUZ80MxdHj4gdeEapYB3GZbkIJsYiQTci0BcN8dCl43mKZ6cCKMEEC4eDdiCm9D8mXMe7NRYThI@RG9Dx2/wsOhaInQCL/ikIxtGm75TJJsc0Fx3NZEczw0q7zL/TEZztBokBHu2Kd/NkgmNT4LjKuia7UjoULBD3By@nwLsvAan8vZHy41p5VyufvEL3ojKkRlUnz91oOXtbKGJHQhF3QhE7mG0UovHJOwVHyTHPuONJDnj4GIzuJ4yZAqZL20OpGC0O30KhBUMQiJxN9jcK7pG7TjFcZb/d0Z0KNgYXg/Npd44uqLjY/xNjxDP8QIIn0LGzhK75RsQRuL@BEMwxbJtmJj6027ugLtVcEnY@gumkRv54VEYSz8h8USotPRrMYW/ljbbS3OcAXStdPdrLyqzmsq6D2i6U3tBgpYnnMs7L7HpdZGVQV6WyxBt5NFX3hOisCEqpC7uk17xtVX2b3xKVVbmpkZ0UX8KvlO4D8jCgr9mMXWKY2qVZPfdv9FNeqkXP5LqQl72@X6b3K0NSdZXJVPk@BcGHrN/0AyMrKJ8oGjzkdr4khtL17qE5OzvoYfVog2ejLPQuNFS8f4xY@ipI@V7v989fPc9/gLL3faWbDd2GIxaGJzwJTxJYYe824R8 "JavaScript (Node.js) – Try It Online")
This regex is [on GitHub](https://github.com/Davidebyzero/RegexGolf/blob/master/regex%20for%20dividing%20by%20sqrt2%2C%20with%20variable-length%20lookbehind.txt).
```
# Given an input number N in the domain ^x*,ドル this regex returns floor(N / sqrt(2))
(?=
(x(x*)) # 1円 = will be the square root of the main number, rounded down; 2円 = 1円 - 1
.*(?=1円*$)
2円+$
)
# Step 1: Calculate N*N in base floor(sqrt(N))+1
(?=(x1円)+(x?(x*))) # 3円 = 1円 + 1, the number base to work in; 4円 = N % 3円; 5円 = 4円-1, or 0 if 4円==0
(?=
4円
(x(x*?)) # 6円 = floor(N / 3円); 7円 = 6円-1; Use the second shortened form of division, because we're
1円+$ # guaranteed that 6円 < 3円 thanks to using floor(sqrt(N))+1 as our number base.
)
(?=
.*
(?=
(?=4円*$) # tail = 4円 * 4円
4円5円+$
)
(x*?)(?=3円*$) # 8円 = (4円 * 4円) % 3,円 the base-3円 digit in place 0 of the result for N*N
(x?(x*)) # 9円 = floor((4円 * 4円) / 3円); 10円 = 9円-1, or 0 if 9円==0
(?=9円*$)
(
(?=1円+$)
1円10円*$
|
$9円 # must make a special case for 9円==0, because 1円 is nonzero
)
)
(?=
.*
(?=
(?=4円*$) # tail = 4円 * 6円; must do symmetric multiplication, because 4円 is occasionally 1 larger than 6円
(?=6円*$)
(?=4円7円+$)
6円5円+$
|
$4円 # must make a special case for 4円==0, because 6円 might not be 0
)
(x*?)(?=3円*$) # 12円 = (4円 * 6円) % 3円
(x?(x*)) # 13円 = floor((4円 * 6円) / 3円); 14円 = 13円-1, or 0 if 13円==0
(?=13円*$)
(
(?=1円+$)
1円14円*$
|
$13円 # must make a special case for 13円==0, because 1円 is nonzero
)
)
(?=
.*(?=12円12円9円$) # tail = 2 * 12円 + 9円
(x*?)(?=3円*$) # 16円 = (2 * 12円 + 9円) % 3,円 the base-3円 digit in place 1 of the result for N*N
(x?(x*)) # 17円 = floor((2 * 12円 + 9円) / 3円); 18円 = 17円-1, or 0 if 17円==0
(?=17円*$)
(
(?=1円+$)
1円18円*$
|
$17円 # must make a special case for 17円==0, because 1円 is nonzero
)
) # {6円*6円 + 2*13円 + 17円} = the base-3円 digit in place 2 of the result for N*N, which is allowed to exceed 3円 and will always do so;
# Note that it will be equal to N iff N is a perfect square, because of the choice of number base.
# Step 2: Find the largest M such that 2*M*M is not greater than N*N
# Step 2a: Calculate M*M in base 3円
(?=
.*? # Determine value of M with backtracking, starting with largest values first
(?=
( # 20円 = M
(?=3円*(x?(x*)))21円 # 21円 = M % 3円; 22円 = 21円-1, or 0 if 21円==0
(x(x*)) # 23円 = floor(M / 3円); 24円 = 23円-1
(?=23円*$)
(?=1円*$)
1円24円*$
)
)
(?<=
(?=
(?=
.*
(?=23円*$)
(23円24円+$) # 25円 = 23円 * 23円
)
(?=
.*
(?=
(?=21円*$) # tail = 21円 * 21円
21円22円+$
)
(x*?)(?=3円*$) # 26円 = (21円 * 21円) % 3,円 the base-3円 digit in place 0 of the result for M*M
(x?(x*)) # 27円 = floor((21円 * 21円) / 3円); 28円 = 27円-1, or 0 if 27円==0
(?=27円*$)
(
(?=1円+$)
1円28円*$
|
$27円 # must make a special case for 27円==0, because 1円 is nonzero
)
)
(?=
.*
(?=
(?=21円*$) # tail = 21円 * 23円; must do symmetric multiplication, because 21円 is occasionally 1 larger than 23円
(?=23円*$)
(?=21円24円+$)
23円22円+$
|
$21円 # must make a special case for 21円==0, because 23円 might not be 0
)
(x*?)(?=3円*$) # 30円 = (21円 * 23円) % 3円
(x?(x*)) # 31円 = floor((21円 * 23円) / 3円); 32円 = 31円-1, or 0 if 31円==0
(?=31円*$)
(
(?=1円+$)
1円32円*$
|
$31円 # must make a special case for 31円==0, because 1円 is nonzero
)
)
(?=
.*(?=30円30円27円$) # tail = 2 * 30円 + 27円
(x*?)(?=3円*$) # 34円 = (2 * 30円 + 27円) % 3,円 the base-3円 digit in place 1 of the result for M*M
(x?(x*)) # 35円 = floor((2 * 30円 + 27円) / 3円); 36円 = 35円-1, or 0 if 35円==0
(?=35円*$)
(
(?=1円+$)
1円36円*$
|
$35円 # must make a special case for 35円==0, because 1円 is nonzero
)
) # {25円 + 2*31円 + 35円} = the base-3円 digit in place 2 of the result for M*M, which is allowed to exceed 3円 and will always do so
# Step 2b: Calculate 2*M*M in base 3円
(?=
.*
(?=26円26円) # tail = 2*26円
(?=3円*(x*)) # 38円 = (2*26円) % 3,円 the base-3円 digit in place 0 of the result for 2*M*M
(1円(x)|) # 40円 = floor((2*26円) / 3円) == +1 carry if {2*26円} does not fit in a base 3円 digit
)
(?=
.*
(?=34円34円40円) # tail = 2*34円 + 40円
(?=3円*(x*)) # 41円 = (2*34円 + 40円) % 3,円 the base-3円 digit in place 1 of the result for 2*M*M
(1円(x)|) # 43円 = floor((2*34円 + 40円) / 3円) == +1 carry if {2*34円 + 40円} does not fit in a base 3円 digit
) # 2*(25円 + 2*31円 + 35円) + 43円 = the base-3円 digit in place 2 of the result for 2*M*M, which is allowed to exceed 3円 and will always do so
# Step 2c: Require that 2*M*M <= N*N
(?=
(?=
(.*) # 44円
13円13円17円
(?=6円*$) # tail = 6円 * 6円
6円7円+$
)
44円 # tail = {6円*6円 + 2*13円 + 17円}; we can do this unconditionally because our digits in place 2 are always greater than those in places 0..1
(
x+
|
(?=
.*(?!16円)41円 # 41円 < 16円
|
(?!.*(?!38円)8円) # 38円 <= 8円
.*(?=16円$)41円$ # 41円 == 16円
)
)
(25円31円31円35円){2}43円$ # 2*(25円 + 2*31円 + 35円) + 43円
)
)
^.*
)
)
20円
|xx?\B| # handle inputs in the domain ^x{0,4}$
```
---
# Regex (ECMAScript)
I have not yet ported this algorithm to basic ECMAScript. One way to do it would be to use \$k=\lceil\sqrt[\uproot{1}3]N\rceil\$ as the number base, and calculate:
$$N^2=(A k^2+B k+C)^2=A^2 k^4 + 2 A B k^3 + (2 A C + B^2)k^2 + 2 B C k + C^2$$
Another way would be to stick with \$k=\lceil\sqrt N\rceil\,ドル capture \$M\$ encoded into two or more backrefs, and emulate the existing calculations within the smaller available space. I'm not sure which way would be more concise. Either way, I expect the regex would roughly double in length.