Retina / .NET Regex, 43 bytes
(?=((2円x+?|^x)(?<=(?=2円+$)^.*))+)(2円x+)3円+$
Try it online! - C# (.NET Core)
Try it online! - Retina
This is 2 bytes shorter than Martin Ender's answer. I've posted this as a separate answer because its structure is quite different, and I wanted to include an explanation and ports to other regex flavors.
It works by first adding up as many proper divisors of N as it can, in strict order from smallest to largest, while having a sum not greater than N. Then it checks if there exists a larger proper divisor than the last one added to the sum; if there does, N is an abundant number.
# For the purpose of these comments, the input number will be referred to as N.
# No anchor needed, because 2円 cannot be captured if
# matching is started anywhere besides the beginning.
(?=
( # Add up all values of 2円 until there is no more room in
# N to keep going
(2円x+?|^x) # 2円 = the smallest value greater than the previous value
# of 2円 which satisfies the following condition; if we're
# at the beginning, 2円 = 1
(?<= # Lookbehind - evaluated from right to left
(?=2円+$) # Assert that N is divisible by 2円
^.* # Jump to the beginning of the input string, then execute
# the above lookahead
)
)+
)
(2円x+) # Match if there exists another proper divisor of N, 3,円
3円+$ # such that 3円 is greater than the last value of 2円. If
# there does, that means there was insufficient room in N
# to add up all of its proper divisors, and N is abundant.
PCRE2 Regex, 49 bytes
This is a direct port of the .NET regex, emulating variable-length lookbehind using a recursive subroutine call.
(?=((2円x+?|^x)((?<=(?=^2円+$|(?3)).)))+)(2円x+)4円+$
(?=
(
(2円x+?|^x)
((?<= # (?3) calls this
(?= # Circumvent the constant-width limitation of lookbehinds
# in PCRE by using a lookahead inside the lookbehind
^2円+$ # This is the payload of the emulated variable-length
# lookbehind, same as the one in the .NET regex
|
(?3) # Recursive call - this is the only alternative that can
# match until we reach the beginning of the string
)
. # Go back one character at a time, trying the above
# lookahead for a match each time
))
)+
)
(2円x+)
4円+$
PCRE1 Regex, 58 bytes
Porting the PCRE2 regex to PCRE1 requires working around some bugs:
(?=((?=(3円|^))(2円x+?)((?<=(?=z|^3円+$|(?4)).)))+)(3円x+)5円+$
The (2円x+?|^x) had to be changed to (?=(3円|^))(2円x+?), copying 3円 into 2円 and 2円 into 3円 (emulating a nested backref using a forward backref), because using a backreference inside its own group forces that group to be atomic in PCRE1. And a fake always-false alternative z had to be added to the recursive subroutine to prevent the error message "recursive call could loop indefinitely".
Try it on regex101
Try it online! (uses an old version of PCRE2, and is buggy starting at 836)
Retina / .NET Regex, 44 bytes
^(?!((?<=(?=(?(3円+$)((?>2円?)3円)))(^x*))x)*$)
Try it online! - C# (.NET Core)
Try it online! - Retina
^(?!(x(?=(x*$)(?<=(?(^2円+)(2円(?>3円?))))))*$)
Try it online! - C# (.NET Core)
Try it online! - Retina
This is based on Martin Ender's answer, but saving 1 byte by testing zero as a potential divisor of \$n\$ (it never will be, so this is harmless), thus skipping the need to explicitly exclude \$n\$ itself as a divisor. Another upshot of this is that we can extend the valid domain from ^\x+$ to ^\x*$, giving the correct answer (non-match, i.e. false) for an input of zero.
I have included versions with both smallest-to-largest and largest-to-smallest divisor summing order. The length for both is 44 bytes. Only the largest-to-smallest version is commented below, because it's simpler to explain, and I already commented the original 45 byte smallest-to-largest version in my ECMAScript answer.
^(?! # Attempt to add up all the divisors. Since this is a regex and we
# can only work within the available space of the input, that means
# if the sum of the divisors is greater than N, the attempt to add
# all the divisors will fail at some point, causing this negative
# lookahead to succeed, showing that N is an abundant number.
(x # Cycle through all positive values of tail that are less than N,
# testing each one to see if it is a divisor of N. Start at N-1.
(?= # Do the below operations in a lookahead, so that upon popping back
# out of it our position will remaing the same as it is here.
(x*$) # 2円 = tail, a potential divisor; go to end to that the following
# lookbehind can operate on N as a whole.
(?<= # Switch to right-to-left evaluation so that we can operate both
# on N and the potential divisor 2円. This requires variable-length
# lookbehind, a .NET feature. Please read these comments in the
# order indicated, from [Step 1] to [Step 4].
(?(^2円+) # [Step 1] If 2円 is a divisor of N, then...
( # [Step 2] Add it to 3,円 the running total sum of divisors:
# 3円 = 3円 + 2円
2円 # [Step 4] Iff we run out of space here, i.e. iff the sum would
# exceed N at this point, the match will fail, making the
# negative lookahead succeed, showing that we have an
# abundant number.
(?>3円?) # [Step 3] Since 3円 is a nested backref, it will fail to match on
# the first iteration. The "?" accounts for this, making
# it add zero to itself on the first iteration. This must
# be done before adding 2,円 to ensure there is enough room
# for the "?" not to cause the match to become zero-length
# even if 3円 has a value.
)
)
)
)
)* # By using "*" instead of "+" here, we can avoid categorizing zero
# as an abundant number.
$ # We can only reach this point if all proper divisors of N, all the
# way down to 2円 = 1, been successfully summed into 3,円 which would
# mean N is not an abundant number.
)
Regex (PCRE2), 73 bytes
This is a direct port of the 44 byte .NET regex (based on Martin Ender's regex). It doesn't port well to PCRE, because it changes the value of a capture group inside the lookbehind – but upon the return of any subroutine in PCRE, all capture groups are reset to the values they had upon entering the subroutine. So the only way to port it is to change the main loop from iteration into recursion, resulting in a large and very slow regex:
^(?!(x(?=(x*$)((?<=(?=^(?(?=2円+$)(?=(4円?+2円))).*(?=2円$)(?1)|(?3)).)))|$))
- 12.9k
- 2
- 71
- 55