21
\$\begingroup\$

A superabundant number is an integer n that sets a new upper bound for its ratio with the divisor sum function σ. In other words, n is superabundant if and only if, for all positive integers x that are less than n:

$$\frac{\sigma(n)}n>\frac{\sigma(x)}x$$

For a few of the values:

n   σ(n)   σ(n)/n   superabundant
1   1      1.0000   yes
2   3      1.5000   yes
3   4      1.3333   no
4   7      1.7500   yes
5   6      1.2000   no
6   12     2.0000   yes
7   8      1.1429   no
8   15     1.8750   no
9   13     1.4444   no

A longer list of these (for test cases) can be found at OEIS A004394.

One highly recommended negative test case (if your interpreter can handle it) is 360360, because it ties with the last superabundant number.

Challenge

Your program should take in a single positive integer, and output a truthy or falsey value representing whether that integer is superabundant.

As this is , the shortest answer in bytes wins.

\$\endgroup\$

21 Answers 21

7
\$\begingroup\$

Jelly, 7 bytes

Æs÷$ÞṪ=

Try it online!

Jelly, 8 bytes

Æs÷$ÐṀ⁼W

Try it online!

Test Suite!

Explanation

Æs÷$ÐṀ⁼W ~ Full program (monadic).

    ÐṀ   ~ Keep the elements with maximal link value (auto-rangifies).
Æs       ~ Divisor sum.
  ÷$     ~ Divide by the current element.
      ⁼W ~ Check equality with the input wrapped into a singleton.
         ~ (for integers like 360360)
\$\endgroup\$
  • \$\begingroup\$ I think you can do Æs÷$ÐṀ= for 7 bytes. I didn't realize ÐṀ rangified, that is useful to know. \$\endgroup\$ – dylnan Dec 19 '17 at 16:27
  • \$\begingroup\$ @dylnan No I can't. Although it cannot be tested online, it fails for 360360. In fact, this was my initial version \$\endgroup\$ – Mr. Xcoder Dec 19 '17 at 16:28
  • \$\begingroup\$ Why would it fail for 360360? \$\endgroup\$ – dylnan Dec 19 '17 at 16:32
  • \$\begingroup\$ @dylnan 360360 is the first number it would fail for (I think), because it is the first number to tie a result which occurred before. (and our result would be [0, 1]) \$\endgroup\$ – Mr. Xcoder Dec 19 '17 at 16:34
  • \$\begingroup\$ @Mr.Xcoder I see, thanks \$\endgroup\$ – dylnan Dec 19 '17 at 16:38
5
\$\begingroup\$

Haskell, 73 bytes

-1 byte thanks to Mr. Xcoder. -7 bytes thanks to Laikoni.

r=read.show
s n=sum[r i|i<-[1..n],n`mod`i<1]/r n
f n=all((s n>=).s)[1..n]

Try it online!

Haskell's type system isn't very golfy...

\$\endgroup\$
5
\$\begingroup\$

Haskell, 64 63 61 bytes

-1 byte thanks to Mr. Xcoder.

-2 bytes thanks to Lynn.

a!x=a*sum[y|y<-[1..x],mod x y<1]
f n=and[x!n>n!x|x<-[1..n-1]]

Try it online!

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

Octave, 41 bytes

@(n)([~,p]=max((x=1:n)*~mod(x,x')./x))==n

Try it online!

Explanation

@(n)                                       % Define anonymous function of n
                x=1:n                      % Range from 1 to n. Call that x
                        mod(x,x')          % n×n matrix of all pair-wise moduli
                       ~                   % Logical negate. True means it's a divisor
               (     )*                    % Matrix-multiply x times the above matrix
                                           % (gives the dot product of vector x times
                                           % each column of the matrix)
                                 ./x       % Divide each column by each entry in x
     [~,p]=max(                     )      % Index of first occurrence of maximum
    (                                )==n  % Does it equal n?
\$\endgroup\$
3
\$\begingroup\$

J, 35 bytes

Thanks to Mr.Xcoder for finding the problem and to cole for fixing it!

[:([:*/{:>}:)@(%~>:@#.~/.~&.q:)1+i.

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ This fails for 360360 (see the challenge for more details: One highly recommended negative test case is 360360, because it ties with the last superabundant number.). \$\endgroup\$ – Mr. Xcoder Dec 19 '17 at 15:34
  • 1
    \$\begingroup\$ Fixed for +3 bytes. Try it online. Working on golfing. I like the use of #.~ a lot (honestly the whole divisor sum function is really nice). What was wrong btw is that, though the thought of doing {:=>./ is clever, it doesn't satisfy the "greater than" part of the question. \$\endgroup\$ – cole Dec 19 '17 at 16:04
  • 1
    \$\begingroup\$ Here's what I came up with to replace the sigma function, which is at the same length currently: (1#.{:(]*0=|~)])\ . Something's wrong with it though, maybe you have some thoughts? \$\endgroup\$ – cole Dec 19 '17 at 16:23
  • 1
    \$\begingroup\$ @cole The credits for the sum of divisors function go to Roger Hui, in this essay . I also started writing another sigma function but stopped after I reached 9 bytes and decided it won't be shorter than the one with the prime factorization. Thanks for fixing the problem! \$\endgroup\$ – Galen Ivanov Dec 19 '17 at 16:30
  • \$\begingroup\$ @cole The shortest other verb for sum of divisors I came up with is this: (1#.]*0=|~)1+i. It's a hook and don't fit as easily into place though :) \$\endgroup\$ – Galen Ivanov Dec 19 '17 at 17:09
3
\$\begingroup\$

Julia 0.6, 52 bytes

n->indmax(sum(x for x=1:m if m%x<1)//m for m=1:n)==n

Try it online!

This solution uses rational numbers to ensure correctness in case of equality. (Testing 360360 took almost 10 minutes.)

Using floating point, 2 bytes can be saved with the left divide:

n->indmax(m\sum(x for x=1:m if m%x<1)for m=1:n)==n
\$\endgroup\$
3
\$\begingroup\$

Pyth, 14 bytes

(FryAmTheEggman saved 1 byte)

qh.Mcs*M{yPZZS

Try it here! or see more test cases.

Just my mandatory Pyth submission which is most likely golfable.

How?

qh.Mcs*M{yPZZS ~ Full program. Q = input.

             S ~ The integers in the range [1, Q].
  .M           ~ Get the elements with maximal function value.
    cs*M{yPZZ  ~ Key function: uses a variable Z.
         yPZ      ~ The powerset of the prime factors of Z.
        {         ~ Deduplicated.
      *M          ~ Product of each.
     s            ~ And summed.
    c       Z     ~ Divided by Z.
 h             ~ First element.
q              ~ Check equality with the input. Outputs either True or False.
\$\endgroup\$
3
\$\begingroup\$

05AB1E, 10 bytes

LÑOā/ZQ¨_P

Try it online! or as a Test suite

Explanation

L            # push range [1 ... input]
 Ñ           # divisors of each
  O          # sum of each
   ā/        # divide each by its 1-based index
     Z       # get max
      Q      # compare to each
       ¨     # remove the last element
        _    # logical negation
         P   # product
\$\endgroup\$
  • \$\begingroup\$ I think (though I ain't sure) this fails for 360360 (see the challenge for more details: One highly recommended negative test case is 360360, because it ties with the last superabundant number.). \$\endgroup\$ – Mr. Xcoder Dec 19 '17 at 15:38
  • \$\begingroup\$ @Mr.Xcoder: True. Fixed it, but there may be a better way to do this now. \$\endgroup\$ – Emigna Dec 19 '17 at 20:40
3
\$\begingroup\$

Python 3, 77 bytes

-1 byte thanks to Rod. -3 bytes thanks to Dennis.

lambda n:max(range(1,n+1),key=lambda k:sum((k%i<1)/i for i in range(1,k)))==n

Try it online!

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

R using numbers, 59 bytes

f=function(n)which.max(sapply(1:n,numbers::Sigma)/(1:n))==n
\$\endgroup\$
2
\$\begingroup\$

Mathematica, 53 50 bytes

a=Tr@Divisors@#/#&;AllTrue[a@#-Array[a,#-1],#>0&]&

Pure function. Takes an integer as input and returns True or False as output.

\$\endgroup\$
  • \$\begingroup\$ Would something like Tr@Divisors@# works? \$\endgroup\$ – user202729 Dec 20 '17 at 1:54
1
\$\begingroup\$

Japt v2.0a0, 12 16 bytes

Sleep deprived brain can't seem to improve on this any further!

Returns 1 for truthy or 0 for falsey.

Æâ x÷U >Xâ x÷XÃ×

Try it

Sacrificed 4 bytes to handle 360360.


Explanation

  • Implicit input of integer U.
  • Æ Ã creates an array of integers from 0 to U-1 and passes each through the following function as X.
  • â gets the divisors of U.
  • ÷U divides each of those by U.
  • x sums the results.
  • gets the divisors of X.
  • ÷X divides each of those by X.
  • x sums the results.
  • > checks if the first result is greater than the second.
  • × reduces the resulting array of booleans by multiplcation.
\$\endgroup\$
  • 1
    \$\begingroup\$ If your current approach matches your explanation, it fails for 360360 or other such integers: One highly recommended negative test case (if your interpreter can handle it) is 360360, because it ties with the last superabundant number \$\endgroup\$ – Mr. Xcoder Dec 19 '17 at 19:23
  • \$\begingroup\$ @Mr.XCoder: Nuts, you're right! That's probably gonna cost me some bytes when I get a moment to fix it. \$\endgroup\$ – Shaggy Dec 20 '17 at 14:11
  • \$\begingroup\$ @Mr.Xcoder: Fixed for now, will have to come back later to see if I can improve on it. \$\endgroup\$ – Shaggy Dec 20 '17 at 14:52
0
\$\begingroup\$

APL+WIN, 37 bytes

 ↑1=⍒⌽(+/¨((0=(⍳¨n)|¨n)×⍳¨n)~¨⊂0)÷n←⍳⎕

Prompts for screen input.

\$\endgroup\$
0
\$\begingroup\$

C (gcc), 99 bytes

s(n,j,k){for(j=k=0;j++<n;)k+=n%j?0:j;n=k;}f(n,i,r){for(i=r=0;++i<n;)r=1.*s(n)/n<1.*s(i)/i?:r;r=!r;}

Try it online!

C, 108 bytes

float s(n,j,k){for(j=k=0;j++<n;)k+=n%j?0:j;return k;}f(n,i,r){for(i=r=0;++i<n;)s(n)/n<s(i)/i&&++r;return!r;}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ So, why does s need to return a float? \$\endgroup\$ – Nissa Dec 19 '17 at 15:31
  • \$\begingroup\$ @StephenLeppik To use float division instead of integer division when comparing s(n)/n to s(i)/i. \$\endgroup\$ – Steadybox Dec 19 '17 at 15:32
0
\$\begingroup\$

Swift, 120 118 bytes

let s={n in Float((1...n).reduce(0){n%$1>0 ?$0:$0+$1})}
{n in(1..<n).reduce(0){max($0,s($1)/Float($1))}<s(n)/Float(n)}

Takes some time (around 6 seconds on TIO) to compile because of the implicit type declarations in Swift.

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Jelly, 12 bytes

RÆs©Ṫ×R>®×$Ạ

Try it online! or Find all superabundant numbers below 1000.

because I hate floating points.

\$\endgroup\$
0
\$\begingroup\$

Funky, 79 bytes

d=n=>fors=i=0i<=n i++s+=i*!n%i
f=n=>{forc=1c<n c++if(d(n)/n)<=d(c)/c return0 1}

Explained

This first defines the function d which is the σ function, and this is the golfed version of

function d(n){
    var s = 0;
    for(var i=0; i<n; i++){
        if(n%i == 0){
            s += i;
        }
    }
    return s;
}

We can set i to 0, because i*n%0 will always equal 0*..., thus 0.

The next half of this defines the function f, which is the Superabandunce function, and it is just the golfed form of

function f(n){
    for(var c=1; c<n; c++){
        if( (d(n)/n) <= (d(c)/c) ){
            return 0;
        }
    }
    return 1;
}

And this just checks, as the challenge spec suggests, that all integers from 1 to n-1 have a d(n)/n of less than the input.

Try it online!

\$\endgroup\$
0
\$\begingroup\$

APL (Dyalog), 33 bytes

{⍵=⊃⌽+⌿∘.≤⍨((+/⍳(/⍨)0=⍳|⊢)÷⊢)¨⍳⍵}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Husk, 9 bytes

εü<m§ṁ/Ḋṫ

Try it online! Too slow for the 360360 test case.

Explanation

εü<m§ṁ/Ḋṫ  Implicit input, say n=6.
        ṫ  Decreasing range: [6,5,4,3,2,1]
   m       Map this function (example argument k=4):
       Ḋ    Divisors of k: [1,2,4]
    §ṁ      Map and sum
      /     division by k: 7/4
           Result: [2,6/5,7/4,4/3,3/2,1]
 ü         Remove duplicates by
  <        strict comparison. This greedily extracts a non-decreasing subsequence: [2]
ε          Is it a singleton list? Yes.
\$\endgroup\$
  • \$\begingroup\$ I got £ü¤<§ṁ/ḊN. Creating the entire list of superabundant numbers \$\endgroup\$ – H.PWiz Dec 20 '17 at 12:57
0
\$\begingroup\$

Perl 5, 84 bytes

say!grep$a[-1]<=$a[$_],0..(@a=map{$i=$_;my$j;map{$i%$_ or$j+=$_/$i}1..$i;$j}1..<>)-2

requires -E (free)

a straightforward implementation of the specification, golfed

\$\endgroup\$
0
\$\begingroup\$

APL(NARS), 61 chars, 122 bytes

r←f w;m;k
r←m←0
r+←1⋄k←r÷⍨11πr⋄→3×⍳r≥w⋄→2×⍳∼m<k⋄m←k⋄→2
r←k>m

11π is the function sum of factors

  (⍳9),¨ f¨1..9
1 1  2 1  3 0  4 1  5 0  6 1  7 0  8 0  9 0 
  f 360360
0
\$\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.