login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001222 Number of prime divisors of n counted with multiplicity (also called bigomega(n) or Omega(n)).
(Formerly M0094 N0031)
1244

%I M0094 N0031

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

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

%U 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

%N Number of prime divisors of n counted with multiplicity (also called bigomega(n) or Omega(n)).

%C Maximal number of terms in any factorization of n.

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

%C Sum of exponents in prime-power factorization of n. - _Daniel Forgues_, Mar 29 2009

%C 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

%C Row sums in A067255. - _Reinhard Zumkeller_, Jun 11 2013

%C 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

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

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

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

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

%H N. J. A. Sloane and Daniel Forgues, <a href="/A001222/b001222.txt">Table of n, a(n) for n = 1..100000</a> (first 10000 terms from N. J. A. Sloane)

%H M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy], p. 844.

%H B. Cloitre, <a href="http://arxiv.org/abs/1107.0812">A tauberian approach to RH</a>, arXiv:1107.0812 [math.NT], 2011.

%H Robert E. Dressler and Jan van de Lune, <a href="http://dx.doi.org/10.1090/S0002-9939-1973-0340191-8">Some remarks concerning the number theoretic functions omega and Omega</a>, Proc. Amer. Math. Soc. 41 (1973), 403-406.

%H G. H. Hardy and S. Ramanujan, <a href="http://www.imsc.res.in/~rao/ramanujan/CamUnivCpapers/Cpaper35/page1.htm">The normal number of prime factors of a number</a>, Quart. J. Math. 48 (1917), 76-92. Also Collected papers of Srinivasa Ramanujan, AMS Chelsea Publ., Providence, RI (2000): 262-275.

%H Amarnath Murthy and Charles Ashbacher, <a href="http://www.gallup.unm.edu/~smarandache/MurthyBook.pdf">Generalized Partitions and Some New Ideas on Number Theory and Smarandache Sequences</a>, Hexis, Phoenix; USA 2005. See Section 1.4, 1.10.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PrimeFactor.html">Prime Factor</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Roundness.html">Roundness</a>

%H Wolfram Research, <a href="http://functions.wolfram.com/NumberTheoryFunctions/FactorInteger/03/02">First 50 numbers factored</a>

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%H <a href="/index/Eu#epf">Index entries for sequences computed from exponents in factorization of n</a>

%H <a href="/index/Pri#prime_indices">Index entries for sequences computed from indices in prime factorization</a>

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

%F Dirichlet generating function: ppzeta(s)*zeta(s). Here ppzeta(s) = Sum_{p prime} Sum_{k=1}^{infinity} 1/(p^k)^s. Note that ppzeta(s) = Sum_{p prime} 1/(p^s-1) and ppzeta(s) = Sum_{k=1}^{infinity} primezeta(k*s). - _Franklin T. Adams-Watters_, Sep 11 2005.

%F Totally additive with a(p) = 1.

%F a(n) = if n=1 then 0 else a(n/A020639(n)) + 1. - _Reinhard Zumkeller_, Feb 25 2008

%F a(n) = Sum_{k=1..A001221(n)} A124010(n,k). - _Reinhard Zumkeller_, Aug 27 2011

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

%F G.f.: Sum_{p prime, k>=1} x^(p^k)/(1 - x^(p^k)). - _Ilya Gutkovskiy_, Jan 25 2017

%F a(n) = A091222(A091202(n)) = A000120(A156552(n)). - _Antti Karttunen_, circa 2004 and Mar 06 2017

%F a(n) >= A267116(n) >= A268387(n). - _Antti Karttunen_, Apr 12 2017

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

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

%t Array[ Plus @@ Last /@ FactorInteger[ # ] &, 105]

%t PrimeOmega[Range[120]] (* _Harvey P. Dale_, Apr 25 2011 *)

%o (PARI) vector(100,n,bigomega(n))

%o (MAGMA) [n eq 1 select 0 else &+[p[2]: p in Factorization(n)]: n in [1..120]]; // _Bruno Berselli_, Nov 27 2013

%o (Sage) [sloane.A001222(n) for n in (1..120)] # _Giuseppe Coppoletta_, Jan 19 2015

%o (Haskell)

%o import Math.NumberTheory.Primes.Factorisation (factorise)

%o a001222 = sum . snd . unzip . factorise

%o -- _Reinhard Zumkeller_, Nov 28 2015

%o (Scheme)

%o (define (A001222 n) (let loop ((n n) (z 0)) (if (= 1 n) z (loop (/ n (A020639 n)) (+ 1 z)))))

%o ;; Requires also A020639 for which an equally naive implementation can be found under that entry. - _Antti Karttunen_, Apr 12 2017

%Y Cf. A001221 (omega (n), primes counted without multiplicity), A046660, A144494, A074946, A134334. Bisections give A091304 and A073093. A086436 is essentially the same sequence. A022559 (partial sums).

%Y 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

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

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

%Y For partial sums see A022559.

%K nonn,easy,nice,core

%O 1,4

%A _N. J. A. Sloane_

%E More terms from _David W. Wilson_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 28 06:06 EDT 2018. Contains 304734 sequences. (Running on oeis4.)