-
Notifications
You must be signed in to change notification settings - Fork 0
/
powerfree_sigma.sf
70 lines (56 loc) · 2.17 KB
/
powerfree_sigma.sf
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#!/usr/bin/ruby
# Sum of the k-powerfree divisors of n.
# See also:
# https://oeis.org/A048250
# https://oeis.org/A073185
func powerfree_sigma0(n, k=2) {
n.factor_prod {|_,e|
min(e, k-1) + 1
}
}
func powerfree_sigma(n, k=2, j=1) {
return powerfree_sigma0(n, k) if (j == 0)
var prod = 1
for p,e in (n.factor_exp) {
e = min(e, k-1)
#prod *= sigma(p**e, j)
prod *= (p**(j*(e+1)) - 1)/(p**j - 1)
}
return prod
}
for n in (1..20) {
say "sum of squarefree divisors of #{n} is #{powerfree_sigma(n, 2)}"
assert_eq(powerfree_sigma(n, 2), 2.powerfree_divisors(n).sum)
assert_eq(powerfree_sigma(n, 3), 3.powerfree_divisors(n).sum)
assert_eq(powerfree_sigma(n, 4), 4.powerfree_divisors(n).sum)
assert_eq(powerfree_sigma(n, 2, 0), 2.powerfree_divisors(n).len)
assert_eq(powerfree_sigma(n, 3, 0), 3.powerfree_divisors(n).len)
assert_eq(powerfree_sigma(n, 4, 0), 4.powerfree_divisors(n).len)
assert_eq(powerfree_sigma(n, 2, 2), 2.powerfree_divisors(n).sum { _**2 })
assert_eq(powerfree_sigma(n, 3, 2), 3.powerfree_divisors(n).sum { _**2 })
assert_eq(powerfree_sigma(n, 4, 2), 4.powerfree_divisors(n).sum { _**2 })
assert_eq(powerfree_sigma(n, 2, 3), 2.powerfree_divisors(n).sum { _**3 })
assert_eq(powerfree_sigma(n, 3, 3), 3.powerfree_divisors(n).sum { _**3 })
assert_eq(powerfree_sigma(n, 4, 3), 4.powerfree_divisors(n).sum { _**3 })
}
__END__
sum of squarefree divisors of 1 is 1
sum of squarefree divisors of 2 is 3
sum of squarefree divisors of 3 is 4
sum of squarefree divisors of 4 is 3
sum of squarefree divisors of 5 is 6
sum of squarefree divisors of 6 is 12
sum of squarefree divisors of 7 is 8
sum of squarefree divisors of 8 is 3
sum of squarefree divisors of 9 is 4
sum of squarefree divisors of 10 is 18
sum of squarefree divisors of 11 is 12
sum of squarefree divisors of 12 is 12
sum of squarefree divisors of 13 is 14
sum of squarefree divisors of 14 is 24
sum of squarefree divisors of 15 is 24
sum of squarefree divisors of 16 is 3
sum of squarefree divisors of 17 is 18
sum of squarefree divisors of 18 is 12
sum of squarefree divisors of 19 is 20
sum of squarefree divisors of 20 is 18