| 12345678910111213141516171819202122232425262728293031323334 |
- #!/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]
|
