38
\$\begingroup\$

Background:

The current Perfect Numbers challenge is rather flawed and complicated, since it asks you to output in a complex format involving the factors of the number. This is a purely repost of the challenge.

Challenge

Given a positive integer through any standard input format, distinguish between whether it is perfect or not.

A perfect number is a number that is equal to the sum of all its proper divisors (its positive divisors less than itself). For example, \$6\$ is a perfect number, since its divisors are \$1,2,3\$, which sum up to \$6\$, while \$12\$ is not a perfect number since its divisors ( \$1,2,3,4,6\$ ) sum up to \$16\$, not \$12\$.

Test Cases:

Imperfect:
1,12,13,18,20,1000,33550335

Perfect:
6,28,496,8128,33550336,8589869056

Rules

  • Your program doesn't have to complete the larger test cases, if there's memory or time constraints, but it should be theoretically able to if it were given more memory/time.
  • Output can be two distinct and consistent values through any allowed output format. If it isn't immediately obvious what represents Perfect/Imperfect, please make sure to specify in your answer.
\$\endgroup\$
6
  • 3
    \$\begingroup\$ @Tvde1 Proper divisors have to less than the number, otherwise no number other than 1 would be perfect, since every number is divisible by 1 and itself. The sum of proper divisors of 1 is 0 \$\endgroup\$
    – Jo King
    Mar 12, 2019 at 7:40
  • 1
    \$\begingroup\$ Are we allowed to assume there are no odd perfect numbers? \$\endgroup\$
    – Grimmy
    Mar 12, 2019 at 8:56
  • 5
    \$\begingroup\$ @Grimy Only if you can prove so. Good luck! (though I'm wondering how that would save bytes) \$\endgroup\$
    – Jo King
    Mar 12, 2019 at 9:15
  • 2
    \$\begingroup\$ So no, too bad. It would cut the size of an ECMA regex answer by a factor of about 3. \$\endgroup\$
    – Grimmy
    Mar 12, 2019 at 9:18
  • 3
    \$\begingroup\$ "Output can be two distinct and consistent values" - may we not use "truthy vs falsey" here (e.g. for Python using zero vs non zero; a list with content vs an empty list; and combinations thereof)? \$\endgroup\$ Mar 12, 2019 at 10:15

66 Answers 66

3
\$\begingroup\$

MATL, 5 bytes

EGZ\s=

Try it out at MATL Online

Explanation

      % Implicitly grab the input as an integer
      %    STACK: { 6 }
E     % Multiply by two
      %    STACK: { 12 }
G     % Grab the input again
      %    STACK: { 12,  6 }
Z\    % Compute all divisors (including itself)
      %    STACK: { 12,  [1, 2, 3, 6] }
s     % Sum up these divisors
      %    STACK: { 12, 12 }
=     % Check that the two elements on the stack are equal
      %    STACK: { 1 }
      % Implicitly display the result
\$\endgroup\$
3
\$\begingroup\$

Fig, \$3\log_{256}(96)\approx\$ 2.469 bytes

=Sk

Try it online!

=Sk
 S  # Does the sum
  k # Of the divisors
=   # Equal the input?
\$\endgroup\$
3
\$\begingroup\$

Qi, 72 bytes (45 characters + 22 brackets)

(λ(n)((☯(~> △(pass(~>(/ n _)integer?))+(= n)))(cdr(range n 0 -1))))

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

PowerShell, 84 bytes

param($n)1..[math]::sqrt($n)|%{$a+=$_,($n/$_)*!($n%$_)};$n-eq(($a|gu)-join"+"|iex)/2

Try it online!

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

CJam, 17 bytes

ri_,(;{1$\%!},:+=

Try it online!

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

Javascript, 62

n=>n==[...Array(n).keys()].filter(a=>n%a<1).reduce((a,b)=>a+b)

Explanation (although it's pretty simple)

n=> //return function that takes n
  n== //and returns if n is equal to
    [...Array(n).keys()] //an array [0..(n-1)]...
      .filter(a=>n%a<1) //where all of the elements that are not divisors of n are taken out...
      .reduce((a,b)=>a+b) //summed up

Thanks to Jo King for the improvement!

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

05AB1E, 4 bytes

ѨOQ

Try it online!

Explanation

  O    # the sum
Ñ      # of the divisors of the input
 ¨     # with the last one removed
   Q   # equals the input
\$\endgroup\$
2
\$\begingroup\$

Batch, 81 bytes

@set s=-%1
@for /l %%i in (1,1,%1)do @set/as+=%%i*!(%1%%%%i)
@if %s%==%1 echo 1

Takes n as a command-line parameter and outputs 1 if it is a perfect number. Brute force method, starts the sum at -n so that it can include n itself in the loop.

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

Charcoal, 13 bytes

Nθ⁼θΣΦθ∧ι¬﹪θι

Try it online! Link is to verbose version of code. Outputs - for perfect numbers. Uses brute force. Explanation:

Nθ              Numeric input
     Φθ         Filter on implicit range
        ι       Current value (is non-zero)
       ∧        Logical And
           θ    Input value
          ﹪     Modulo
            ι   Current value
         ¬      Is zero
    Σ           Sum of matching values
  ⁼             Equals
   θ            Input value
\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 14 bytes

PerfectNumberQ

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Yes, Mathematica! Another built-in. \$\endgroup\$
    – tsh
    Mar 12, 2019 at 10:21
2
\$\begingroup\$

Pyth, 8 bytes

qs{*MPyP

Try it online here.

qs{*MPyPQQ   Implicit: Q=eval(input())
             Trailing QQ inferred
       PQ    Prime factors of Q
      y      Powerset
     P       Remove last element - this will always be the full prime factorisation
   *M        Take product of each
  {          Deduplicate
 s           Sum
q        Q   Is the above equal to Q? Implicit print
\$\endgroup\$
2
\$\begingroup\$

Powershell, 46 bytes 43 bytes

param($i)1..$i|%{$o+=$_*!($i%$_)};$o-eq2*$i

Try it Online!

Edit: -3 bytes thanks to @AdmBorkBork

\$\endgroup\$
1
  • \$\begingroup\$ 43 bytes by rolling the accumulator into the loop and checking against 2*$i to eliminate the subtract-one parens. \$\endgroup\$ Mar 12, 2019 at 12:42
2
\$\begingroup\$

Java 8, 66 bytes


Someone has to use the stream API at some point, even if there's a shorter way to do it

n->java.util.stream.IntStream.range(1,n).filter(i->n%i<1).sum()==n

Try it online!

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

cQuents, 8 bytes

?#N=U\zN

Try it online!

Explanation

?           Mode query: return whether or not input is in sequence
 #          Conditional: iterate N, add N to sequence if condition is true
  N=         Condition: N == 
    U    )                   sum(                  )
     \z )                        proper_divisors( )
       N                                         N
        ))    implicit
\$\endgroup\$
2
\$\begingroup\$

Smalltalk, 34 bytes

((1to:n-1)select:[:i|n\\i=0])sum=n
\$\endgroup\$
2
\$\begingroup\$

Factor, 57 bytes

: f ( x -- ? ) dup [1,b) [ dupd divisor? ] filter sum = ;

Try it online!

There is a shorter solution on the Rosetta Code that uses the divisors builtin:

: f ( n -- ? )  [ divisors sum ] [ 2 * ] bi = ;

but I wanted to come up with my own solution.

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

Racket, 54 bytes

(require math)(define(p n)(=(sum(divisors n))(* 2 n)))

Try it online!

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

APL(NARS), chars 11, bytes 22

{⍵=2÷⍨11π⍵}

11π return the sum of all divisors, test:

  f←{⍵=2÷⍨11π⍵}
  f¨1 12 13 18 20 1000 33550335
0 0 0 0 0 0 0 
  f¨6 28 496 8128 33550336 8589869056
1 1 1 1 1 1 
\$\endgroup\$
2
\$\begingroup\$

Retina 0.8.2, 44 40 bytes

crossed out 44 is still regular 44

.+
$*
M!&`(.+)$(?<=^\1+)
1>`¶

^(1+)¶\1$

Try it online! Edit: Saved 4 bytes thanks to @Deadcode. Still somewhat slow, so link excludes largest test cases. Explanation:

.+
$*

Convert to unary.

M!&`(.+)$(?<=^\1+)

Match all factors of the input. This uses overlapping mode, which in Retina 0.8.2 requires all of the matches to start at different positions, so the matches are actually returned in descending order, starting with the original input.

1>`¶

Delete all of the newlines except for the first. This sums together the proper factors, leaving the original input and sum of factors.

^(1+)¶\1$

Test whether they are the same.

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

MMIX, 48 bytes (12 instrs)

(jxd¹ -T)

00000000: 27010001 f7010000 e3020000 1eff0001  '¢¡¢ẋ¢¡¡ẉ£¡¡œ”¡¢
00000010: feff0006 72ffff01 220202ff 27010101  “”¡©r””¢"££”'¢¢¢
00000020: 5b01fffb 32000002 73000001 f8010000  [¢”»2¡¡£s¡¡¢ẏ¢¡¡

Disassembly:

perf    SUBU $1,$0,1        // i = n - 1
        PUT  rD,0           // zero out hidiv register
        SETL $2,0           // s = 0
0H      DIVU $255,$0,$1     // loop: t:rR = rD:n /% i
        GET  $255,rR        // t = rR
        ZSZ  $255,$255,$1   // t = t? 0 : i
        ADDU $2,$2,$255     // s += i
        SUBU $1,$1,1        // i--
        PBNZ $1,0B          // iflikely(i) goto loop
        CMPU $0,$0,$2       // r = n <=> s
        ZSZ  $0,$0,1        // r = !r
        POP  1,0            // return r

The best part of this is that the only branch in the whole thing is to do a loop. Testing the division is handled by the ZSZ instruction (which is also used later to handle a negation).

I could save an instruction if I were allowed to return different results for abundant and deficient numbers.

  1. jxd is a program I wrote, available on request; it is like xxd, but with support for only jelly and 05AB1E codepages (and no -p or -r support, it would be redundant).
\$\endgroup\$
2
\$\begingroup\$

Thunno D, \$ 5 \log_{256}(96) \approx \$ 4.12 bytes

fZHS=

Attempt This Online!

Explanation

fZHS=  # D flag duplicates input
f      # Factors, including 1 and input
 ZH    # Without last item (input)
   S   # Sum this list
    =  # Equal to the input?
       # Implicit output
\$\endgroup\$
2
\$\begingroup\$

Pip, 16 bytes

a=$+Y{!\a%a}FI,a

Attempt This Online!

There's no factors builtin so we have to implement it ourselves

a=$+Y{!\a%a}FI,a    ; input on command line
              ,a    ; range(input)
     {     }FI      ; filtered by:
       \a%a         ;  the input mod this number
      !             ;  logical not
  $+Y               ; sum of the list
a=                  ; equals the input?
\$\endgroup\$
2
\$\begingroup\$

Arturo, 25 24 bytes

$=>[=∑chop factors<=&]

Try it

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

Pyt, 5 bytes

ĐðƩ₂=

Try it online!

Returns True if perfect, False otherwise

Đ             implicit input; Đuplicate
 ð            get ðivisors
  Ʃ           Ʃum
   ₂          divide by two
    =         is it equal to the input; implicit print
\$\endgroup\$
2
\$\begingroup\$

Stax, 6 bytes

ôxⁿ♪σ▀

Run and debug it

This is PackedStax, which unpacks to the following 7 bytes:

:dNs|+=

Run and debug it

Explanation

:d      # divisors
  N     # minus the last item (which is equal to the input)
    |+  # summed
      = # is equal to
   s    # the input

Times out for larger test cases on the online interpreter.

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

Bash, 56 bytes

Maybe a recursive function will be shorter? My Bash is certainly not strong.

s=0;for ((;v++<$1;)){ $[s+=($1%$v<1)*$v-1];};[ $s = $1 ]

A full program taking a command line argument which has a return code 0 if it was perfect and 1 otherwise.

Try it online!

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

Haskell, 35 bytes

f x=x==sum[y|y<-[1..x-1],x`mod`y<1]

Try it online!

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

Twig, 108 bytes

Yeah, I managed to get something longer than Java :/

This creates a macro that you import into your own template and call the method a

{%macro a(n,x=0)%}{%if n>1%}{%for i in 1..n-1%}{%set x=x+i*(n%i==0)%}{%endfor%}{{x==n}}{%endif%}{%endmacro%}

Returns 1 for perfect numbers, nothing for imperfect.

You can try it on https://twigfiddle.com/0or03v (testcases included)

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

MACHINE LANGUAGE(X86, 32 bit), 38 bytes

00000788  53                push ebx
00000789  8B442408          mov eax,[esp+0x8]
0000078D  31DB              xor ebx,ebx
0000078F  31C9              xor ecx,ecx
00000791  43                inc ebx
00000792  39C3              cmp ebx,eax
00000794  730E              jnc 0x7a4
00000796  31D2              xor edx,edx
00000798  50                push eax
00000799  F7F3              div ebx
0000079B  58                pop eax
0000079C  09D2              or edx,edx
0000079E  75F1              jnz 0x791
000007A0  01D9              add ecx,ebx
000007A2  EBED              jmp short 0x791
000007A4  29C8              sub eax,ecx
000007A6  0F94C0            setz al
000007A9  0FB6C0            movzx eax,al
000007AC  5B                pop ebx
000007AD  C3                ret
000007AE

Function lenght: 7AEh-788h=26h=38d; below assembly file that generate obj for linking:

; nasmw -fobj  this.asm
; bcc32 -v  file.c this.obj
section _DATA use32 public class=DATA
global _sumd
section _TEXT use32 public class=CODE

_sumd:    
      push    ebx
      mov     eax,  dword[esp+  8]
      xor     ebx,  ebx
      xor     ecx,  ecx
.1:   inc     ebx
      cmp     ebx,  eax
      jae     .2
      xor     edx,  edx
      push    eax
      div     ebx
      pop     eax
      or      edx,  edx
      jnz     .1
      add     ecx,  ebx
      jmp     short  .1
.2:   sub     eax,  ecx
      setz    al
      movzx   eax,  al
      pop     ebx
      ret

below the C file for link and test that function:

#include <stdio.h>
unsigned es[]={1,12,13,18,20,1000,33550335,6,28,496,8128,33550336,0};
int sumd(unsigned);

main(void)
{int  i;
 for(i=0;es[i];++i)
    printf("f(%u)=%u\n",es[i],sumd(es[i]));    
 return 0;
}

below the macro assembly file source of the .asm one:

; nasmw -fobj  this.asm
; bcc32 -v  file.c this.obj
section _DATA use32 public class=DATA
global  _sumd
section _TEXT use32 public class=CODE

_sumd:
<b  |a=^8|b^=b|c^=c
.1:  ++b |b>=a#.2|r^=r|<a|div b|>a|r|=r|jnz .1|c+=b|#.1
.2:  a-=c|setz al|movzx eax, al
>b
ret

below the 113 bytes golfing code of above:

_sumd:<b|a=^8|b^=b|c^=c|.1:++b|b>=a#.2|r^=r|<a|div b|>a|r|=r|jnz .1|c+=b|#.1|.2:a-=c|setz al|movzx eax, al|>b|ret

the results:

f(1)=0
f(12)=0
f(13)=0
f(18)=0
f(20)=0
f(1000)=0
f(33550335)=0
f(6)=1
f(28)=1
f(496)=1
f(8128)=1
f(33550336)=1

I got the trick of use push eax|div | pop eax from https://codegolf.stackexchange.com/a/181515/58988

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

C++ (clang), 55 bytes

[](long n){long i,s;for(i=s=n;--i;n%i?:s-=i);return!s;}

Try it online!

Can handle 8589869056 just fine thanks to the use of long, but this input is not included in the TIO as it takes more than 60 seconds to process. (On my i7-4930K @ 4.1 GHz it takes 65 seconds.)

This has a golf optimization that can't be done in C – n%i?:s-=i, using not only the GNU extension of allowing the true or false field of a ternary to be empty, but taking advantage of the fact that in C++, ?: and -= have the same operator precedence with right-to-left associativity – whereas in C ?: has a higher precedence than -=, so the only way to make it work would be as n%i?:(s-=i) and then it'd cost 1 byte over s-=n%i?0:i rather than saving 1 byte.

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