A362325 - OEIS

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

(list; table; graph; refs; listen; history; text; internal format)

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.

LINKS

Table of n, a(n) for n=1..86.

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

Sequence in context: A116482 A173306 A276430 * A325002 A182594 A201593

Adjacent sequences: A362322 A362323 A362324 * A362326 A362327 A362328

KEYWORD

nonn,tabl

AUTHOR

Sidney Cadot, Apr 16 2023

STATUS

approved