cube-full_numbers.sf

#!/usr/bin/ruby

# Fast algorithm for generating all the cube-full numbers <= n.
# A positive integer n is considered cube-full, if for every prime p that divides n, so does p^3.
# These are numbers of the form: a^3 * b^4 * c^5, for a,b,c >= 1.

# See also:
#   THE DISTRIBUTION OF CUBE-FULL NUMBERS, by P. SHIU (1990).

# OEIS:
#   https://oeis.org/A036966 -- cube-full numbers

func cubefull_numbers (n) {    # cubefull numbers <= n

    var cubefull = []

    n.iroot(5).each_squarefree {|a|
        idiv(n, a**5).iroot(4).each_squarefree {|b|
            gcd(a,b) == 1 || next
            var v = (a**5 * b**4)
            for c in (1..iroot(idiv(n, v), 3)) {
                cubefull << (v * c**3)
            }
        }
    }

    cubefull.sort
}

say cubefull_numbers(1e4)

__END__
[1, 8, 16, 27, 32, 64, 81, 125, 128, 216, 243, 256, 343, 432, 512, 625, 648, 729, 864, 1000, 1024, 1296, 1331, 1728, 1944, 2000, 2048, 2187, 2197, 2401, 2592, 2744, 3125, 3375, 3456, 3888, 4000, 4096, 4913, 5000, 5184, 5488, 5832, 6561, 6859, 6912, 7776, 8000, 8192, 9261, 10000]