A001222 - OEIS (original) (raw)

A001222

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

3201

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

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

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

G. H. Hardy, Ramanujan: twelve lectures on subjects suggested by his life and work, Cambridge, University Press, 1940, pp. 48-57.

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

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.

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.

Eric Weisstein's World of Mathematics, Prime Factor

Eric Weisstein's World of Mathematics, Roundness

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.

G.f.: Sum_{p prime, k>=1} x^(p^k)/(1 - x^(p^k)). - Ilya Gutkovskiy, Jan 25 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

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]

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

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

(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

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. A027748 (without repetition).

KEYWORD

nonn,easy,nice,core,changed