A001222 Number of prime divisors of n counted with multiplicity (also called big omega of n, bigomega(n) or Omega(n)). (Formerly M0094 N0031)

0, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 3, 1, 2, 2, 4, 1, 3, 1, 3, 2, 2, 1, 4, 2, 2, 3, 3, 1, 3, 1, 5, 2, 2, 2, 4, 1, 2, 2, 4, 1, 3, 1, 3, 3, 2, 1, 5, 2, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 4, 1, 2, 3, 6, 2, 3, 1, 3, 2, 3, 1, 5, 1, 2, 3, 3, 2, 3, 1, 5, 4, 2, 1, 4, 2, 2, 2, 4, 1, 4, 2, 3, 2, 2, 2, 6, 1, 3, 3, 4, 1, 3, 1, 4, 3, 2, 1, 5, 1, 3, 2

Offset

1,4

Comments

Maximal number of terms in any factorization of n.

Number of prime powers (not including 1) that divide n.

Sum of exponents in prime-power factorization of n. - Daniel Forgues, Mar 29 2009

Sum_{d|n} 2^(-A001221(d) - a(n/d)) = Sum_{d|n} 2^(-a(d) - A001221(n/d)) = 1 (see Dressler and van de Lune link). - Michel Marcus, Dec 18 2012

Row sums in A067255. - Reinhard Zumkeller, Jun 11 2013

Conjecture: Let f(n) = (x+y)^a(n), and g(n) = x^a(n), and h(n) = (x+y)^A046660(n) * y^A001221(n) with x, y complex numbers and 0^0 = 1. Then f(n) = Sum_{d|n} g(d)*h(n/d). This is proved for x = 1-y (see Dressler and van de Lune link). - Werner Schulte, Feb 10 2018

Let r, s be some fixed integers. Then we have:

(1) The sequence b(n) = Dirichlet convolution of r^bigomega(n) and s^bigomega(n) is multiplicative with b(p^e) = (r^(e+1)-s^(e+1))/(r-s) for prime p and e >= 0. The case r = s leads to b(p^e) = (e+1)*r^e.

(2) The sequence c(n) = Dirichlet convolution of r^bigomega(n) and mu(n)*s^bigomega(n) is multiplicative with c(p^e) = (r-s)*r^(e-1) and c(1) = 1 for prime p and e > 0 where mu(n) = A008683(n). - Werner Schulte, Feb 20 2019

a(n) is also the length of the composition series for every solvable group of order n. - Miles Englezou, Apr 25 2024

References

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 119, #12, omega(n).

M. Kac, Statistical Independence in Probability, Analysis and Number Theory, Carus Monograph 12, Math. Assoc. Amer., 1959, see p. 64.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Daniel Forgues, Table of n, a(n) for n = 1..100000 (first 10000 terms from N. J. A. Sloane)

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy], p. 844.

Benoit Cloitre, A tauberian approach to RH, arXiv:1107.0812 [math.NT], 2011.

Robert E. Dressler and Jan van de Lune, Some remarks concerning the number theoretic functions omega and Omega, Proc. Amer. Math. Soc. 41 (1973), 403-406.

G. H. Hardy and S. Ramanujan, The normal number of prime factors of a number, Quart. J. Math. 48 (1917), 76-92. Also Collected papers of Srinivasa Ramanujan, AMS Chelsea Publ., Providence, RI (2000): 262-275.

Douglas E. Iannucci and Urban Larsson, Game values of arithmetic functions, arXiv:2101.07608 [math.NT], 2021. Section 1.1.1. pp. 4-5.

Amarnath Murthy and Charles Ashbacher, Generalized Partitions and Some New Ideas on Number Theory and Smarandache Sequences, Hexis, Phoenix; USA 2005. See Section 1.4, 1.10.

Eric Weisstein's World of Mathematics, Prime Factor

Eric Weisstein's World of Mathematics, Roundness

Wolfram Research, First 50 numbers factored

Index entries for "core" sequences

Index entries for sequences computed from exponents in factorization of n

Index entries for sequences computed from indices in prime factorization

Formula

n = Product_(p_j^k_j) -> a(n) = Sum_(k_j).

Dirichlet g.f.: ppzeta(s)*zeta(s). Here ppzeta(s) = Sum_{p prime} Sum_{k>=1} 1/(p^k)^s. Note that ppzeta(s) = Sum_{p prime} 1/(p^s-1) and ppzeta(s) = Sum_{k>=1} primezeta(k*s). - Franklin T. Adams-Watters, Sep 11 2005

Totally additive with a(p) = 1.

a(n) = if n=1 then 0 else a(n/A020639(n)) + 1. - Reinhard Zumkeller, Feb 25 2008

a(n) = Sum_{k=1..A001221(n)} A124010(n,k). - Reinhard Zumkeller, Aug 27 2011

a(n) = A022559(n) - A022559(n-1).

G.f.: Sum_{p prime, k>=1} x^(p^k)/(1 - x^(p^k)). - Ilya Gutkovskiy, Jan 25 2017

a(n) = A091222(A091202(n)) = A000120(A156552(n)). - Antti Karttunen, circa 2004 and Mar 06 2017

a(n) >= A267116(n) >= A268387(n). - Antti Karttunen, Apr 12 2017

Sum_{k=1..n} 2^(-A001221(gcd(n,k)) - a(n/gcd(n,k)))/phi(n/gcd(n,k)) = Sum_{k=1..n} 2^(-a(gcd(n,k)) - A001221(n/gcd(n,k)))/phi(n/gcd(n,k)) = 1, where phi = A000010. - Richard L. Ollerton, May 13 2021

a(n) = a(A046523(n)) = A007814(A108951(n)) = A061395(A122111(n)) = A056239(A181819(n)) = A048675(A293442(n)). - Antti Karttunen, Apr 30 2022

Example

16=2^4, so a(16)=4; 18=2*3^2, so a(18)=3.

Maple

with(numtheory): seq(bigomega(n), n=1..111);

Mathematica

Array[ Plus @@ Last /@ FactorInteger[ # ] &, 105]
PrimeOmega[Range[120]] (* Harvey P. Dale, Apr 25 2011 *)

Prog

(PARI) vector(100, n, bigomega(n))
(Magma) [n eq 1 select 0 else &+[p[2]: p in Factorization(n)]: n in [1..120]]; // Bruno Berselli, Nov 27 2013
(SageMath) [sloane.A001222(n) for n in (1..120)] # Giuseppe Coppoletta, Jan 19 2015
(SageMath) [gp.bigomega(n) for n in range(1, 131)] # G. C. Greubel, Jul 13 2024
(Haskell)
import Math.NumberTheory.Primes.Factorisation (factorise)
a001222 = sum . snd . unzip . factorise
-- Reinhard Zumkeller, Nov 28 2015
(Scheme)
(define (A001222 n) (let loop ((n n) (z 0)) (if (= 1 n) z (loop (/ n (A020639 n)) (+ 1 z)))))
;; Requires also A020639 for which an equally naive implementation can be found under that entry. - Antti Karttunen, Apr 12 2017
(GAP) Concatenation([0], List([2..150], n->Length(Factors(n)))); # Muniru A Asiru, Feb 21 2019
(Python)
from sympy import primeomega
def a(n): return primeomega(n)
print([a(n) for n in range(1, 112)]) # Michael S. Branicky, Apr 30 2022
(Julia)
using Nemo
function NumberOfPrimeFactors(n; distinct=true)
    distinct && return length(factor(ZZ(n)))
    sum(e for (p, e) in factor(ZZ(n)); init=0)
end
println([NumberOfPrimeFactors(n, distinct=false) for n in 1:60])  # Peter Luschny, Jan 02 2024

Crossrefs

Cf. A001221 (omega, primes counted without multiplicity), A008836 (Liouville's lambda, equal to (-1)^a(n)), A046660, A144494, A074946, A134334.

Bisections give A091304 and A073093. A086436 is essentially the same sequence. Cf. A022559 (partial sums), A066829 (parity), A092248 (parity of omega).

Sequences listing n such that a(n) = r: A000040 (r = 1), A001358 (r = 2), A014612 (r = 3), A014613 (r = 4), A014614 (r = 5), A046306 (r = 6), A046308 (r = 7), A046310 (r = 8), A046312 (r = 9), A046314 (r = 10), A069272 (r = 11), A069273 (r = 12), A069274 (r = 13), A069275 (r = 14), A069276 (r = 15), A069277 (r = 16), A069278 (r = 17), A069279 (r = 18), A069280 (r = 19), A069281 (r = 20). - Jason Kimberley, Oct 02 2011

Cf. A079149 (primes adj. to integers with at most 2 prime factors, a(n)<=2).

Cf. A000120, A020639, A091202, A091222, A156552, A267116, A268387.

Cf. A027748 (without repetition).

Cf. A000010.

Sequence in context: A305822 A326190 A086436 * A257091 A351418 A359909

Adjacent sequences: A001219 A001220 A001221 * A001223 A001224 A001225

Keyword

nonn,easy,nice,core

Author

N. J. A. Sloane

Extensions

More terms from David W. Wilson

Status

approved