squarefree_almost_primes_in_range.sf

#!/usr/bin/ruby

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

# Generate squarefree k-almost primes in range [a,b]. (not in sorted order)

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

func squarefree_almost_primes(a, b, k, callback) {

    a = max(k.pn_primorial, a)

    func (m, lo, k) {

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

        if (lo > hi) {
            return nil
        }

        if (k == 1) {

            lo = max(lo, idiv_ceil(a, m))

            if (lo > hi) {
                return nil
            }

            primes_each(lo, hi, {|p|
                callback(m*p)
            })

            return nil
        }

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

    return callback
}

# Generate squarefree 5-almost in the range [3000, 10000]

var k    = 5
var from = 3000
var upto = 10000

var arr = gather {
    squarefree_almost_primes(from, upto, k, { take(_) })
}.sort

assert_eq(arr, max(from, k.pn_primorial)..upto -> grep{.is_squarefree && .is_almost_prime(k)})     # just for testing
say arr

# Run some more tests

for k in (1..10) {

    var from = k.pn_primorial
    var upto = from+1e4.irand

    say "Testing: k = #{k} with #{from} .. #{upto}"

    var arr = gather {
        squarefree_almost_primes(from, upto, k, { take(_) })
    }.sort

    assert_eq(arr, max(from, k.pn_primorial)..upto -> grep{.is_squarefree && .is_almost_prime(k)})
}