Sum of divisors: Difference between revisions
Thundergnat (talk | contribs) (→{{header|Raku}}: fix links) |
Thundergnat (talk | contribs) m (→{{header|Raku}}: add word) |
||
| Line 159: | Line 159: | ||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
Yet more tasks that are tiny variations of each other. [[Tau function]], [[Tau number]], [[Sum of divisors]] and [[Product of divisors]] all code with minimal changes. What the heck, post 'em all. |
Yet more tasks that are tiny variations of each other. [[Tau function]], [[Tau number]], [[Sum of divisors]] and [[Product of divisors]] all use code with minimal changes. What the heck, post 'em all. |
||
<lang perl6>say "\nTau function - first 100:\n", # ID |
<lang perl6>say "\nTau function - first 100:\n", # ID |
||
Revision as of 21:02, 20 December 2020
Given a positive integer, sum its positive divisors.
- Task
Show the result for the first 100 positive integers.
Go
<lang go>package main
import "fmt"
func sumDivisors(n int) int {
sum := 0
i := 1
k := 2
if n%2 == 0 {
k = 1
}
for i*i <= n {
if n%i == 0 {
sum += i
j := n / i
if j != i {
sum += j
}
}
i += k
}
return sum
}
func main() {
fmt.Println("The sums of positive divisors for the first 100 positive integers are:")
for i := 1; i <= 100; i++ {
fmt.Printf("%3d ", sumDivisors(i))
if i%10 == 0 {
fmt.Println()
}
}
}</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
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>
Raku
Yet more tasks that are tiny variations of each other. Tau function, Tau number, Sum of divisors and Product of divisors all use code with minimal changes. What the heck, post 'em all.
<lang perl6>say "\nTau function - first 100:\n", # ID (1..*).map({ +.&divisors })[^100]\ # the task .batch(20)».fmt("%3d").join("\n"); # display formatting
say "\nTau numbers - first 100:\n", # ID (1..*).grep({ $_ %% +.&divisors })[^100]\ # the task .batch(10)».&comma».fmt("%5s").join("\n"); # display formatting
say "\nDivisor sums - first 100:\n", # ID (1..*).map({ [+] .&divisors })[^100]\ # the task .batch(20)».fmt("%4d").join("\n"); # display formatting
say "\nDivisor products - first 100:\n", # ID (1..*).map({ [×] .&divisors })[^100]\ # the task .batch(5)».&comma».fmt("%16s").join("\n"); # display formatting</lang>
- Output:
Tau function - first 100:
1 2 2 3 2 4 2 4 3 4 2 6 2 4 4 5 2 6 2 6
4 4 2 8 3 4 4 6 2 8 2 6 4 4 4 9 2 4 4 8
2 8 2 6 6 4 2 10 3 6 4 6 2 8 4 8 4 4 2 12
2 4 6 7 4 8 2 6 4 8 2 12 2 4 6 6 4 8 2 10
5 4 2 12 4 4 4 8 2 12 4 6 4 4 4 12 2 6 6 9
Tau numbers - first 100:
1 2 8 9 12 18 24 36 40 56
60 72 80 84 88 96 104 108 128 132
136 152 156 180 184 204 225 228 232 240
248 252 276 288 296 328 344 348 360 372
376 384 396 424 441 444 448 450 468 472
480 488 492 504 516 536 560 564 568 584
600 612 625 632 636 640 664 672 684 708
712 720 732 776 792 804 808 824 828 852
856 864 872 876 880 882 896 904 936 948
972 996 1,016 1,040 1,044 1,048 1,056 1,068 1,089 1,096
Divisor sums - first 100:
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
Divisor products - first 100:
1 2 3 8 5
36 7 64 27 100
11 1,728 13 196 225
1,024 17 5,832 19 8,000
441 484 23 331,776 125
676 729 21,952 29 810,000
31 32,768 1,089 1,156 1,225
10,077,696 37 1,444 1,521 2,560,000
41 3,111,696 43 85,184 91,125
2,116 47 254,803,968 343 125,000
2,601 140,608 53 8,503,056 3,025
9,834,496 3,249 3,364 59 46,656,000,000
61 3,844 250,047 2,097,152 4,225
18,974,736 67 314,432 4,761 24,010,000
71 139,314,069,504 73 5,476 421,875
438,976 5,929 37,015,056 79 3,276,800,000
59,049 6,724 83 351,298,031,616 7,225
7,396 7,569 59,969,536 89 531,441,000,000
8,281 778,688 8,649 8,836 9,025
782,757,789,696 97 941,192 970,299 1,000,000,000
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 /handle case if this is the 1st display*/ 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