A362325 Table read by antidiagonals: T(n,k) = number of numbers <= n that can be fully factored using the first k prime numbers.

1, 2, 1, 2, 2, 1, 3, 3, 2, 1, 3, 4, 3, 2, 1, 3, 4, 4, 3, 2, 1, 3, 5, 5, 4, 3, 2, 1, 4, 5, 6, 5, 4, 3, 2, 1, 4, 6, 6, 6, 5, 4, 3, 2, 1, 4, 7, 7, 7, 6, 5, 4, 3, 2, 1, 4, 7, 8, 8, 7, 6, 5, 4, 3, 2, 1, 4, 7, 9, 9, 8, 7, 6, 5, 4, 3, 2, 1, 4, 8, 9, 10, 9, 8, 7, 6

Offset: 1

Author

Sidney Cadot, Apr 16 2023

Keywords

• nonn
• tabl

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.

Examples

			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
		

Programs

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