16
\$\begingroup\$

Let \$\sigma(n)\$ represent the divisor sum of \$n\$ and \$\sigma^m(n)\$ represent the repeated application of the divisor function \$m\$ times.

Perfect numbers are numbers whose divisor sum equals their double or \$\sigma(n) = 2n\$. For example, \$\sigma(6) = 12 = 2\times6\$

Superperfect numbers are numbers whose twice iterated divisor sum equals their double. For example, \$\sigma^2(16) = \sigma(\sigma(16)) = \sigma(31) = 32 = 2\times16\$

\$m\$-superperfect numbers are numbers such that \$\sigma^m(n) = 2n\$ for \$m \ge 1\$. For \$m \ge 3\$, there are no such numbers.

\$(m,k)\$-perfect numbers are numbers such that \$\sigma^m(n) = kn\$. For example, \$\sigma^3(12) = 120 = 12\times10\$, so \$12\$ is a \$(3,10)\$-perfect number.

You are to choose one of the following three tasks to do:

  • Take three positive integers \$n, m, k\$ and output the \$n\$th \$(m,k)\$-perfect number (0 or 1 indexed, your choice)
  • Take three positive integers \$n, m, k\$ and output the first \$n\$ \$(m,k)\$-perfect numbers
  • Take two positive integers \$m, k\$ and output all \$(m,k)\$-perfect numbers

You may assume that the inputs will never represent an impossible sequence (e.g. \$m = 5, k = 2\$) and that the sequences are all infinite in length. You may take input in any convenient method.

Note that methods that count up starting from either \$m\$ or \$k\$ are not valid, as they fail for \$(4,4)\$-perfect numbers, the smallest of which is \$2\$ (credit to Carl Schildkraut for finding this)

This is so the shortest code in bytes wins.


Test cases

This lists the first few outputs\${}^*\$ for example inputs of \$(m, k)\$

m, k -> out
3, 10 -> 12, 156, 32704, ...
2, 2 -> 2, 4, 16, 64, 4096, 65536, ...
1, 2 -> 6, 28, 496, 8128, ...
4, 48 -> 160, 455, 5920, ...
3, 28 -> 4480, ...
3, 16 -> 294, 6882, ...
1, 4 -> 30240, 32760, ...
4, 4 -> 2, ...

\${}^*\$: Aka, the outputs I could get from my generating program without timing out on TIO

\$\endgroup\$
1

15 Answers 15

5
\$\begingroup\$

PowerShell, 95 92 87 bytes

-8 bytes thanks to mazzy!

This takes two parameters, m and k, and calculates all (m,k) perfect numbers (up to the maximum for a 64-bit signed integer).

param($m,$k)for(;$n=++$x){1..$m|%{$a=0;1..$n|%{$a+=$_*!($n%$_)};$n=$a}
,$x*!($a-$k*$x)}

Try it online!

\$\endgroup\$
4
  • 2
    \$\begingroup\$ $x=1 instead $x=$n=1? \$\endgroup\$
    – mazzy
    Mar 1, 2021 at 18:25
  • \$\begingroup\$ @mazzy Good spot! \$\endgroup\$ Mar 1, 2021 at 18:31
  • \$\begingroup\$ $x=1 is redundant. and ,$x*!($a-$k*$x) instead ,$x*($a-eq$k*$x). Try it online!. thanks Zaelin, smart solution \$\endgroup\$
    – mazzy
    Mar 1, 2021 at 19:04
  • \$\begingroup\$ Ahhhh, I had the x=1 in there because I was testing it in a console, so x needed reset every time; definitely wouldn't have thought to cut it; smart saves! Thanks again @mazzy! \$\endgroup\$ Mar 1, 2021 at 19:11
5
\$\begingroup\$

05AB1E, 11 10 bytes

-1 byte thanks to Kevin Cruijssen!

Outputs the infinite sequence given \$m\$ and \$k\$.

∞ʒ¹FÑO}y/Q

Try it online!

∞            # push an infinite list of positice integers
 ʒ           # iterate over the list and keep y if:
  ¹          # push the first input m
   F  }      # iterate m times:
    ÑO       # take sum O of divisors Ñ
             # sigma^m(y)
       y/    # divide by y
         Q   # is this equal to the second input k?
             # sigma^m(y) / y == k
\$\endgroup\$
4
  • \$\begingroup\$ I'm not entirely sure, but I think you can remove the ² and use implicit inputs. It will in that case incorrectly multiply the first input \$m\$ with \$1\$ in the first iteration, but I think (based on the test cases, so I'm not sure) \$1\$ will never be in the output anyway, so it shouldn't matter. But it's likely a counter-example could be found where it might incorrectly result in truthy for \$1\$ if you have \$m\$ instead of \$k\$ in the first iteration? Not sure how to prove or disprove my hunch. \$\endgroup\$ Mar 12, 2021 at 10:13
  • 1
    \$\begingroup\$ @KevinCruijssen this fails for \$m=1\$ and any \$k>1\$ as \$\sigma(1)=1\$. I remember spending some time on trying to use implicit input here without success. \$\endgroup\$
    – ovs
    Mar 12, 2021 at 10:58
  • 1
    \$\begingroup\$ Hmm, and if you swap the two, and use the implicit second input after dividing by the current number at the end: ∞ʒ¹FÑO}y/Q? (Not sure how floating point inaccuracies might affect the results, though.) \$\endgroup\$ Mar 12, 2021 at 11:09
  • 1
    \$\begingroup\$ @KevinCruijssen thanks a lot, this does work :). And as long as k is reasonably small, no floating point issues should occur. \$\endgroup\$
    – ovs
    Mar 12, 2021 at 11:25
3
\$\begingroup\$

Jelly, 9 bytes

1Æs⁴¡÷¥Ƒ#

A full program accepting k m n which prints a list representation of the first n \$k\$-\$m\$-generalised-perfect-numbers.

Try it online!

How?

1Æs⁴¡÷¥Ƒ# - Main Link: k
1       # - count up from j=1 & find the first (3rd argument, n) truthy results of f(j, k):
       Ƒ  -   is (j) invariant under?:
      ¥   -     last two links as a dyad - g(j, k):
    ¡     -       repeated application...
   ⁴      -         ...number of times: 1st argument, m
 Æs       -         ...action: divisor sum
     ÷    -       divide (by k)
\$\endgroup\$
6
  • \$\begingroup\$ Is it guaranteed that k will always be less than or equal to the first output? If so, I think I can save a byte on mine \$\endgroup\$ Mar 1, 2021 at 20:08
  • \$\begingroup\$ I thought so as I wrote the code, but now I'm not so sure... deleting for now. \$\endgroup\$ Mar 1, 2021 at 21:00
  • \$\begingroup\$ @cairdcoinheringaahing I've rewritten to start counting up from \$m\$, but I do feel like \$k\$ might actually be OK (but can't prove it). Can you save 1 by counting up from \$k\$? \$\endgroup\$ Mar 2, 2021 at 13:54
  • \$\begingroup\$ Unfortunately neither \$m\$ nor \$k\$ are valid starts, as demonstrated in this Math.SE question: \$2\$ is a \$(4,4)\$-perfect number. I’ll add that as an example test case when I get back to a computer \$\endgroup\$ Mar 2, 2021 at 14:37
  • 2
    \$\begingroup\$ Mine was this actually, but nice use of Ƒ! \$\endgroup\$ Mar 2, 2021 at 18:05
3
\$\begingroup\$

Husk, 14 bytes

fS=ö/⁰!²t¡oΣḊN

Try it online!

Outputs the infinite sequence of (m [arg1], k [arg2])-perfect numbers. TIO header gets just the first two terms, to avoid timing-out.

             N   # from the sequence N of all integers, 
f                # output the elements that are truthy with this function:
         ¡o      # construct an infinite list by repeatedly getting
           ΣḊ    # the sum of divisors;
        t        # discard the first element,
      !²         # and get the element at index given by arg1,
    /⁰           # then divide it by arg2,
 S=ö             # and check whether it's equal to the original number
\$\endgroup\$
2
\$\begingroup\$

Scala -language:postfixOps, 80 bytes

m=>k=>Stream from 2 filter(n=>(n/:1.to(m))((n,_)=>1 to n filter(n%_<1)sum)==k*n)

Try it online!

Outputs all (m, k)-perfect numbers. The flag just saves a couple bytes, but why not use it?

m=>k=>                     //Curried arguments
  Stream from 2            //Infinite stream of integers starting at 2
    filter(n=>             //Filter every n in the Stream according to this predicate
      k*n==                  //Check if k * n equals
                              //The iterated divisor sum
        (n/:1.to(m))          //Fold left over the range [1..m] starting with n
                              //We don't actually care about the values in [1..m], it's just to repeatedly find the divisor sum
          ((n,_)=>              //Find the divisor sum of the left argument:
            1 to n               //Range [1..n] of possible divisors
              filter(n%_<1)      //Filter the ones that divide n
              sum                //Sum them
          )
  )
\$\endgroup\$
2
\$\begingroup\$

Python 3, 139 123 bytes

g=lambda n,m:m and g(n+sum(i*(n%i<1)for i in range(1,n)),m-1)or n
f=lambda m,k,n,x=1:n and f(m,k,n-(g(x,m)==k*x),x+1)or x-1

Try it online!

Very direct approach, brute-forces for every number and runs until a result is found.

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

Wolfram Language (Mathematica), 49 bytes

outputs all (m,k)

Do[Nest[Tr@*Divisors,n,#]==n#2&&Print@n,{n,∞}]&

Try it online!

-3 bytes from @att

\$\endgroup\$
1
  • \$\begingroup\$ 49 bytes \$\endgroup\$
    – att
    Mar 1, 2021 at 19:13
2
\$\begingroup\$

Python 2, 94 bytes

Takes two positive integers \$ m,k \$ and outputs all \$(m,k)\$-perfect numbers.

def f(m,k,n=1):
 s=n;exec"i=t=s\nwhile~-i:i-=1;s+=i>>t%i*t\n"*m
 if s==k*n:print n
 f(m,k,n+1)

Try it online!

A straightforward implementation of the problem. The one obfuscation used is the s+=i>>t%i*t, which is equivalent to s+=i*(t%i<1), or if t%i<1:s+=i.

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

Stax, 13 bytes

ü╩╔◘8┌╜♀ñêP=e

Run and debug it

the divisor sum part takes a lot of space due to two byte builtins.

Outputs the sequence for m,k infinitely.

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

JavaScript (V8), 119 bytes

f=(m,k,i=1)=>((g=x=>(s=[...Array(x+1).keys()].reduce((a,b)=>a+(x%b<1)*b),--t?g(s):s))(i,t=m)==k*i&&print(i),f(m,k,i+1))

Try it online!

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

JavaScript (ES6), 86 bytes

Expects (m,k,n) and returns the \$n\$th \$(m,k)\$-perfect number (1-indexed).

(m,k,n)=>{for(i=0;n;n-=s==i*k)for(M=m,s=++i,d=0;d||(j=d=s,M--);)s+=j%--d?0:d;return i}

Try it online!

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

Haskell, 76 bytes

f m k n=take n[r|r<-[1..],r*k==iterate(\a->sum[x|x<-[1..a],a`mod`x==0])r!!m]

Try it online!

  • returns first n terms
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 43 bytes

NθNηNζ≔¹εW‹ⅉθ«≦⊕ε≔εδFη≔ΣΦ…·¹δ¬﹪δλδ¿⁼δ×εζ⟦Iε

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

NθNηNζ

Input n, m and k.

≔¹ε

Initialise the loop at one.

W‹ⅉθ«

Repeat until n values have been output.

≦⊕ε

Try the next integer.

≔εδ

Make a copy of it.

Fη

Repeat m times...

≔ΣΦ…·¹δ¬﹪δλδ

... replace the copy with the sum of its divisors.

¿⁼δ×εζ

If the result is k times the loop counter, ...

⟦Iε

Output the loop counter on its own line.

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

Clojure, 112 bytes

#(rest(for[i(range):when(=(* %2 i)(nth(iterate(fn[j](apply + j(for[k(range 1 j):when(=(rem j k)0)]k)))i)%1))]i))

Try it online!

Anonymous function that returns an infinite lazy sequence of all \$(m,k)\$-perfect numbers.

Test suite extracts \$n\$ first members of the sequences, albeit a bit fewer than in the task specification in order to fit within a minute on TIO.

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

Japt, 18 16 bytes

È*V¥_â x}g[X]}iW

Try it

Prints nth element 1-indexed

1st input(U) = m
2nd input(V) = k
3rd input(W) = n

@ ... }iW   - return W-th number that satisfy Om(n)==kn
_â x}         - sum of divisors
     g[X]     - repeated U times starting with X
         ¥X*V - ==kn ?
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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