# An abundance of integers!

An Abundant number is any number where the sum of its proper divisors is greater than the original number. For example, the proper divisors of 12 are:

1, 2, 3, 4, 6


And summing these results in 16. Since 16 is larger than 12, 12 is abundant. Note that this does not include "Perfect numbers", e.g. numbers that are equal to the sum of its proper divisors, such as 6 and 28.

Your task for today is to write a program or function that determines if a number is abundant or not. Your program should take a single integer as input, and output a truthy/falsy value depending on whether it is abundant or not. You can assume that the input will always be valid and greater than 0, so for bad inputs, undefined behavior is fine.

You may take your input and output in any reasonable format, for example STDIN/STDOUT, files, or arguments/return values would all be acceptable.

For reference, here are the abundant numbers up to 100:

12,
18,
20,
24,
30,
36,
40,
42,
48,
54,
56,
60,
66,
70,
72,
78,
80,
84,
88,
90,
96,
100


And more can be found on A005101

Since this is , standard loopholes are denied, and try to write the shortest possible code you can in whichever language you happen to choose!

• "the first odd abundant is 945 = 3^3*5*7, the 232nd abundant number!" Commented Feb 21, 2017 at 14:29
• The asymptotic density of abundant numbers is somewhere within the interval [0.24761748, 0.24764422]. Calculated using the source code included in this paper. Commented Jan 25, 2019 at 22:20
• I am trying to do this in Geometry Dash. It's a nightmare Commented Jan 29, 2019 at 3:25

# Regex (ECMAScript), 1085855597536511508 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
# 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: 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$)
)
)+$ • Comments are not for extended discussion; this conversation has been moved to chat. Commented Jan 23, 2019 at 20:35 • -98 bytes Commented Mar 5, 2019 at 17:19 # Python 2, 41 40 bytes n=k=j=input() while~k<0:j-=1;k-=j>>n%j*n  Output is via exit code, so 0 is truthy and 1 is falsy. Try it online! ### How it works After setting all of n, k, and j to the input from STDIN, we enter the while loop. Said loop will break as soon as -k - 1 = ~k ≥ 0, i.e., k ≤ -1 / k < 0. In each iteration, we first decrement j to consider only proper divisors of n. If j is a divisor of n, n%j yields 0 and j >> n%j*n = j/20 = j gets subtracted from k. However, if j does not divide n, n%j is positive, so n%j*n is at least n > log2 j and j >> n%j*n = j / 2n%j*n = 0 is subtracted from k. For abundant numbers, k will reach a negative value before or when j becomes 1, since the sum of n's proper divisors is strictly greater than n. In this case, we break out of the while loop and the program finishes normally. However, if n is not abundant, j eventually reaches 0. In this case, n%j throws a ZeroDivisionError and the program exits with an error. • ~k<0 is fancy, but I think -1<k also does the trick ;) Commented Feb 21, 2017 at 13:55 # Brachylog, 5 bytes fk+>?  Try it online! ### Explanation f Factors k Knife: remove the last one (the input itself) + Sum >? Stricly greater than the Input  ## Mathematica, 17 bytes Tr@Divisors@#>2#&  ## Explanation Tr@ The sum of the main diagonal of Divisors@ the list of divisors of # the first argument > is greater than 2# twice the first argument. & End of function.  • I'm surprised Mathematica has no built in for this.. Commented Feb 21, 2017 at 17:08 • @MrPaulch Considering the length of the program though, the builtin may very well be longer in name >.> Commented Feb 22, 2017 at 1:51 • @ConorO'Brien If it existed, it would probably be AbundantNumberQ, so it would save a couple bytes :) – user61980 Commented Feb 22, 2017 at 1:54 # Jelly, 3 bytes Æṣ>  Try it online! ### How it works Æṣ> Main link. Argument: n Æs Get the proper divisor sum of n. > Test if the result is greater than n.  # Python, 44 bytes lambda n:sum(i*(n%i<1)for i in range(1,n))>n  Try it online! • It's a shame you can't do range(n). That pesky modulus by zero Commented Feb 21, 2017 at 1:44 # 05AB1E, 5 4 bytes -1 bytes thanks to scottinet Ñ¨O‹  ## Retina, 50 45 bytes ^(?!(1(?<=(?=(?(\3+$)((?>\2?)\3)))^(1+)))*1$)  Input in unary, output 1 for abundant numbers, 0 otherwise. There is nothing Retina-specific about this solution. The above is a pure .NET regex which matches only abundant numbers. Try it online! (Test suite that filters decimal input with the above regex.) ## Retina, 34 bytes Byte count assumes ISO 8859-1 encoding. M!&(1+)$(?<=^\1+)
1>¶

^(1+)¶1\1


Input in unary, output 1 for abundant numbers, 0 otherwise.

Try it online!

### Explanation

M!&(1+)$(?<=^\1+)  We start by getting all divisors of the input. To do this, we return (!) all overlapping (&) matches (M) of the regex (1+)$(?<=^\1+). The regex matches some suffix of the input, provided that the entire input is a multiple of that suffix (which we ensure by trying to reach the beginning fo the string using only copies of the suffix). Due to the way the regex engine looks for matches, this will result a list of divisors in descending order (separated by linefeeds).

1>¶



The stage itself simply matches linefeeds (¶) and removes them. However, the 1> is a limit, which skips the first match. So this effectively adds together all divisors except the input itself. We end up with the input on the first line and the sum of all proper divisors on the second line.

^(1+)¶1\1


Finally, we try to match the at least one more 1 on the second line than we have on the first line. If that's the case, the sum of proper divisors exceeds the input. Retina counts the number of matches of this regex, which will be 1 for abundant numbers and 0 otherwise.

• It's always amazed me how you can do math in retina. I'd love to see an explanation! :) Commented Feb 21, 2017 at 14:49
• @DJMcMayhem Sorry forgot to add that earlier. Done. Commented Feb 21, 2017 at 14:55

# x86 machine code, 25 bytes

00000000: 8bc8 d1e9 33db 33d2 50f7 f158 85d2 7502  ....3.3.P..X..u.
00000010: 03d9 7204 e2f0 3bc3 c3                   ..r...;..


Listing:

8B C8       MOV  CX, AX         ; counter starts at N / 2
D1 E9       SHR  CX, 1          ; divide by 2
33 DB       XOR  BX, BX         ; clear BX (running sum of factors)
DIV_LOOP:
33 D2       XOR  DX, DX         ; clear DX (high word for dividend)
50          PUSH AX             ; save original dividend
F7 F1       DIV  CX             ; DX = DX:AX MOD CX, AX = DX:AX / CX
58          POP  AX             ; restore dividend (AX was changed by DIV)
85 D2       TEST DX, DX         ; if remainder (DX) = 0, CX is a divisor
75 02       JNZ  CONT_LOOP      ; if not, continue loop to next
CONT_LOOP:
72 04       JC   END_ABUND      ; if CF=1, BX has unsigned overflow it is abundant
E2 F0       LOOP DIV_LOOP
3B C3       CMP  AX, BX         ; BX<=AX -> CF=0 (non-abund), BX>AX -> CF=1 (abund)
END_ABUND:


Callable function, input N in AX. Output CF=1 if abundant, CF=0 if not abundant.

Try it online!

Props:

• Fixed for 16-bit overflow (+5 bytes). Thanks @deadcode for the suggestions!
• Simplified return logic (-3 bytes). Thx to help from @deadcode once again.
• Use TEST instead of CMP (-1 byte). Thx to @l4m2, and make sure to upvote @l4m2's shorter x86 answer!
• I would suggest replacing JLE with JBE to double the range of numbers this can test before overflows start causing it to give false negatives. Then instead of starting to fail at 12600 (aliquot sum 35760), it'll start to fail at 25200 (aliquot sum 74744). Even better would be to also detect the carry flag and treat that as an abundant number without needing to calculate the actual >16 bit sum. Commented Jan 23, 2019 at 9:11
• Good catch @Deadcode. I've updated the code for jump below instead of jump less. I see what you mean, doing a JC after the ADD BX,CX will catch the unsigned overflow there and make it correct up until N=65535. Complicates flag testing and return state a bit, since previously CF implied false. Updated with fix also. Commented Jan 23, 2019 at 17:04
• You can save 3 bytes by inverting the specification of your return value, with CF being set if abundant and clear if not. But I'd recommend doing the edit to correct the output documentation first, so it looks nice in the edit history. Commented Jan 24, 2019 at 23:31
• Also, to keep things simple, the specification should be that the return value is in the carry flag, and none of that fuss with the other flags. The caller should use JC or JNC to act on whether the number is abundant or not. Commented Jan 24, 2019 at 23:37
• Thanks so much for all of your help and your comments. I've updated the inline documentation and removed the term ungolfed. Honestly never gave it much thought but I see your point about it, as it isn't any different with the exception of inline comments. Also agree about makint the return flags clearer as well. Will work on that in a bit. Thanks for the attention and the assistance! Commented Jan 25, 2019 at 0:30

# Actually, 5 bytes

;÷Σ½>


Try it online!

;     # Duplicate input
÷    # Get divisors
Σ   # Sum
½  # Divide by 2 (float)
> # Test is greater than input


Java 8, 53 bytes ( a lot more if you include the ceremonial code )

return IntStream.range(1,n).filter(e->n%e<1).sum()>n;


Try it online

Explanation :

IntStream.range(1,n) \\ numbers from 1 to n-1
filter(e->n%e<1)     \\ filter in numbers that perfectly divide the number n
sum()>n              \\ sum and compare to original number

• Great answer, but with Java 8 you must include the function in your byte-count. Then again, you can drop the return if I'm not mistaken, so it will be even shorter: n->IntStream.range(1,n).filter(e->n%e<1).sum()>n (not 100% if this is correct, I almost never program in Java 8). Welcome to PPCG! Commented Feb 21, 2017 at 9:30
• The correct count via standard count would be n->java.util.stream.IntStream.range(1,n).filter(e->n%e<1).sum()>n for 65 bytes (assuming I got the package right off the top of my head) Commented Feb 21, 2017 at 14:30

# 05AB1E, 4 bytes

Ñ¨O‹


Try it online!

# How it works

Ñ        #list of divisors
¨       #remove last element (i.e the input from the list of factors)
O      #sum the list
‹     #is this sum less than the input?


Sorry to post in old question, I was just going through old posts for practise and noticed my solution was shorter than the next best 05AB1E solution.

• Sorry to post in old question Don't worry about it! I'm always happy to see answers on my old challenges, and it's actually encouraged around here. :) Commented Jul 18, 2017 at 15:44

# Julia, 25 bytes

a(n,r=1:n)=(n.%r.<1)'r>2n

Attempt This Online!

# Regex (Perl/PCRE+(?^=)RME), 36 bytes

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


Try it on replit.com (RegexMathEngine)

Takes its input in unary, as the length of a string of xs.

This is based on my 43 byte .NET version; for the full explanation, see below. Lookinto, a new feature in RegexMathEngine, allows (?<=(?=\2+$)^.*) to be shortened to the equivalent (?^=\2+$).

This is not just the shortest, but the fastest under RegexMathEngine, even though the 43 byte .NET regex it's based on is the slowest under .NET (beaten by both 44 byte regexes in speed).

# Regex (Java / .NET) / Retina, 43 bytes

(?=((\2x+?|^x)(?<=(?=\2+$)^.*))+)(\2x+)\3+$


Try it online! - Java (very slow)
Try it online! - Regex (.NET)
Try it online! - Retina

This is 2 bytes shorter than Martin Ender's answer. Its structure is quite different, and it's more portable to different regex engines.

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
(\2x+?|^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 ) )+ ) (\2x+) # 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.


# Regex (Pythonregex / .NET) / Retina, 47 bytes

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


Try it online! - Python import regex
Try it online! - .NET
Try it online! - Retina

This is a port of the 43 byte Java/.NET version, avoiding a nested backreference in order to add Pythonregex support. The way in which this is done (placing the copy inside the lookbehind) removes Java support.

# Regex (Perl / PCRE2v10.35+), 49 bytes

This is a direct port of the .NET regex, emulating variable-length lookbehind using a recursive subroutine call.

(?=((\2x+?|^x)((?<=(?=^\2+$|(?3)).)))+)(\2x+)\4+$


Try it online! - Perl (slow)
Attempt This Online! - PCRE2 v10.40+

(?=
(
(\2x+?|^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 )) )+ ) (\2x+) \4+$


# Regex (Java / Pythonregex / .NET) / Retina, 50 bytes

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


Try it online! - Java (very slow)
Try it online! - Python import regex
Try it online! - .NET

This is a port of the 43 byte Java/.NET version, avoiding a nested backreference in order to add Pythonregex support, while keeping Java support.

# Regex (Perl / PCRE), 58 bytes

Porting the PCRE2 regex to PCRE1 requires working around some bugs:

(?=((?=(\3|^))(\2x+?)((?<=(?=z|^\3+$|(?4)).)))+)(\3x+)\5+$


The (\2x+?|^x) had to be changed to (?=(\3|^))(\2x+?), 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 in PCRE2 up to v10.34. 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" in PCRE1.

Try it online! - Perl (slow)
Try it online! - PCRE1
Try it online! - PCRE2 v10.33

Attempt This Online! - PCRE2 v10.40+

# Regex (.NET) / Retina, 44 bytes

^(?!((?<=(?=(?(\3+$)((?>\2?)\3)))(^x*))x)*$)


Try it online! - Regex (.NET)
Try it online! - Retina

^(?!(x(?=(x*$)(?<=(?(^\2+)(\2(?>\3?))))))*$)


Try it online! - Regex (.NET)
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.
)


As far as speed goes, the smallest-to-largest version is faster than the largest-to-smallest version (both in .NET and their ports below). Both are faster than the 43 byte version under .NET.

## Regex (Perl/PCRE+(?^=)RME), 42 bytes

^(?!(x(?=(x*))(?^=(?(?=\2+$)(\3?+\2))))*$)


Try it on replit.com (RegexMathEngine)

This is a port of the largest-to-smallest 44 byte .NET regex, using lookinto instead of variable-length lookbehind. Although the Perl/PCRE syntax for lookahead conditionals is more verbose, this is compensated for by being able to use a possessive quantifier.

## Regex (Perl/PCRE+(?^=)RME), 44 bytes

^(?!((?^0=(x*))(?^=(?(?=\2+$)(\3?+\2)))x)*$)


Try it on replit.com (RegexMathEngine)

This is a port of the smallest-to-largest 44 byte .NET regex, again using lookinto instead of variable-length lookbehind. This one is less conducive to being ported, and I had to use (?^0=), lookinto accessing the in-progress current match. I've not decided how to finalize the current behavior of this, so it's likely this version will not work with a future version of lookinto.

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


Try it online! - PCRE2 v10.33 (PHP)
Try it on regex101 - PCRE2 v10.38+
Attempt This Online! - PCRE2 v10.40+ (PHP)
Attempt This Online! - PCRE2 v10.40+ (C++)

• Variable-length lookbehind emulation? Whatever next?
– Neil
Commented Mar 4, 2021 at 12:31

# PARI/GP, 15 bytes

n->sigma(n)>2*n


The variant n->sigma(n,-1)>2 is, unfortunately, longer.

# Powershell, 51 49 Bytes

param($i)((1..$i|?{!($i%$_)})-join"+"|iex)-gt2*$i  I wish I could remove some brackets. -2 thanks to AdmBorkBork, instead of not counting the input in the initial range, we just take it into account in the final check. Loop through range of 1.. to the $input, minus 1, find where (?) the inverse modulo of input by the current number is $true (aka only 0) - then -join all of those numbers together with + and iex the resulting string to calculate it, then see if the sum of these parts is greater than the input. PS C:\++> 1..100 | ? {.\abundance.ps1$_}
12
18
20
24
30
36
40
42
48
54
56
60
66
70
72
78
80
84
88
90
96
100

• You can save two bytes by counting the top value and checking that it's bigger than 2x the input -- param($i)((1..$i|?{!($i%$_)})-join"+"|iex)-gt2*$i Commented Feb 21, 2017 at 15:27 # k, 19 16 15 bytes {x<+/&~(!x)!'x}  Returns 1 for true, and 0 for false. Try it online! { } /function(x) (!x) /{0, 1, ..., x-1} ' /for each n in {0, 1, ..., x-1}: ! x / do (x mod n) ~ /for each, turn 0 -> 1, * -> 0 (map not) & /get indices of 1's +/ /sum (fold add) x< /check if x < the sum  # MATL, 6 bytes Z\sGE>  Outputs 1 for abundant numbers, 0 otherwise. ## How it works Z\ % list the divisors of the implicit input s % add them G % push the input again E % double it > % compare % implicitly display result  ## QBIC, 22 bytes :[a/2|~a%b|\p=p+b}?p>a  This is an adaptation to the QBIC primality test. Instead of counting the divisors and checking if it's less than three, this sums the proper divisors. This runs only along half of 1 to n, where the primality test runs through 1 to n completely. Explanation: : Get the input number, 'a' [a/2| FOR(b=1, b<=(a/2), b++) ~a%b IF a MOD b != 0 --> QBasic registers a clean division (0) as false. The IF-branch ('|') therefor is empty, the code is in the ELSE branch ('\') |\p=p+b THEN add b to runnning total p } Close all language constructs: IF/END IF, FOR/NEXT ?p>a Print '-1' for abundant numbers, 0 otherwise.  # JavaScript (ES6), 33 bytes let g = x=>(f=n=>--n&&n*!(x%n)+f(n))(x)>x <input type=number min=1 value=1 step=1 oninput="O.innerHTML=g(+value)"><br> <pre id=O>false</pre> • I was sure a recursive answer would be best but I didn't think it would be this good. – Neil Commented Feb 22, 2017 at 0:18 # Japt, 9 7 6 bytes <Uâ1 x  Saved 2 bytes thanks to ETHproductions. Saved 1 byte thanks to obarakon. Try it online! • 9 characters, 10 bytes. Commented Feb 21, 2017 at 10:20 • @Metoniem I'm sure â is 1 byte, in unicode at least (0xE2). – Tom Commented Feb 21, 2017 at 10:29 • @Metoniem Japt uses the ISO-8859-1 encoding, in which â is a single byte. Commented Feb 21, 2017 at 14:29 • If â is given a truthy argument, it will remove the actual number from the remaining list, so you can do â1 x >U to save a couple bytes :-) Commented Feb 21, 2017 at 14:30 • @TomDevs Nice! You can do <Uâ1 x to save a byte. Japt adds the U in front of the program. Commented Feb 21, 2017 at 16:12 # Cubix, 38 bytes /..?%?(O;0I:^.<.>;rrw+s;rUO?-<...O0L.@  Try it here  / . . ? % ? ( O ; 0 I : ^ . < . > ; r r w + s ; r U O ? - < . . . O 0 L . @ . . . . . . . . . . . . . . . .  0I: - sets up the stack with 0, n, n (s, n, d) ^ - start of the loop )? - decrement d and test for 0. 0 exits loop %? - mod against n and test. 0 causes ;rrw+s;rU which rotates s to top and adds d, rotates s to bottom and rejoins loop ;< - Cleanup and rejoin the loop. On exiting loop ;< - Remove d from stack and redirect -? - Remove n from s and test, 0 LOU@ turns left, outputs and exits, negatives 0O@ push zero, output and exits. positives ;O remove difference and outputs n. The path then goes through to the left turn which redirects to the @ exit # Pure Bash, 37 bytes for((;k++<$1;s+=$1%k?0:k)){((s>$1));}


Thanks to @Dennis for rearranging the code -- saving 6 bytes and eliminating the incidental output to stderr.

The input is passed as an argument.

The output is returned in the exit code: 0 for abundant, 1 for not abundant.

Output to stderr should be ignored.

Test runs:

for n in {1..100}; do if ./abundant "$n"; then echo$n; fi; done 2>/dev/null
12
18
20
24
30
36
40
42
48
54
56
60
66
70
72
78
80
84
88
90
96
100


# APL (Dyalog Unicode), 11 bytesSBCS

⊢<1⊥∘⍸0=⍳|⊢


Try it online!

Explanation:

⊢<1⊥∘⍸0=⍳|⊢ ⍝ Monadic function train
⍳   ⍝ Generate integers from 1 to input
|⊢ ⍝ For each of the above, modulo the input
0=   ⍝ Return a boolean vector where ones correspond
⍝ to zeroes
⍸      ⍝ Return the indices of the ones in the above vector
⍝ This results in a vector of the proper divisors of our input
1⊥∘      ⍝ Composed with the above, decode into unary base.
⍝ This has the same effect as summing the vector, but is used
⍝ here to comply with the function train format.
⊢<         ⍝ Is the above sum greater than our input?


# Arn, 12 bytes

Ý░™€ºa^¬"/”&


Try it!

# Explained

Unpacked: <(+\$v{!%v}1->  _ Variable initialized to STDIN; implied < Is less than ( Begin expression \ Fold with + Addition$              Filtered list
v{           Block with key of v
!          Boolean not
_      Implied
%        Modulo
v
}           End of block
1         Literal one
->          Exclusive range
_         Implied
)                    End of expression, implied


I should probably add a builtin fix for getting factors...

# RProgN, 8 Bytes

~_]k+2/<


## Explained

~_]k+2/<
~           # Zero Space Segment
_          # Convert the input to an integer
]         # Duplicate the input on the stack
k+       # Get the sum of the divisors of the top of the stack
2/     # Divded by 2
<    # Is the Input less than the sum of its divisors/2.


Try it online!

## Batch, 84 bytes

@set/ak=%1*2
@for /l %%j in (1,1,%1)do @set/ak-=%%j*!(%1%%%%j)
@cmd/cset/a"%k%>>31


Outputs -1 for an abundant number, 0 otherwise. Works by subtracting all the factors from 2n and then shifting the result 31 places to extract the sign bit. Alternative formulation, also 84 bytes:

@set k=%1
@for /l %%j in (1,1,%1)do @set/ak-=%%j*!(%1%%%%j)
@if %k% lss -%1 echo 1


Outputs 1 for an abundant number. Works by subtracting all the factors from n and then comparing the result to to -n. (set/a is Batch's only way of doing arithmetic so I can't easily adjust the loop.)

• "(%1%%%%j)" oh, batch :) Commented Feb 21, 2017 at 23:44

# Perl 6, 72 24 bytes

{$_ <sum grep$_%%*,^$_}  • Program argument: a. • Generate a list from 1..a. • Take all the numbers that are divisors of a. • Sum them. • Check if that sum is greater than a. Thanks to @b2gills. • Every occurrence of $^a after the first one can be shortened to just $a. but it is even shorter if you write it as {$_ <sum grep $_%%*,^$_} Also looking at an earlier version, [+](LIST) works (no spaces) Commented Feb 21, 2017 at 20:35
– Ven
Commented Feb 21, 2017 at 22:22

# J, 19 bytes

Thanks to Conor O'Brien for cutting it to 19 bytes!

<[:+/i.#~i.e.]%2+i.

Previous: (34 bytes)

f=:3 :'(+/((i.y)e.y%2+i.y)#i.y)>y'

Returns 1 if it's abundant and 0 if it's not.

Output:

   f 3
0
f 12
1
f 11
0
f 20
1

• Welcome to PPCG! We allow anonymous functions, so you can remove the leading f=: as part of your byte count. Also, you can get down to 19 by converting to a tacit verb: <[:+/i.#~i.e.]%2+i. Commented Feb 22, 2017 at 1:55
• Thanks for the advice! However, could you please explain the cap verb ([:) and the switch verb (~). I don't really get what they're supposed to do in this tacit verb. Commented Feb 22, 2017 at 11:06
• ~ switches so it's i.e.#i. but what is the purpose of [: ? Commented Feb 22, 2017 at 11:09
• so you know about forks, right? (f g h) y' is the same as (f y) g (h y). When f is a cap, ([: g h) y is roughly the same as g h y. As for ~, this switches the left and right arguments. It is important to know that ~ is not a verb but is actually an adverb. It modifies a verb. For example, we could have something like 2 %~ 8. Here, ~ modifies % to switch its arguments, so the expression is equivalent to 8 % 2. Commented Feb 22, 2017 at 12:27
• In the fork chain, #~` is evaluated after the verbs to its right are executed, so it's left argument becomes the result on the right Commented Feb 22, 2017 at 12:28