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

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, 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, 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

Offset: 1

Author

Naohiro Nomoto, Jan 11 2001

Keywords

• easy
• nonn

Comments

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

There is a close relationship between a(n) and a(n^2). See A209934 for an exploratory quantification. - Peter Munn, Aug 04 2019

Examples

			3 is prime, so a(3)=2. 10 is 2-almost prime (semiprime), so a(10)=4.
From _Gus Wiseman_, Dec 28 2018: (Start)
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:
  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20
  ---------------------------------------------------------------------
  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20
        2     3  4  5     6  9   7   8   11  10  14      13  12  17  18
              2     3     4  6   5       7   9   10      11  8   13  12
                    2        4   3       5   6   9       7       11  8
                                 2       3   4   6       5       7
                                         2       4       3       5
                                                         2       3
                                                                 2
(End)
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..20000

Crossrefs

Positions of 1's are A000079.

Cf. A001358, A014612, A014613, A014614.

Cf. A000010, A000961, A001222, A006049, A045920, A061142, A067003, A078843, A209934, A302242, A322838, A322839, A322840.

Equivalent sequence restricted to squarefree numbers: A340313.

Programs

Maple

p:= proc() 0 end:
a:= proc(n) option remember; local t;
      t:= numtheory[bigomega](n);
      p(t):= p(t)+1
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Oct 09 2015

Mathematica

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 *)

PARI

a(n) = my(k=bigomega(n)); sum(i=1, n, bigomega(i)==k); \\ Michel Marcus, Jun 27 2024

Python

from math import prod, isqrt
from sympy import isprime, primepi, primerange, integer_nthroot, primeomega
def A058933(n):
    if n==1: return 1
    if isprime(n): return primepi(n)
    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,primeomega(n)))) # Chai Wah Wu, Aug 28 2024

Formula

Ordinal transform of A001222 (bigomega). - Franklin T. Adams-Watters, Aug 28 2006

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

Extensions

Name edited by Peter Munn, Dec 30 2022