A368210 Irregular triangle T(n,k) read by rows (n >= 1, 0 <= k <= max(A001222([1..n]))), giving the number of k-almost primes in [1,n].

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

Offset: 1

Author

Daniel Suteu, Dec 17 2023

Keywords

• nonn
• tabf

Comments

The smallest k-almost prime is 2^k, therefore the n-th row has 1+floor(log_2(n)) terms.

Examples

			First few rows are:
1;
1, 1;
1, 2;
1, 2, 1;
1, 3, 1;
1, 3, 2;
1, 4, 2;
1, 4, 2, 1;
1, 4, 3, 1;
1, 4, 4, 1;
...
		

Links

• Eric Weisstein's World of Mathematics, Almost Prime.

Crossrefs

Cf. A001222, A285577, A346617.

Programs

PARI

tabf(nn) = for(n=1, nn, my(v=vector(n, j, bigomega(j))); for(k=0, vecmax(v), print1(#select(x->x==k, v), ", ")); print());

PARI

almost_prime_count(n,k) = if(k==0, return(n>=1)); if(k==1, return(primepi(n))); (f(m, p, k, j=0)=my(s=sqrtnint(n\m, k), count=0); if(k==2, forprime(q=p, s, count += primepi(n\(m*q)) - j; j+=1); return(count)); forprime(q=p, s, count += f(m*q, q, k-1, j); j+=1); count); f(1, 2, k);
nth_row(n) = for(k=0, logint(n, 2), print1(almost_prime_count(n, k), ", "));
tabf(nn) = for(n=1, nn, nth_row(n); print());
upto(nn) = for(n=1, nn, nth_row(n));

Python

from math import prod, isqrt
from sympy import primerange, integer_nthroot, primepi
def A368210_T(n,k):
    if k==0: return int(n>=1)
    def g(x,a,b,c,m): yield from (((d,) for d in enumerate(primerange(b,isqrt(x//c)+1),a)) if m==2 else (((a2,b2),)+d for a2,b2 in enumerate(primerange(b,integer_nthroot(x//c,m)[0]+1),a) for d in g(x,a2,b2,c*b2,m-1)))
    return int(sum(primepi(n//prod(c[1] for c in a))-a[-1][0] for a in g(n,0,1,1,k)) if k>1 else primepi(n)) # Chai Wah Wu, Sep 02 2024