Regex (ECMAScript), 1085 855 597 536 511 508 504 bytes
Matching abundant numbers in ECMAScript regex is an entirely different beast than doing so in practically any other regex flavor. The lack of forward/nested backreferences or recursion means that it is impossible to directly count or keep a running total of anything. The lack of lookbehind makes it often a challenge even to have enough space to work in.
Many problems must be approached from an entirely different perspective, and you'll be wondering if they're solvable at all. It forces you to cast a much wider net in finding which mathematical properties of the numbers you're working with might be able to be used to make a particular problem solvable.
Back in March-April 2014 I constructed a solution to this problem in ECMAScript regex. At first I had every reason to suspect the problem was completely impossible, but then the mathematician teukon sketched an idea that made an encouraging case for making it look solvable after all – but he made it clear he had no intention of constructing the regex (he had competed/cooperated with my on constructing/golfing previous regexes, but reached his limit by this point and was content to restrict his further contributions to theorizing).
Solving unary mathematical problems in ECMAScript regex has been a fascinating journey for me, so in the past I put spoiler warnings in this post and others like it – in case others, especially those with an interest in number theory, wanted to take a crack at independently solving things like generalized multiplication. I am now removing the spoiler warnings though; they did not prove to be constructive.
Before posting my ECMAScript regex, I thought it would be interesting to analyze Martin Ender's .NET pure regex solution, ^(?!(1(?<=(?=(?(\3+$)((?>\2?)\3)))^(1+)))*1$). It turns out to be very straightforward to understand that regex, and it is elegant in its simplicity. To demonstrate the contrast between our solutions, here is a commented and pretty-printed (but unmodified) version of his regex:
# For the purpose of these comments, the input number will be referred to as N.
^(?! # 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.
(1 # Cycle through all values of tail that are less than N, testing
# each one to see if it is a divisor of N.
(?<= # Temporarily go back to the start so we can directly operate both
# on N and the potential divisor. This requires variable-length
# lookbehind, a .NET feature – even though this special case of
# going back to the start, if done left-to-right, would actually be
# very easy to implement even in a regex flavour that has no
# lookbehind to begin with. But .NET evaluates lookbehinds right
# to left, so please read these comments in the order indicated,
# from [Step 1] to [Step 7]. The comment applying to entering the
# lookahead group, [Step 2], is shown on its closing parenthesis.
(?= # [Step 3] Since we're now in a lookahead, evaluation is left to
# right.
(?(\3+$) # [Step 4] If \3 is a divisor of N, then...
( # [Step 5] Add it to \2, the running total sum of divisors:
# \2 = \2 + \3
(?>\2?) # [Step 6] Since \2 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 \3, to ensure there is enough room
# for the "?" not to cause the match to become zero-length
# even if \2 has a value.
\3 # [Step 7] 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.
)
)
) # [Step 2] Enter a lookahead that is anchored to the start due to
# having a "^" immediately to its right. The regex would
# still work if the "^" were moved to the left of the
# lookahead, but would be slightly slower, because the
# engine would do some spurious matching before hitting
# the "^" and backtracking.
^(1+) # [Step 1] \3 = number to test for being a potential divisor – its
# right-side-end is at the point where the lookbehind
# started, and thus \3 cycles through all values from
# 1 to N-1.
)
)*1$ # Exclude N itself from being considered as a potential divisor,
# because if we included it, the test for proper abundance would be
# the sum of divisors exceeding 2*N. We don't have enough space for
# that, so instead what would happen if we did not exclude N as a
# divisor would be testing for "half-abundance", i.e. the sum of
# all divisors other than N exceeding N/2. By excluding N as a
# divisor we can let our threshold for abundance be the sum of
# divisors exceeding N.
)
Try the .NET regex online
Now, back to my ECMAScript regex. First, here it is in raw, whitespace-and-comment-free format:
^(?=(((?=(xx+?)\3+$)(x+)\4*(?=\4$))+(?!\3+$)(?=(xx(x*?))\5*$)x)(x+))(?=\1(x(x*))(?=\8*$)\6\9+$)(?=(.*)((?=\8*$)\5\9+$))(?=(x*?)(?=(x\11)+$)(?=\12\10|(x))(x(x*))(?=\15*$)(?=\11+$)\11\16+$)(?=(x(x*))(?=\17*$)\7\18+$)((?=(x*?(?=\17+$)(?=\17+?(?=((xx(x*))(?=\18+$)\22*$))(x+).*(?=\17$)\24*(?=\24$)(?!(xx+)\25*(?!\22+$)\25$)\22+$)((?=(x\7)+$)\15{2}\14|)))(?=.*(?=\24)x(x(x*))(?=\28*$)\23\29*$)(?=.*(x((?=\28*$)\22\29+$)))(.*(?!\30)\20|(?=.*?(?!x\20)(?=\30*$)(x(x*))(?=\33*$)(?=\31+$)\31\34+$).*(?=\33\21$)))+$
(change \14 to \14? for compatibility with PCRE, .NET, and practically every other regex flavour that's not ECMAScript)
Try it online!
Try it online! (faster, 537 byte version of the regex)
And now a brief summary of the story behind it.
At first it was very non-obvious, to me at least, that it was even possible to match primes in the general case. And after solving that, the same applied to powers of 2. And then powers of composite numbers. And then perfect squares. And even after solving that, doing generalized multiplication seemed impossible at first.
In an ECMAScript loop, you can only keep track of one changing number; that number cannot exceed the input, and has to decrease at every step. My first working regex for matching correct multiplication statements A*B=C was 913 bytes, and worked by factoring A, B, and C into their prime powers – for each prime factor, repeatedly divide the pair of prime power factors of A and C by their prime base until the one corresponding to A reaches 1; the one corresponding to C is then compared to the prime power factor of B. These two powers of the same prime were "multiplexed" into a single number by adding them together; this would always be unambiguously separable on each subsequent iteration of the loop, for the same reason that positional numeral systems work.
We got multiplication down to 50 bytes using a completely different algorithm (which teukon and I were able to arrive at independently, though it took him only a few hours and he went straight to it, whereas it took me a couple days even after it was brought to my attention that a short method existed): for A≥B, A*B=C if and only if C is the smallest number which satisfies C≡0 mod A and C≡B mod A-1. (Conveniently, the exception of A=1 needs no special handling in regex, where 0%0=0 yields a match.) I just can't get over how neat it is that such an elegant way of doing multiplication exists in such a minimal regex flavour. (And the requirement of A≥B can be replaced with a requirement that A and B are prime powers of the same power. For the case of A≥B, this can be proven using the Chinese remainder theorem.) See this post for a more in-depth explanation.
If it had turned out that there was no simpler algorithm for multiplication, the abundant number regex would probably be on the order of ten thousand bytes or so (even taking into account that I golfed the 913 byte algorithm down to 651 bytes). It does lots of multiplication and division, and ECMAScript regex has no subroutines.
I started working on the abundant number problem tangentially in 23 March 2014, by constructing a solution for what seemed at the time to be a sub-problem of this: Identifying the prime factor of highest multiplicity, so that it could be divided out of N at the start, leaving room to do some necessary calculations. At the time this seemed to be a promising route to take. (My initial solution ended up being quite large at 326 bytes, later golfed down to 185 bytes.) But the rest of the method teukon sketched would have been extremely complicated, so as it turned out, I took a rather different route. It proved to be sufficient to divide out the largest prime power factor of N corresponding to the largest prime factor on N; doing this for the prime of highest multiplicity would have added needless complexity and length to the regex.
What remained was treating the sum of divisors as a product of sums instead of a straight sum. As explained by teukon on 14 March 2014:
We're given a number n = p0a0p1a1...pk-1ak-1. We want to handle the sum of the factors of n, which is (1 + p0 + p02 + ... + p0a0)(1 + p1 + p12 + ... + p1a1)...(1 + pk-1 + pk-12 + ... + pk-1ak-1).
It blew my mind to see this. I had never thought of factoring the aliquot sum in that way, and it was this formula more than anything else that made the solvability of abundant number matching in ECMAScript regex look plausible.
In the end, instead of testing for a result of addition or multiplication exceeding N, or testing that such a result pre-divided by M exceeds N/M, I went with testing if a result of division is less than 1. I arrived at the first working version on 7 April 2014.
The full history of my golf optimizations of this regex is on github. At a certain point one optimization ended up making the regex much slower, so from that point on I maintained two versions. They are:
regex for matching abundant numbers.txt
regex for matching abundant numbers - shortest.txt
These regexes are fully compatible with both ECMAScript and PCRE, but a recent optimization involved using a potentially non-participating capture group \14, so by dropping PCRE compatibility and changing \14? to \14 they can both be reduced by 1 byte.
Here is the smallest version, with that optimization applied (making it ECMAScript-only), reformatted to fit in a StackExchange code block with (mostly) no horizontal scrolling needed:
# Match abundant numbers in the domain ^x*$ using only the ECMAScript subset of regex
# functionality. For the purposes of these comments, the input number = N.
^
# Capture the largest prime factor of N, and the largest power of that factor that is
# also a factor of N. Note that the algorithm used will fail if N itself is a prime
# power, but that's fine, because prime powers are never abundant.
(?=
( # \1 = tool to make tail = Z-1
( # Repeatedly divide current number by its smallest factor
(?=(xx+?)\3+$)
(x+)\4*(?=\4$)
)+ # A "+" is intentionally used instead of a "*", to fail if N
# is prime. This saves the rest of the regex from having to
# do needless work, because prime numbers are never abundant.
(?!\3+$) # Require that the last factor divided out is a different prime.
(?=(xx(x*?))\5*$) # \5 = the largest prime factor of N; \6 = \5-2
x # An extra 1 so that the tool \1 can make tail = Z-1 instead of just Z
)
(x+) # Z = the largest power of \5 that is a factor of N; \7 = Z-1
)
# We want to capture Z + Z/\5 + Z/\5^2 + ... + \5^2 + \5 + 1 = (Z * \5 - 1) / (\5 - 1),
# but in case Z * \5 > N we need to calculate it as (Z - 1) / (\5 - 1) * \5 + 1.
# The following division will fail if Z == N, but that's fine, because no prime power is
# abundant.
(?=
\1 # tail = (Z - 1)
(x(x*)) # \8 = (Z - 1) / (\5 - 1); \9 = \8-1
# It is guaranteed that either \8 > \5-1 or \8 == 1, which allows the following
# division-by-multiplication to work.
(?=\8*$)
\6\9+$
)
(?=
(.*) # \10 = tool to compare against \11
( # \11 = \8 * \5 = (Z - 1) / (\5 - 1) * \5; later, \13 = \11+1
(?=\8*$)
\5\9+$
)
)
# Calculate Q = \15{2} + Q_R = floor(2 * N / \13). Since we don't have space for 2*N, we
# need to calculate N / \13 first, including the fractional part (i.e. the remainder),
# and then multiply the result, including the fractional part, by 2.
(?=
(x*?)(?=(x\11)+$) # \12 = N % \13; \13 = \11 + 1
(?=\12\10|(x)) # \14 = Q_R = floor(\12 * 2 / \13)
# = +1 carry if \12 * 2 > \11, or NPCG otherwise
(x(x*)) # \15 = N / \13; \16 = \15-1
(?=\15*$)
(?=\11+$) # must match if \15 < \13; otherwise doesn't matter
\11\16+$ # must match if \15 >= \13; otherwise doesn't matter
)
# Calculate \17 = N / Z. The division by Z can be done quite simply, because the divisor
# is a prime power.
(?=
(x(x*)) # \17 = N / Z; \18 = \17-1
(?=\17*$)
\7\18+$
)
# Seed a loop which will start with Q and divide it by (P^(K+1)-1)/(P-1) for every P^K
# that is a factor of \17. The state is encoded as \17 * P + R, where the initial value
# of R is Q, and P is the last prime factor of N to have been already processed.
#
# However, since the initial R would be larger than \17 (and for that matter there would
# be no room for any nonzero R since with the initial value of P, it is possible for
# \17 * P to equal N), treat it as a special case, and let the initial value of R be 0,
# signalling the first iteration to pretend R=Q. This way we can avoid having to divide Q
# and \17 again outside the loop.
#
# While we're at it, there's really no reason to do anything to seed this loop. To seed
# it with an initial value of P=\5, we'd have to do some multiplication. If we don't do
# anything to seed it, it will decode P=Z. That is wrong, but harmless, since the next
# lower prime that \17 is divisible by will still be the same, as \5 cannot be a factor
# of \17.
# Start the loop.
(
(?=
( # \20 = actual value of R
x*?(?=\17+$) # move forward by directly decoded value of R, which can be zero
# The division by \17 can be done quite simply, because it is known that
# the quotient is prime.
(?=
\17+? # tail = \17 * (a prime which divides into \17)
(?=
( # \21 = encoded value for next loop iteration
(xx(x*)) # \22 = decoded value of next smaller P; \23 = (\22-1)-1
(?=\18+$) # iff \22 > \17, this can have a false positive, but never a false negative
\22*$ # iff \22 < \17, this can have a false positive, but never a false negative
)
)
# Find the largest power of \22 that is a factor of \17, while also asserting
# that \22 is prime.
(x+) # \24 = the largest power of \22 that is a factor of \17
.*(?=\17$)
\24*(?=\24$)
(?!
(xx+)\25*
(?!\22+$)
\25$
)
\22+$
)
(
(?=(x\7)+$) # True iff this is the first iteration of the loop.
\15{2}\14 # Potentially unset capture, and thus dependent on ECMAScript
# behavior. Change "\14" to "\14?" for compatibility with non-
# ECMAScript engines, so that it will act as an empty capture
# with engines in which unset backrefs always fail to match.
|
)
)
)
# Calculate \30 = (\24 - 1) / (\22 - 1) * \22 + 1
(?=
.*(?=\24)x # tail = \24 - 1
(x(x*)) # \28 = (\24 - 1) / (\22 - 1); \29 = \28-1
(?=\28*$)
\23\29*$
)
(?=
.*(x( # \30 = 1 + \28 * \22 = (\28 - 1) / (\22 - 1) * \22 + 1; \31 = \30-1
(?=\28*$)
\22\29+$
))
)
# Calculate \33 = floor(\20 / \30)
(
.*(?!\30)\20 # if dividing \20 / \30 would result in a number less than 1,
# then N is abundant and we can exit the loop successfully
|
(?=
.*?(?!x\20)(?=\30*$)
(x(x*)) # \33 = \20 / \30; \34 = \33-1
(?=\33*$)
(?=\31+$) # must match if \33 < \30; otherwise doesn't matter
\31\34+$ # must match if \33 >= \30; otherwise doesn't matter
)
# Encode the state for the next iteration of the loop, as \17 * \22 + \33
.*(?=\33\21$)
)
)+$
