count_of_integers_with_gpf_of_n_equals_p.sf

#!/usr/bin/ruby

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

# Given `n` and `p`, count the number of integers k <= n, such that:
#    gpf(k) = p
# where `gpf(k)` is the greatest prime factor of k.

# Equivalently, this is the number of p-smooth numbers <= floor(n/p).

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

func count_with_gpf (n, p) {
    p.smooth_count(idiv(n,p))
}

for p in (primes(23)) {
    say ("a(10^n, #{p}) for n below 15: ", 15.range.map { count_with_gpf(10**_, p) })
}

__END__
a(10^n, 2) for n below 15: [0, 3, 6, 9, 13, 16, 19, 23, 26, 29, 33, 36, 39, 43, 46]
a(10^n, 3) for n below 15: [0, 3, 13, 30, 53, 84, 122, 166, 217, 276, 342, 415, 494, 580, 673]
a(10^n, 5) for n below 15: [0, 2, 14, 46, 108, 212, 365, 578, 861, 1224, 1677, 2231, 2895, 3677, 4590]
a(10^n, 7) for n below 15: [0, 1, 12, 55, 163, 381, 766, 1387, 2322, 3664, 5522, 8005, 11243, 15373, 20551]
a(10^n, 11) for n below 15: [0, 0, 9, 51, 184, 503, 1159, 2365, 4411, 7673, 12618, 19836, 30024, 44020, 62797]
a(10^n, 13) for n below 15: [0, 0, 7, 50, 211, 651, 1674, 3769, 7681, 14498, 25721, 43384, 70135, 109383, 165407]
a(10^n, 17) for n below 15: [0, 0, 5, 45, 212, 731, 2073, 5100, 11290, 22986, 43765, 78843, 135589, 224150, 358120]
a(10^n, 19) for n below 15: [0, 0, 5, 44, 224, 840, 2572, 6809, 16141, 35060, 70947, 135375, 245883, 428099, 718581]
a(10^n, 23) for n below 15: [0, 0, 4, 38, 216, 879, 2903, 8236, 20818, 48029, 102903, 207286, 396341, 724686, 1274576]