cp's OEIS Frontend

A058933 Let k be bigomega(n) (i.e., n is a k-almost-prime). a(n) = number of k-almost-primes <= n.

%I A058933 #44 Aug 29 2024 01:36:57
%S A058933 1,1,2,1,3,2,4,1,3,4,5,2,6,5,6,1,7,3,8,4,7,8,9,2,9,10,5,6,10,7,11,1,
%T A058933 11,12,13,3,12,14,15,4,13,8,14,9,10,16,15,2,17,11,18,12,16,5,19,6,20,
%U A058933 21,17,7,18,22,13,1,23,14,19,15,24,16,20,3,21,25,17,18,26,19,22,4,8,27,23
%N A058933 Let k be bigomega(n) (i.e., n is a k-almost-prime). a(n) = number of k-almost-primes <= n.
%C A058933 Equivalently, the number of positive integers less than or equal to n with the same number of prime factors as n, counted with multiplicity. - _Gus Wiseman_, Dec 28 2018
%C A058933 There is a close relationship between a(n) and a(n^2). See A209934 for an exploratory quantification. - _Peter Munn_, Aug 04 2019
%H A058933 Alois P. Heinz, <a href="/A058933/b058933.txt">Table of n, a(n) for n = 1..20000</a>
%F A058933 Ordinal transform of A001222 (bigomega). - _Franklin T. Adams-Watters_, Aug 28 2006
%F A058933 If a(n) < a(3^A001222(2n)) = A078843(A001222(2n)) then a(2n) = a(n), otherwise a(2n) > a(n). - _Peter Munn_, Aug 05 2019
%e A058933 3 is prime, so a(3)=2. 10 is 2-almost prime (semiprime), so a(10)=4.
%e A058933 From _Gus Wiseman_, Dec 28 2018: (Start)
%e A058933 Column n lists the a(n) positive integers less than or equal to n with the same number of prime factors as n, counted with multiplicity:
%e A058933   1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20
%e A058933   ---------------------------------------------------------------------
%e A058933   1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20
%e A058933         2     3  4  5     6  9   7   8   11  10  14      13  12  17  18
%e A058933               2     3     4  6   5       7   9   10      11  8   13  12
%e A058933                     2        4   3       5   6   9       7       11  8
%e A058933                                  2       3   4   6       5       7
%e A058933                                          2       4       3       5
%e A058933                                                          2       3
%e A058933                                                                  2
%e A058933 (End)
%p A058933 p:= proc() 0 end:
%p A058933 a:= proc(n) option remember; local t;
%p A058933       t:= numtheory[bigomega](n);
%p A058933       p(t):= p(t)+1
%p A058933     end:
%p A058933 seq(a(n), n=1..100);  # _Alois P. Heinz_, Oct 09 2015
%t A058933 p[_] = 0; a[n_] := a[n] = Module[{t}, t = PrimeOmega[n]; p[t] = p[t]+1]; Table[a[n], {n, 1, 100}] (* _Jean-François Alcover_, Jan 24 2017, after _Alois P. Heinz_ *)
%o A058933 (PARI) a(n) = my(k=bigomega(n)); sum(i=1, n, bigomega(i)==k); \\ _Michel Marcus_, Jun 27 2024
%o A058933 (Python)
%o A058933 from math import prod, isqrt
%o A058933 from sympy import isprime, primepi, primerange, integer_nthroot, primeomega
%o A058933 def A058933(n):
%o A058933     if n==1: return 1
%o A058933     if isprime(n): return primepi(n)
%o A058933     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 A058933     return int(sum(primepi(n//prod(c[1] for c in a))-a[-1][0] for a in g(n,0,1,1,primeomega(n)))) # _Chai Wah Wu_, Aug 28 2024
%Y A058933 Positions of 1's are A000079.
%Y A058933 Cf. A001358, A014612, A014613, A014614.
%Y A058933 Cf. A000010, A000961, A001222, A006049, A045920, A061142, A067003, A078843, A209934, A302242, A322838, A322839, A322840.
%Y A058933 Equivalent sequence restricted to squarefree numbers: A340313.
%K A058933 easy,nonn
%O A058933 1,3
%A A058933 _Naohiro Nomoto_, Jan 11 2001
%E A058933 Name edited by _Peter Munn_, Dec 30 2022