count_of_rough_numbers.sf

#!/usr/bin/ruby

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

# Count the number of k-rough numbers <= n.

func rough_count (n,k) {
    func (n,p) {

        if (p > n.isqrt) {
            return 1
        }

        if (p == 2) {
            return (n >> 1)
        }

        if (p == 3) {
            var t = idiv(n,3)
            return (t - (t >> 1))
        }

        var u = 0
        var t = idiv(n,p)

        for (var q = 2; q < p; q.next_prime!) {

            var v = __FUNC__(t - (t % q), q)

            if (v == 1) {
                u += prime_count(q, p-1)
                break
            }

            u += v
        }

        t - u
    }(n*k, k)
}

for p in (primes(23)) {
    say ("Φ(10^n, #{p}) for n < 15: ", 15.range.map { rough_count(10**_, p) })
}

__END__
Φ(10^n, 2) for n < 15: [1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000, 100000000000, 1000000000000, 10000000000000, 100000000000000]
Φ(10^n, 3) for n < 15: [1, 5, 50, 500, 5000, 50000, 500000, 5000000, 50000000, 500000000, 5000000000, 50000000000, 500000000000, 5000000000000, 50000000000000]
Φ(10^n, 5) for n < 15: [1, 3, 33, 333, 3333, 33333, 333333, 3333333, 33333333, 333333333, 3333333333, 33333333333, 333333333333, 3333333333333, 33333333333333]
Φ(10^n, 7) for n < 15: [1, 2, 26, 266, 2666, 26666, 266666, 2666666, 26666666, 266666666, 2666666666, 26666666666, 266666666666, 2666666666666, 26666666666666]
Φ(10^n, 11) for n < 15: [1, 1, 22, 228, 2285, 22857, 228571, 2285713, 22857142, 228571428, 2285714285, 22857142857, 228571428571, 2285714285713, 22857142857142]
Φ(10^n, 13) for n < 15: [1, 1, 21, 207, 2077, 20779, 207792, 2077921, 20779221, 207792207, 2077922077, 20779220779, 207792207792, 2077922077921, 20779220779221]
Φ(10^n, 17) for n < 15: [1, 1, 20, 190, 1917, 19181, 191808, 1918081, 19180820, 191808190, 1918081917, 19180819181, 191808191808, 1918081918081, 19180819180820]
Φ(10^n, 19) for n < 15: [1, 1, 19, 179, 1806, 18053, 180524, 1805251, 18052535, 180525355, 1805253568, 18052535698, 180525356997, 1805253569957, 18052535699595]
Φ(10^n, 23) for n < 15: [1, 1, 18, 170, 1711, 17103, 171021, 1710234, 17102401, 171024023, 1710240224, 17102402242, 171024022417, 1710240224169, 17102402241721]