40
\$\begingroup\$

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!

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

55 Answers 55

41
+400
\$\begingroup\$

ECMAScript Regex, 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).

As with my regex posted a couple days ago, I'll give a warning: I highly recommend learning how to solve unary mathematical problems in ECMAScript regex. It's been a fascinating journey for me, and I don't want to spoil it for anybody who might potentially want to try it themselves, especially those with an interest in number theory. See that post for a list of consecutively spoiler-tagged recommended problems to solve one by one.

So do not read any further if you don't want some deep unary regex magic spoiled for you. My previous post was just a small taste. If you do want to take a shot at figuring out this magic yourself, I highly recommend starting by solving some problems in ECMAScript regex as outlined in that post linked above.

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 any 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.)

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$)
  )
)+$
\$\endgroup\$
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – DJMcMayhem Jan 23 at 20:35
  • 1
    \$\begingroup\$ -98 bytes \$\endgroup\$ – Grimmy Mar 5 at 17:19
27
\$\begingroup\$

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.

\$\endgroup\$
  • 4
    \$\begingroup\$ ~k<0 is fancy, but I think -1<k also does the trick ;) \$\endgroup\$ – Martin Ender Feb 21 '17 at 13:55
12
\$\begingroup\$

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
\$\endgroup\$
10
\$\begingroup\$

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.
\$\endgroup\$
10
\$\begingroup\$

Python, 44 bytes

lambda n:sum(i*(n%i<1)for i in range(1,n))>n

Try it online!

\$\endgroup\$
  • \$\begingroup\$ It's a shame you can't do range(n). That pesky modulus by zero \$\endgroup\$ – DJMcMayhem Feb 21 '17 at 1:44
10
\$\begingroup\$

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.
\$\endgroup\$
  • 1
    \$\begingroup\$ I'm surprised Mathematica has no built in for this.. \$\endgroup\$ – MrPaulch Feb 21 '17 at 17:08
  • 1
    \$\begingroup\$ @MrPaulch Considering the length of the program though, the builtin may very well be longer in name >.> \$\endgroup\$ – Conor O'Brien Feb 22 '17 at 1:51
  • 1
    \$\begingroup\$ @ConorO'Brien If it existed, it would probably be AbundantNumberQ, so it would save a couple bytes :) \$\endgroup\$ – ngenisis Feb 22 '17 at 1:54
8
\$\begingroup\$

05AB1E, 5 4 bytes

-1 bytes thanks to scottinet

ѨO‹

Try it online! or Try 0 to 100

\$\endgroup\$
  • \$\begingroup\$ @scottinet Nice! \$\endgroup\$ – Riley Sep 12 '17 at 15:50
7
\$\begingroup\$

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

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ It's always amazed me how you can do math in retina. I'd love to see an explanation! :) \$\endgroup\$ – DJMcMayhem Feb 21 '17 at 14:49
  • 1
    \$\begingroup\$ @DJMcMayhem Sorry forgot to add that earlier. Done. \$\endgroup\$ – Martin Ender Feb 21 '17 at 14:55
6
+100
\$\begingroup\$

8086 Assembly, 23 28 25 24 bytes

8bc8 d1e9 33db 33d2 50f7 f158 85d2 7502 03d9 7204 e2f0 3bc3

Unassembled:

; calculate if N (1 < N <= 65535) is abundant
; input: N (mem16/r16)
; output: CF=1 -> abundant, CF=0 -> not abundant
ABUND   MACRO   N 
        LOCAL DIV_LOOP, CONT_LOOP, END_ABUND
        IFDIFI <N>,<AX> ; skip if N is already AX
    MOV  AX, N          ; AX is dividend
        ENDIF
    MOV  CX, AX         ; counter starts at N / 2
    SHR  CX, 1          ; divide by 2
    XOR  BX, BX         ; clear BX (running sum of factors)
DIV_LOOP:
    XOR  DX, DX         ; clear DX (high word for dividend)
    PUSH AX             ; save original dividend
    DIV  CX             ; DX = DX:AX MOD CX, AX = DX:AX / CX
    POP  AX             ; restore dividend (AX was changed by DIV)
    TEST DX, DX         ; if remainder (DX) = 0, it divides evenly so CX is a divisor
    JNZ  CONT_LOOP      ; if not, continue loop to next
    ADD  BX, CX         ; add number to sum
    JC   END_ABUND      ; if CF=1, BX has unsigned overflow it is abundant (when CX < 65536)
CONT_LOOP:
    LOOP DIV_LOOP
    CMP  AX, BX         ; BX<=AX -> CF=0 (non-abund), BX>AX -> CF=1 (abund)
END_ABUND:
        ENDM

Example test program, testing N = [12..1000]:

    MOV  AX, 12         ; start tests at 12
LOOP_START:
    ABUND AX            ; call ABUND MACRO for N (in AX)
    JNC  LOOP_END       ; if not abundant, display nothing
    CALL OUTDECCSV      ; display AX as decimal (generic decimal output routine)
LOOP_END:
    INC  AX             ; increment loop counter
    CMP  AX, 1000       ; if less than 1000...
    JBE  LOOP_START     ; continue loop
    RET                 ; return to DOS

Output [2..1000]

12, 18, 20, 24, 30, 36, 40, 42, 48, 54, 56, 60, 66, 70, 72, 78, 80, 84, 88, 90, 96, 100, 102, 104, 108, 112, 114, 120, 126, 132, 138, 140, 144, 150, 156, 160, 162, 168, 174, 176, 180, 186, 192, 196, 198, 200, 204, 208, 210, 216, 220, 222, 224, 228, 234, 240, 246, 252, 258, 260, 264, 270, 272, 276, 280, 282, 288, 294, 300, 304, 306, 308, 312, 318, 320, 324, 330, 336, 340, 342, 348, 350, 352, 354, 360, 364, 366, 368, 372, 378, 380, 384, 390, 392, 396, 400, 402, 408, 414, 416, 420, 426, 432, 438, 440, 444, 448, 450, 456, 460, 462, 464, 468, 474, 476, 480, 486, 490, 492, 498, 500, 504, 510, 516, 520, 522, 528, 532, 534, 540, 544, 546, 550, 552, 558, 560, 564, 570, 572, 576, 580, 582, 588, 594, 600, 606, 608, 612, 616, 618, 620, 624, 630, 636, 640, 642, 644, 648, 650, 654, 660, 666, 672, 678, 680, 684, 690, 696, 700, 702, 704, 708, 714, 720, 726, 728, 732, 736, 738, 740, 744, 748, 750, 756, 760, 762, 768, 770, 774, 780, 784, 786, 792, 798, 800, 804, 810, 812, 816, 820, 822, 828, 832, 834, 836, 840, 846, 852, 858, 860, 864, 868, 870, 876, 880, 882, 888, 894, 896, 900, 906, 910, 912, 918, 920, 924, 928, 930, 936, 940, 942, 945, 948, 952, 954, 960, 966, 968, 972, 978, 980, 984, 990, 992, 996, 1000

Output [12500..12700]

12500, 12504, 12510, 12512, 12516, 12520, 12522, 12528, 12530, 12534, 12540, 12544, 12546, 12552, 12558, 12560, 12564, 12570, 12572, 12576, 12580, 12582, 12584, 12588, 12594, 12600, 12606, 12612, 12618, 12620, 12624, 12628, 12630, 12636, 12640, 12642, 12648, 12650, 12654, 12656, 12660, 12666, 12670, 12672, 12678, 12680, 12684, 12688, 12690, 12696, 12700

Output [25100..25300]

25100, 25104, 25110, 25116, 25120, 25122, 25128, 25130, 25134, 25140, 25144, 25146, 25152, 25158, 25160, 25164, 25168, 25170, 25172, 25176, 25180, 25182, 25188, 25194, 25200, 25206, 25212, 25216, 25218, 25220, 25224, 25228, 25230, 25232, 25236, 25240, 25242, 25245, 25248, 25254, 25256, 25260, 25266, 25270, 25272, 25278, 25280, 25284, 25290, 25296, 25300

Updates:

  • 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!
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Deadcode Jan 23 at 9:11
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – 640KB Jan 23 at 17:04
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Deadcode Jan 24 at 23:31
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Deadcode Jan 24 at 23:37
  • 1
    \$\begingroup\$ 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! \$\endgroup\$ – 640KB Jan 25 at 0:30
5
\$\begingroup\$

Actually, 5 bytes

;÷Σ½>

Try it online!

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

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.

\$\endgroup\$
  • 4
    \$\begingroup\$ 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. :) \$\endgroup\$ – DJMcMayhem Jul 18 '17 at 15:44
4
\$\begingroup\$

PARI/GP, 15 bytes

n->sigma(n)>2*n

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

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
  • 4
    \$\begingroup\$ 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! \$\endgroup\$ – Kevin Cruijssen Feb 21 '17 at 9:30
  • 1
    \$\begingroup\$ 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) \$\endgroup\$ – CAD97 Feb 21 '17 at 14:30
4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – AdmBorkBork Feb 21 '17 at 15:27
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

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>

\$\endgroup\$
  • \$\begingroup\$ I was sure a recursive answer would be best but I didn't think it would be this good. \$\endgroup\$ – Neil Feb 22 '17 at 0:18
3
\$\begingroup\$

Japt, 9 7 6 bytes

<Uâ1 x

Saved 2 bytes thanks to ETHproductions. Saved 1 byte thanks to obarakon.

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 9 characters, 10 bytes. \$\endgroup\$ – Metoniem Feb 21 '17 at 10:20
  • \$\begingroup\$ @Metoniem I'm sure â is 1 byte, in unicode at least (0xE2). \$\endgroup\$ – Tom Feb 21 '17 at 10:29
  • 1
    \$\begingroup\$ @Metoniem Japt uses the ISO-8859-1 encoding, in which â is a single byte. \$\endgroup\$ – ETHproductions Feb 21 '17 at 14:29
  • \$\begingroup\$ 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 :-) \$\endgroup\$ – ETHproductions Feb 21 '17 at 14:30
  • \$\begingroup\$ @TomDevs Nice! You can do <Uâ1 x to save a byte. Japt adds the U in front of the program. \$\endgroup\$ – Oliver Feb 21 '17 at 16:12
3
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ "(%1%%%%j)" oh, batch :) \$\endgroup\$ – Bryan Boettcher Feb 21 '17 at 23:44
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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) \$\endgroup\$ – Brad Gilbert b2gills Feb 21 '17 at 20:35
  • \$\begingroup\$ @BradGilbertb2gills Thanks! :) \$\endgroup\$ – Ven Feb 21 '17 at 22:22
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Conor O'Brien Feb 22 '17 at 1:55
  • \$\begingroup\$ 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. \$\endgroup\$ – Blocks Feb 22 '17 at 11:06
  • \$\begingroup\$ ~ switches so it's i.e.#i. but what is the purpose of [: ? \$\endgroup\$ – Blocks Feb 22 '17 at 11:09
  • \$\begingroup\$ 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. \$\endgroup\$ – Conor O'Brien Feb 22 '17 at 12:27
  • \$\begingroup\$ 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 \$\endgroup\$ – Conor O'Brien Feb 22 '17 at 12:28
2
\$\begingroup\$

Pyth, 11 bytes

>sPf!%QTS

Old:

L!%Qb>sPy#S

I can't use !% as a pfn for #, because it's two functions. Makes me sad :(.


L!%Qb>sPy#SQ    Program's argument: Q
L!%Qb           Define a lambda y, that takes b as an argument
 !%Qb           Return true if Q is divisible by b
          S     Make a range 1..Q
        y#      Filter that range with the lambda (y)
       P        Remove the last element (Q itself)
      s         Sum them
     >     Q    Check if that sum is greater than the program's argument
\$\endgroup\$
  • \$\begingroup\$ Not defining a function seems to be shorter: >sPf!%QTS \$\endgroup\$ – FryAmTheEggman Feb 21 '17 at 15:42
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

PowerShell, 43 bytes

param($n)1..$n|%{$s+=$_*!($n%$_)}
$s-gt2*$n

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Common Lisp, 63 bytes

(lambda(n)(>(loop for i from 1 below n if(=(mod n i)0)sum i)n))

Try it online!

\$\endgroup\$
2
\$\begingroup\$

F#, 51 bytes

let f n=Seq.filter(fun x->n%x=0){1..n-1}|>Seq.sum>n

Try it online!

Filters out all the numbers that don't divide evenly into n, then sums them and compares them against n.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.