sidef-scripts/Math/count_of_tau_inverse_in_range.sf at master · trizen/sidef-scripts · GitHub

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 19 May 2026
# https://github.com/trizen

# Count the numbers with exactly `k` divisors in a given range [A,B].

# See also:
#   https://en.wikipedia.org/wiki/Almost_prime
#   https://en.wikipedia.org/wiki/Prime_signature

func count_prime_signature_numbers(n, prime_signature) {

    # Handle empty prime signature
    if (prime_signature.len == 0) {
        return 1 if (1 <= n)
        return 0
    }

    return 0 if (n <= 0)

    var count = 0

    func generate(m, lo, k, P, sum_e, j=0) {

        var e = P[k-1]
        var hi = idiv(n,m).iroot(sum_e)

        if (lo > hi) {
            return nil
        }

        if (k == 1) {
            count += (hi.prime_count - j)
            return nil
        }

        if (k == 2) {
            var e2 = P[0]
            primes(lo, hi).each {|p|
                var t = (m * ipow(p, e))
                var u = idiv(n,t).iroot(e2)
                count += (u.prime_count - ++j)
            }
            return nil
        }

        var p = lo
        while (p <= hi) {
            var t = (m * ipow(p,e))
            var r = p.next_prime
            __FUNC__(t, r, k-1, P, sum_e - e, ++j)
            p = r
        }
    }

    var sum_e = prime_signature.sum || return 0

    if (sum_e > n.ilog2) {
        return 0
    }

    prime_signature.sort.uniq_permutations {|*a|
        generate(1, 2, a.len, a, sum_e)
    }

    return count
}

func count_prime_signature_numbers_in_range(A, B, signature) {

    var term_1 = count_prime_signature_numbers(A-1, signature)
    var term_2 = count_prime_signature_numbers(B, signature)

    term_2 - term_1
}

func multiplicative_partitions(n, max_value = n) {

    var results = []
    var divs = n.divisors.slice(1)  # divisors greater than 1

    var path = []

    func (target, min_idx) {

        if (target == 1) {
            results << [path...]    # copy
            return nil
        }

        for i in (min_idx .. divs.end) {
            var d = divs[i]

            # Prune branch if the divisor exceeds the remaining target
            break if (d > target)
            break if (d > max_value)

            if (target % d == 0) {
                path.push(d)
                __FUNC__(target/d, i)
                path.pop
            }
        }
    }(n, 0)

    return results
}

func count_inverse_tau (A, B, n) {

    var signatures = multiplicative_partitions(n, B.ilog2 + 1).map {
        .map{ .dec }
    }

    var count = 0
    signatures.each {|sig|
        count += count_prime_signature_numbers_in_range(A, B, sig)
    }
    return count
}

assert_eq(count_inverse_tau(1, 462, 16), 16)
assert_eq(count_inverse_tau(1, 2**9, 10), 13)
assert_eq(count_inverse_tau(1e5, 1e5 + 500, 48), 10)
assert_eq(count_inverse_tau(100050, 100500, 48), 10)
#assert_eq(count_inverse_tau(1, 2**40, 5040), 103)

# Number of k <= 2^(n-1) such that tau(k) = n
# https://oeis.org/A393179
for n in (1 .. 31) {
    say ("a(#{n}) = ", count_inverse_tau(1, 2**(n-1), n))
}