OFFSET
1,2
COMMENTS
The behavior of this function for very large values of n, and reasonably large values of k, can be used to select reasonable prime-base sizes for algorithms like quadratic sieve factoring.
EXAMPLE
There are 7 integers in the range from 1 to n=10 that can be factored using only the first k=2 primes 2 and 3: {1, 2, 3, 4, 6, 8, 9}. Hence, a(10, 2)=7.
The table begins
| k
| 1 2 3 4 5
----+--------------
1 | 1 1 1 1 1
2 | 2 2 2 2 2
3 | 2 3 3 3 3
4 | 3 4 4 4 4
5 | 3 4 5 5 5
n 6 | 3 5 6 6 6
7 | 3 5 6 7 7
8 | 4 6 7 8 8
9 | 4 7 8 9 9
10 | 4 7 9 10 10
MATHEMATICA
a[n_, k_] := With[{pp = Times @@ Prime[Range[k]]}, Count[Map[FixedPoint[#/GCD[#, pp] &, #] &, Range[n]], 1]];
Table[a[n, k], {n, 1, 10}, {k, 1, 5}] // TableForm
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Sidney Cadot, Apr 16 2023
STATUS
approved