-
Notifications
You must be signed in to change notification settings - Fork 0
/
is_infinitary_divisor.sf
56 lines (44 loc) · 1.23 KB
/
is_infinitary_divisor.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
#!/usr/bin/ruby
# Check if a given divisors d of n, is an infinitary divisors of n.
# See also:
# https://oeis.org/A049417
# https://oeis.org/A077609
func is_infinitary_divisor(d, n, P = n.prime_divisors) {
P.each {|p|
var n2 = n.valuation(p)
var d2 = d.valuation(p)
(n2 & d2) == d2 || return false
}
return true
}
func infinitary_divisors(n) {
var D = n.divisors
var P = D.grep { .is_prime }
D.grep {|d| is_infinitary_divisor(d, n, P) }
}
for n in (1..20) {
say "i-divisors of #{n} = #{infinitary_divisors(n)}"
assert_eq(infinitary_divisors(n).len, n.isigma0)
assert_eq(infinitary_divisors(n).sum, n.isigma)
}
__END__
i-divisors of 1 = [1]
i-divisors of 2 = [1, 2]
i-divisors of 3 = [1, 3]
i-divisors of 4 = [1, 4]
i-divisors of 5 = [1, 5]
i-divisors of 6 = [1, 2, 3, 6]
i-divisors of 7 = [1, 7]
i-divisors of 8 = [1, 2, 4, 8]
i-divisors of 9 = [1, 9]
i-divisors of 10 = [1, 2, 5, 10]
i-divisors of 11 = [1, 11]
i-divisors of 12 = [1, 3, 4, 12]
i-divisors of 13 = [1, 13]
i-divisors of 14 = [1, 2, 7, 14]
i-divisors of 15 = [1, 3, 5, 15]
i-divisors of 16 = [1, 16]
i-divisors of 17 = [1, 17]
i-divisors of 18 = [1, 2, 9, 18]
i-divisors of 19 = [1, 19]
i-divisors of 20 = [1, 4, 5, 20]