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

%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