sidef-scripts/Math/count_of_smooth_numbers.sf

#!/usr/bin/ruby

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

# Count the number of B-smooth numbers <= n.

func smooth_count(n, p) {

    if (p == 2) {
        return 1+n.ilog2
    }

    var q = p.prev_prime

    0..n.ilog(p) -> sum {|k|
        __FUNC__(idiv(n, p**k), q)
    }
}

for p in (primes(15)) {
    var arr = 10.range.map {|n| smooth_count(10**n, p) }
    assert_eq(arr, 10.range.map {|n| p.smooth_count(10**n) })
    say ("Ψ(10^n, #{p}) for n < 10: ", arr)
}

__END__
Ψ(10^n, 2) for n < 10: [1, 4, 7, 10, 14, 17, 20, 24, 27, 30]
Ψ(10^n, 3) for n < 10: [1, 7, 20, 40, 67, 101, 142, 190, 244, 306]
Ψ(10^n, 5) for n < 10: [1, 9, 34, 86, 175, 313, 507, 768, 1105, 1530]
Ψ(10^n, 7) for n < 10: [1, 10, 46, 141, 338, 694, 1273, 2155, 3427, 5194]
Ψ(10^n, 11) for n < 10: [1, 10, 55, 192, 522, 1197, 2432, 4520, 7838, 12867]
Ψ(10^n, 13) for n < 10: [1, 10, 62, 242, 733, 1848, 4106, 8289, 15519, 27365]
Ψ(10^n, 17) for n < 10: [1, 10, 67, 287, 945, 2579, 6179, 13389, 26809, 50351]
Ψ(10^n, 19) for n < 10: [1, 10, 72, 331, 1169, 3419, 8751, 20198, 42950, 85411]