login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A058933
Let k be bigomega(n) (i.e., n is a k-almost-prime). a(n) = number of k-almost-primes <= n.
12
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,3
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
LINKS
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
EXAMPLE
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)
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 *)
PROG
(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
CROSSREFS
Positions of 1's are A000079.
Equivalent sequence restricted to squarefree numbers: A340313.
Sequence in context: A349191 A336394 A336472 * A087470 A373215 A191475
KEYWORD
easy,nonn
AUTHOR
Naohiro Nomoto, Jan 11 2001
EXTENSIONS
Name edited by Peter Munn, Dec 30 2022
STATUS
approved