%I #17 Jul 09 2024 19:41:49
%S 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,
%T 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,
%U 9,9,8,7,6,5,4,3,2,1,4,8,9,10,9,8,7,6
%N Table read by antidiagonals: T(n,k) = number of numbers <= n that can be fully factored using the first k prime numbers.
%C 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.
%e 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.
%e The table begins
%e | k
%e | 1 2 3 4 5
%e ----+--------------
%e 1 | 1 1 1 1 1
%e 2 | 2 2 2 2 2
%e 3 | 2 3 3 3 3
%e 4 | 3 4 4 4 4
%e 5 | 3 4 5 5 5
%e n 6 | 3 5 6 6 6
%e 7 | 3 5 6 7 7
%e 8 | 4 6 7 8 8
%e 9 | 4 7 8 9 9
%e 10 | 4 7 9 10 10
%t a[n_, k_] := With[{pp = Times @@ Prime[Range[k]]}, Count[Map[FixedPoint[#/GCD[#, pp] &, #] &, Range[n]], 1]];
%t Table[a[n, k], {n, 1, 10}, {k, 1, 5}] // TableForm
%K nonn,tabl
%O 1,2
%A _Sidney Cadot_, Apr 16 2023