login
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].
0
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,5
COMMENTS
The smallest k-almost prime is 2^k, therefore the n-th row has 1+floor(log_2(n)) terms.
LINKS
Eric Weisstein's World of Mathematics, Almost Prime.
EXAMPLE
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;
...
PROG
(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
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Daniel Suteu, Dec 17 2023
STATUS
approved