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]
Choosing the right abstraction
This is really an exercise in defining a divisors function, and the only difference between the suggested Sum and Product draft tasks boils down to two trivial morphemes:
reduce(add, divisors(n), 0) vs reduce(mul, divisors(n), 1)
The goal of Rosetta code (see the landing page) is to provide contrastive insight (rather than comprehensive coverage of homework questions :-). Perhaps the scope for contrastive insight in the matter of divisors is already exhausted by the trivially different Proper divisors task.
<lang python>Sums and products of divisors
from math import floor, sqrt from functools import reduce from operator import add, mul
- divisors :: Int -> [Int]
def divisors(n):
List of all divisors of n including n itself.
root = floor(sqrt(n))
lows = [x for x in range(1, 1 + root) if 0 == n % x]
return lows + [n // x for x in reversed(lows)][
(1 if n == (root * root) else 0):
]
- ------------------------- TEST -------------------------
- main :: IO ()
def main():
Sums and products of divisors for each integer in range [1..50]
print('Products of divisors:')
for n in range(1, 1 + 50):
print(n, '->', reduce(mul, divisors(n), 1))
print('Sums of divisors:')
for n in range(1, 1 + 100):
print(n, '->', reduce(add, divisors(n), 0))
- MAIN ---
if __name__ == '__main__':
main()</lang>
REXX
<lang rexx>/*REXX program displays the first N sum of divisors (shown in a columnar format). */ 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 j<=10 then j= 2 if $\== then say right(j-1, 6)' ' $ /*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
Wren
<lang ecmascript>import "/math" for Int, Nums import "/fmt" for Fmt
System.print("The sums of positive divisors for the first 100 positive integers are:") for (i in 1..100) {
Fmt.write("$3d ", Nums.sum(Int.divisors(i)))
if (i % 10 == 0) System.print()
}</lang>
- Output:
The sums of positive divisors for the first 100 positive integers are: 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