count_of_integers_with_lpf_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:
#    lpf(k) = p
# where `lpf(k)` is the least prime factor of k.

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

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

func count_with_lpf (n, p) {
    p.rough_count(idiv(n,p))
}

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

__END__
a(10^n,  2) for n below 15: [0, 5, 50, 500, 5000, 50000, 500000, 5000000, 50000000, 500000000, 5000000000, 50000000000, 500000000000, 5000000000000, 50000000000000]
a(10^n,  3) for n below 15: [0, 2, 17, 167, 1667, 16667, 166667, 1666667, 16666667, 166666667, 1666666667, 16666666667, 166666666667, 1666666666667, 16666666666667]
a(10^n,  5) for n below 15: [0, 1, 7, 67, 667, 6667, 66667, 666667, 6666667, 66666667, 666666667, 6666666667, 66666666667, 666666666667, 6666666666667]
a(10^n,  7) for n below 15: [0, 1, 4, 38, 381, 3809, 38095, 380953, 3809524, 38095238, 380952381, 3809523809, 38095238095, 380952380953, 3809523809524]
a(10^n, 11) for n below 15: [0, 0, 1, 21, 208, 2078, 20779, 207792, 2077921, 20779221, 207792208, 2077922078, 20779220779, 207792207792, 2077922077921]
a(10^n, 13) for n below 15: [0, 0, 1, 17, 160, 1598, 15984, 159840, 1598401, 15984017, 159840160, 1598401598, 15984015984, 159840159840, 1598401598401]
a(10^n, 17) for n below 15: [0, 0, 1, 11, 111, 1128, 11284, 112830, 1128285, 11282835, 112828349, 1128283483, 11282834811, 112828348124, 1128283481225]
a(10^n, 19) for n below 15: [0, 0, 1, 9, 95, 950, 9503, 95017, 950134, 9501332, 95013344, 950133456, 9501334580, 95013345788, 950133457874]
a(10^n, 23) for n below 15: [0, 0, 1, 7, 77, 742, 7435, 74357, 743582, 7435827, 74358272, 743582708, 7435827061, 74358270615, 743582706160]