Sum of divisors

Given a positive integer, sum its positive divisors.

Task

Show the result for the first 100 positive integers.

Python

Using prime factorization

<lang Python>def factorize(n):

   assert(isinstance(n, int))
   if n < 0: 
       n = -n 
   if n < 2: 
       return 
   k = 0 
   while 0 == n%2: 
       k += 1 
       n //= 2 
   if 0 < k: 
       yield (2,k) 
   p = 3 
   while p*p <= n: 
       k = 0 
       while 0 == n%p: 
           k += 1 
           n //= p 
       if 0 < k: 
           yield (p,k)
       p += 2 
   if 1 < n: 
       yield (n,1)

def sum_of_divisors(n):

   assert(n != 0) 
   ans = 1 
   for (p,k) in factorize(n): 
       ans *= (pow(p,k+1) - 1)//(p-1) 
   return ans

if __name__ == "__main__":

   print([sum_of_divisors(n) for n in range(1,101)])</lang>

Finding divisors efficiently

<lang Python>def sum_of_divisors(n):

   assert(isinstance(n, int) and 0 < n)
   ans, i, j = 0, 1, 1
   while i*i <= n:
       if 0 == n%i:
           ans += i
           j = n//i
           if j != i:
               ans += j
       i += 1
   return ans

if __name__ == "__main__":

   print([sum_of_divisors(n) for n in range(1,101)])</lang>

Output:

[1, 3, 4, 7, 6, 12, 8, 15, 13, 18, 12, 28, 14, 24, 24, 31, 18, 39, 20, 42, 32, 36, 24, 60, 31, 42, 40, 56, 30, 72, 32, 63, 48, 54, 48, 91, 38, 60, 56, 90, 42, 96, 44, 84, 78, 72, 48, 124, 57, 93, 72, 98, 54, 120, 72, 120, 80, 90, 60, 168, 62, 96, 104, 127, 84, 144, 68, 126, 96, 144, 72, 195, 74, 114, 124, 140, 96, 168, 80, 186, 121, 126, 84, 224, 108, 132, 120, 180, 90, 234, 112, 168, 128, 144, 120, 252, 98, 171, 156, 217]

<lang rexx>/*REXX program displays the first N sum of divisiors. */ parse arg n . /*obtain optional argument from the CL.*/ if n== | n=="," then n= 100 /*Not specified? Then use the default.*/ say 'the sums of divisors for ' n " integers:"; say /*show what output is being shown*/ say '─index─' center(" sum of divisors ",70,'─') /*display a title for the tau numbers. */ w= max(7, length(n) ) /*W: used to align 1st output column. */ $= /*$: the output list, shown ten/line. */

          do j=1  for N                         /*process  N  positive integers.       */
          $= $  ||  right( commas(sigma(j)), 7) /*add a sigma (sum) to the output list.*/
          if j//10\==0  then iterate            /*Not a multiple of 10?  Don't display.*/
          say right(commas(j-9), 6)' '  $       /*display partial list to the terminal.*/
          $=                                    /*start with a blank line for next line*/
          end   /*j*/

if $\== then say center((j-1) // 10, 7) $ /*any residuals sums left to display? */ exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ? /*──────────────────────────────────────────────────────────────────────────────────────*/ iSqrt: procedure; parse arg x; q= 1; r= 0; do while q<=x; q= q*4; end

       do while q>1; q=q%4; _=x-r-q; r=r%2; if _>=0 then do;x=_;r=r+q; end; end; return r

/*──────────────────────────────────────────────────────────────────────────────────────*/ sigma: procedure; parse arg x; if x==1 then return 1; odd=x // 2 /* // ◄──remainder.*/

      s= 1 + x                                  /* [↓]  only use  EVEN or ODD integers.*/
            do k=2+odd  by 1+odd  while k*k<x   /*divide by all integers up to  √x.    */
            if x//k==0  then  s= s + k +  x % k /*add the two divisors to (sigma) sum. */
            end   /*k*/                         /* [↑]  %  is the REXX integer division*/
      if k*k==x  then  return s + k             /*Was  X  a square?   If so, add  √ x  */
                       return s                 /*return (sigma) sum of the divisors.  */</lang>

output when using the default input:

the sums of divisors for  100  integers:

─index─ ────────────────────────── sum of divisors ───────────────────────────
     1        1      3      4      7      6     12      8     15     13     18
    11       12     28     14     24     24     31     18     39     20     42
    21       32     36     24     60     31     42     40     56     30     72
    31       32     63     48     54     48     91     38     60     56     90
    41       42     96     44     84     78     72     48    124     57     93
    51       72     98     54    120     72    120     80     90     60    168
    61       62     96    104    127     84    144     68    126     96    144
    71       72    195     74    114    124    140     96    168     80    186
    81      121    126     84    224    108    132    120    180     90    234
    91      112    168    128    144    120    252     98    171    156    217