count_of_squarefree_k-almost_primes.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 15 March 2021
# https://github.com/trizen

# Count the number of squarefree k-almost primes <= n.

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

func squarefree_almost_prime_count(n, k) {

    if (k == 1) {
        return n.prime_count
    }

    var count = 0

    func (m, lo, k, j = 1) {

        var hi = idiv(n,m).iroot(k)

        if (k == 2) {

            each_prime(lo, hi, {|p|
                count += (prime_count(idiv(n, m*p)) - j++)
            })

            return nil
        }

        each_prime(lo, hi, {|p|
            __FUNC__(m*p, p+1, k-1, ++j)
        })
    }(1, 2, k)

    return count
}

# Run some tests

for k in (1..10) {

    var upto = k.pn_primorial+1e5.irand

    var x = squarefree_almost_prime_count(upto, k)
    var y = k.squarefree_almost_primes(upto).len
    var z = k.squarefree_almost_prime_count(upto)

    say "Testing: #{k} with n = #{upto} -> #{x}"

    assert_eq(x, y)
    assert_eq(x, z)
}

say ''

for k in (1..6) {
    say ("Count of squarefree #{'%2d' % k}-almost primes for 10^n: ", 8.of {|n| squarefree_almost_prime_count(10**n, k) })
}

__END__
Count of squarefree  1-almost primes for 10^n: [0, 4, 25, 168, 1229, 9592, 78498, 664579]
Count of squarefree  2-almost primes for 10^n: [0, 2, 30, 288, 2600, 23313, 209867, 1903878]
Count of squarefree  3-almost primes for 10^n: [0, 0, 5, 135, 1800, 19919, 206964, 2086746]
Count of squarefree  4-almost primes for 10^n: [0, 0, 0, 16, 429, 7039, 92966, 1103888]
Count of squarefree  5-almost primes for 10^n: [0, 0, 0, 0, 24, 910, 18387, 286758]
Count of squarefree  6-almost primes for 10^n: [0, 0, 0, 0, 0, 20, 1235, 32396]