18
\$\begingroup\$

Two or more positive integers are said to be "friendly" if they have the same "abundancy". The abundancy of an positive integer \$n\$ is defined as $$\frac {\sigma(n)} n,$$ where \$\sigma(n)\$ is the sum of \$n\$'s divsors. For example, the abundancy of \$30\$ is \$\frac {12} 5\$ as

$$\frac {\sigma(30)} {30} = \frac {1 + 2 + 3 + 5 + 6 + 10 + 15 + 30} {30} = \frac {72} {30} = \frac {12} 5$$

Because \$140\$ has the same abundancy (\$\frac {12} 5\$), we know that \$30\$ and \$140\$ are "friendly". If a number does not have the same abundancy of any other numbers, it is termed a "solitary" number. For example, \$3\$'s abundancy is \$\frac 4 3\$ and it can be shown that no other number has an abundancy of \$\frac 4 3\$, so \$3\$ is solitary.

We can partition the positive integers into "clubs" of friendly numbers. For example, the perfect numbers form a club, as they all have abundancy \$2\$, and solitary numbers each form a club by themselves. It is currently unknown whether or not infinitely large clubs exist, or if every club is finite.


You are to take two positive integers \$n\$ and \$k\$, and output \$k\$ numbers in \$n\$'s club. You may assume that \$k\$ will never exceed the size of the club (so \$k\$ will always be \$1\$ for solitary numbers etc.). You may output any \$k\$ numbers, so long as they all belong to \$n\$'s club (note that this means you do not always have to output \$n\$). You may input and output in any reasonable format and manner - keep your golfing in your code, not your I/O.

A few remarks

  • You may assume that \$n\$ is known to be either friendly or solitary - you will never get e.g. \$n = 10\$.
  • It has been shown that if \$\sigma(n)\$ and \$n\$ are co-prime, \$n\$ is solitary, and so, in this case, \$k = 1\$.
  • Your answers may fail if values would exceed the limit of integers in your language, but only if that is the only reason for failing (i.e. if your language's integers were unbounded, your algorithm would never fail).
  • I am willing to offer a bounty for answers that also include a program that aims to be quick, as well as correct. A good benchmark to test against is \$n = 24, k = 2\$ as the smallest friendly number to \$24\$ is \$91963648\$

This is a challenge, so the shortest code in each language wins.


Test cases

Note that the outputs provided are, in some cases, sample outputs, and do not have to match your outputs

n, k -> output
3, 1 -> 3
6, 4 -> 6, 28, 496, 8128
8, 1 -> 8
24, 2 -> 24, 91963648
84, 5 -> 84, 270, 1488, 1638, 24384
140, 2 -> 30, 140
17360, 3 -> 210, 17360, 43400
\$\endgroup\$
4
  • \$\begingroup\$ Related. Brownie points for beating/tying my (incredibly slow) 15 byte Jelly answer \$\endgroup\$ Apr 10 at 12:42
  • \$\begingroup\$ Failure by e.g. passing the recursion limit is still allowed as normal, right? \$\endgroup\$
    – allxy
    Apr 10 at 19:51
  • \$\begingroup\$ @allxy Yes, as that's a practical limitation, not an algorithmic one \$\endgroup\$ Apr 10 at 19:51
  • 1
    \$\begingroup\$ Related? I'd say it's a dupe of this one considering the question quality... \$\endgroup\$
    – emanresu A
    Apr 11 at 7:01

15 Answers 15

12
\$\begingroup\$

Jelly, 11 10 bytes

-1 thanks to @Jonathan Allan.

1,Æs×ṭʋE¥#

Try it online!

Explanation

Jelly's # parsing is really confusing. # doesn't consume the first link 1, since it's a nilad. (This, as it turns out, works really weirdly if you use chain separators; the equivalent code would be ø1ð,,Æs$ÆḊ¬ð#.)

The code is essentially parsed from postfix notation to the following, where [] represent chains:

[1 #(filter=¥[ʋ[, Æs × ṭ] E])]

This chain is then applied to the arguments (n, k). The value is first initialized to n.

The # operation is then used as a dyad, as if it's the + in 1+. It receives (1, n) as arguments and starts passing those to its filter chain, incrementing the 1 until k matches are found. (Since # only consumed one link, the last command-line argument is used as the count.)

The filter chain then does this, where x is the candidate number:

  • ,: make pair [x, n].
  • Æs: compute [sigma(x), sigma(n)].
  • : make pair [n, x].
  • ×: elementwise multiply, i.e. [sigma(x)*n, sigma(n)*x].
  • E: see if the values equal. This is pretty clearly true iff x/sigma(x)=n/sigma(n).
\$\endgroup\$
3
  • \$\begingroup\$ Ah, clever use of the determinant! I was using a helper link to calculate the abundancy for each candidate number, and n \$\endgroup\$ Apr 10 at 16:44
  • 1
    \$\begingroup\$ You can save a byte by checking for equality of the products directly (rather than ÆḊ¬) like so: 1,Æs×ṭʋE¥# TIO. \$\endgroup\$ Apr 10 at 19:17
  • \$\begingroup\$ @JonathanAllan Ah, that's a cool way of (ab?)using . Thanks! \$\endgroup\$ Apr 10 at 19:52
5
\$\begingroup\$

Husk, 11 10 bytes

↑f¤=oṁ\Ḋ⁰N

Try it online!

↑f¤=S/oΣḊ⁰N
 f        N  # filter the natural numbers by
  ¤          # combin: '¤fgxy' means 'f(g x)(g y)', where
   =         #  f is '=' equals
    oṁ\Ḋ     #  g is 'oṁ\Ḋ', which parses as:
    o        #   compose 
     ṁ       #    map this & sum the results:
      \      #     reciprocal
       Ḋ     #    over each divisor of argument
        ⁰    #  x is the last input argument
             #  y is the number being filtered (so, each of the natural numbers)
↑            # finally, from the filtered numbers, take 
             # the first n equal to the other input argument.
\$\endgroup\$
4
\$\begingroup\$

Ruby, 90 79 bytes

->n,k{w=0;g=->w{(1..w).sum{|x|w%x<1?x:0}};k.times{g[w+=1]*n==g[n]*w||redo;p w}}

Try it online!

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

PARI/GP, 57 bytes

f(n,k)=i=0;while(k,sigma(n)/n-sigma(i++)/i||k-=!print(i))

Attempt This Online!

This is slow. It tries every positive integer one by one until it finds k answers. It takes 3 minutes to calculate f(24, 2) on my computer.

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

JavaScript (V8),  91 89 88  85 bytes

Saved 3 bytes thanks to @tsh

Expects (n)(k). Prints the numbers.

n=>k=>{for(g=x=>{for(q=d=x;--d;)x%d?0:q+=d},i=0;k;q*++i+~g(i)*q*n||print(i)|k--)g(n)}

Try it online!

Commented

n =>                   // n = positive integer
k => {                 // k = required number of solutions
  for(                 // main loop:
    g = x => {         //   g is a helper function loading sigma(x) in q
      for(             //   loop:
        q = d = x;     //     start with q = d = x
        --d;           //     decrement d and stop when d = 0
      ) x % d ? 0      //     add d to q if d is a divisor of x
              : q += d //
    },                 //   end
    i = 0;             //   start with i = 0
    k;                 //   stop when k = 0
    q * ++i +          //   increment i and test whether:
    ~g(i) * q * n ||   //     sigma(n) * i = sigma(i) * n
    print(i) | k--     //   if so, print i and decrement k
  ) g(n)               //   load sigma(n) in q
}                      // end
\$\endgroup\$
2
  • 1
    \$\begingroup\$ n=>k=>{for(g=x=>{for(q=d=x;--d;)x%d?0:q+=d},i=0;k;q*++i+~g(i)*q*n||print(i)|k--)g(n)} \$\endgroup\$
    – tsh
    Apr 11 at 2:48
  • \$\begingroup\$ Or -7 more bytes if recursion stack limit is allowed. \$\endgroup\$
    – tsh
    Apr 11 at 2:55
3
\$\begingroup\$

05AB1E, 10 bytes

µN‚ÂÑO*ËD–

Inputs in the order \$k,n\$, outputs the results on separated newlines to STDOUT.

Port of @PurkkaKoodari's Jelly answer.

Try it online or verify almost all test cases (times out for 2,24).

Explanation:

µ           # Loop while `¾` is not equal to the first (implicit) input-integer:
            # (`¾` is 0 by default)
 N‚         #  Pair the loop-index with the second (implicit) input-integer
   Â        #  Bifurcate it; short for Duplicate & Reverse copy
    Ñ       #  Map both values in the reversed copy to a list of its divisors
     O      #  Sum those inner lists of divisors
      *     #  Multiply it to the pair
       Ë    #  Check if both values in the pair are the same
        D   #  Duplicate this check
         –  #  Pop, and if this is truthy: print `N` with trailing newline
            #  (implicit - Pop, and if this is truthy: increase `¾` by 1)
\$\endgroup\$
1
3
\$\begingroup\$

R, 74 72 bytes

\(n,k,s=\(m,l=1:m)mean(l*!m%%l))while(k)s(F<-F+1)==s(n)&&{show(F);k=k-1}

Attempt This Online!

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

Charcoal, 44 bytes

NθNη≔⁰ζW‹ⅉη«≦⊕ζ¿⁼×ζΣΦ⊕θ∧κ¬﹪θκ×θΣΦ⊕ζ∧κ¬﹪ζκ⟦Iζ

Try it online! Link is to verbose version of code. Don't try any of the other test cases on TIO because it's too slow. Explanation:

NθNη

Input n and k.

≔⁰ζ

Start enumerating the club.

W‹ⅉη«

Repeat until k numbers have been output.

≦⊕ζ

Increment the number to be tested.

¿⁼×ζΣΦ⊕θ∧κ¬﹪θκ×θΣΦ⊕ζ∧κ¬﹪ζκ

If it's in the club, then...

⟦Iζ

... output it on its own line.

Save 2 bytes by dropping support for n=1:

NθNη≔¹ζW‹ⅉη«≦⊕ζ¿⁼×ζΣΦθ∧κ¬﹪θκ×θΣΦζ∧κ¬﹪ζκ⟦Iζ

Try it online! Link is to verbose version of code.

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

Desmos, 122 bytes

o->join(o,a),T->T+sign(k-o.length)
n=\ans_0
k=\ans_1
o=[]
T=0
a=\{f(T)=f(n):[T],[]\}
f(K)=\sum_{N=1}^K\{\mod(K,N)=0,0\}N/K

Input in the first two lines of the graph (n on the first line, k on the second)

Output is the value of o after the program has completely ran (which is when T stops incrementing)

Try It On Desmos!

Try It On Desmos! - Prettified

\$\endgroup\$
2
  • \$\begingroup\$ I'm not 100% confident on this, but I think with the input rules of Desmos you don't have to include the lines n=\ans_0 and k=\ans_1, and you can assume those two variables are defined as the input elsewhere. \$\endgroup\$
    – Bbrk24
    Apr 15 at 17:21
  • \$\begingroup\$ @Bbrk24 I am simply following this default I/O method. Also, hardcoding input is generally discouraged. Also see this. \$\endgroup\$
    – Aiden Chow
    Apr 15 at 23:08
2
\$\begingroup\$

05AB1E, 9 bytes

µN‚ÑzOËD–

Try it online!

Uses that simplification that the "sum of divisors of x, divided by x" is just equal to "sum of reciprocals of divisors of x".
Apart from this, the rest of the 05AB1E nuts & bolts are shamefully stolen from Kevin Cruijssen's answer.

\$\endgroup\$
1
\$\begingroup\$

Factor + lists.lazy math.primes.factors math.unicode, 78 bytes

[ [ dup divisors Σ swap / ] tuck call '[ @ _ = ] 1 lfrom swap lfilter ltake ]

Try it online!

Explanation

Naive algorithm. Takes input as k n and returns a k-long lazy list containing numbers in the same club as n.

                           ! 4 6
[ dup divisors Σ swap / ]  ! 4 6 [ dup divisors Σ swap / ]  (push abundancy function)
tuck                       ! 4 [ dup divisors Σ swap / ] 6 [ dup divisors Σ swap / ]
call                       ! 4 [ dup divisors Σ swap / ] 2
'[ @ _ = ]                 ! 4 [ dup divisors Σ swap / 2 = ]
1 lfrom                    ! 4 [ dup divisors Σ swap / 2 = ] L{ 1 2 3 ... }
swap                       ! 4 L{ 1 2 3 ... } [ dup divisors Σ swap / 2 = ]
lfilter                    ! 4 L{ 6 28 496 8128 ... }
ltake                      ! L{ 6 28 496 8128 }
\$\endgroup\$
1
\$\begingroup\$

Python, 116 bytes

def f(n,k):
 x=lambda n:sum([i for i in range(1,n+1)if n%i==0])/n;i=1
 while k:
  if x(i)==x(n):print(i);k-=1
  i+=1

Pretty basic but painfully slow. Calculates the abundancy of each integer from 1 to n using the x function until the chosen number of matches have been found.

\$\endgroup\$
1
\$\begingroup\$

Python 3, 109 bytes

a=lambda n:sum(-~i*(n%-~i<1)for i in range(n))/n
def f(n,k,i=1):
 if a(n)==a(i):print(i);k-=1
 f(n,k*k/k,i+1)

Try it online!

A little longer one-liner,

def f(n,k,i=1,a=lambda n:sum(-~i*(n%-~i<1)for i in range(n))/n):print(end=(f"{[i,k:=k-1][0]}\n"if a(n)==a(i)else""));f(n,k*k/k,i+1)

Both functions always ends in a error(division by 0) after printing the answers.

\$\endgroup\$
1
\$\begingroup\$

Haskell, 85 bytes

f=fromIntegral
a n=f(sum[y|y<-[1..n],n`mod`y==0])/f n
n!k=take k[x|x<-[1..],a n==a x]

Attempt This Online!

! is the infix function that implements the friendly club function.

Some testcases are commented out because this is very slow.

-3 bytes from caird.

\$\endgroup\$
2
  • \$\begingroup\$ Can you use something like # as a function name instead of ab? \$\endgroup\$ Apr 16 at 10:59
  • \$\begingroup\$ i could use a single letter name. dunno about #, better to ask in chat. \$\endgroup\$
    – Razetime
    Apr 16 at 13:25
1
\$\begingroup\$

C (gcc), 99 bytes

d;c;s(n){for(d=c=n;--d;)c+=n%d?0:d;d=c;}i;f(n,k){for(i=1;k;++i)s(n)*i-n*s(i)?:printf("%d ",i,--k);}

Try it online!

\$\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.