cp's OEIS Frontend

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].

%I A368210 #8 Sep 02 2024 19:38:14
%S A368210 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,
%T A368210 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,
%U A368210 1,1,8,6,4,1,1,8,7,4,1,1,8,8,4,1,1,9,8,4,1
%N 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].
%C A368210 The smallest k-almost prime is 2^k, therefore the n-th row has 1+floor(log_2(n)) terms.
%H A368210 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/AlmostPrime.html">Almost Prime.</a>
%e A368210 First few rows are:
%e A368210 1;
%e A368210 1, 1;
%e A368210 1, 2;
%e A368210 1, 2, 1;
%e A368210 1, 3, 1;
%e A368210 1, 3, 2;
%e A368210 1, 4, 2;
%e A368210 1, 4, 2, 1;
%e A368210 1, 4, 3, 1;
%e A368210 1, 4, 4, 1;
%e A368210 ...
%o A368210 (PARI)
%o A368210 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());
%o A368210 (PARI)
%o A368210 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);
%o A368210 nth_row(n) = for(k=0, logint(n, 2), print1(almost_prime_count(n, k), ", "));
%o A368210 tabf(nn) = for(n=1, nn, nth_row(n); print());
%o A368210 upto(nn) = for(n=1, nn, nth_row(n));
%o A368210 (Python)
%o A368210 from math import prod, isqrt
%o A368210 from sympy import primerange, integer_nthroot, primepi
%o A368210 def A368210_T(n,k):
%o A368210     if k==0: return int(n>=1)
%o A368210     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)))
%o A368210     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
%Y A368210 Cf. A001222, A285577, A346617.
%K A368210 nonn,tabf
%O A368210 1,5
%A A368210 _Daniel Suteu_, Dec 17 2023