This site is supported by donations to The OEIS Foundation.



Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001221 Number of distinct primes dividing n (also called omega(n)).
(Formerly M0056 N0019)

%I M0056 N0019

%S 0,1,1,1,1,2,1,1,1,2,1,2,1,2,2,1,1,2,1,2,2,2,1,2,1,2,1,2,1,3,1,1,2,2,

%T 2,2,1,2,2,2,1,3,1,2,2,2,1,2,1,2,2,2,1,2,2,2,2,2,1,3,1,2,2,1,2,3,1,2,

%U 2,3,1,2,1,2,2,2,2,3,1,2,1,2,1,3,2,2,2,2,1,3,2,2,2,2,2,2,1,2,2,2,1,3,1,2,3,2,1,2,1,3,2

%N Number of distinct primes dividing n (also called omega(n)).

%C From Peter C. Heinig (algorithms(AT)gmx.de), Mar 08 2008: (Start)

%C This is also the number of maximal ideals of the ring (Z/nZ,+,*). Since every finite integral domain must be a field, every prime ideal of Z/nZ is a maximal ideal and since in general each maximal ideal is prime, there are just as many prime ideals as maximal ones in Z/nZ, so the sequence gives the number of prime ideals of Z/nZ as well.

%C The reason why this number is given by the sequence is that the ideals of Z/nZ are precisely the subgroups of (Z/nZ,+). Hence for an ideal to be maximal it has form a maximal subgroup of (Z/nZ,+) and this is equivalent to having prime index in (Z/nZ) and this is equivalent to being generated by a single prime divisor of n.

%C Finally, all the groups arising in this way have different orders, hence are different, so the number of maximal ideals equals the number of distinct primes dividing n. (End)

%C Equals double inverse Mobius transform of A143519, where A051731 = the inverse Mobius transform. - _Gary W. Adamson_, Aug 22 2008

%C a(n) = number of prime-power divisors of n. If n = Product (p_i^e_i), the prime-power divisors of n are p_1^e_1, p_2^e_2, ..., p_k^e_k, where k = number of distinct primes dividing n. - _Jaroslav Krizek_, May 04 2009

%C Sum_{d|n} 2^(-A001221(d) - A001222(n/d)) = Sum_{d|n} 2^(-A001222(d) - A001221(n/d)) = 1 (see Dressler and van de Lune link). - _Michel Marcus_, Dec 18 2012

%C Up to 2*3*5*7*11*13*17*19*23*29 - 1 = 6469693230 - 1, also the decimal expansion of the constant 0.01111211... = sum_{k>=0} 1 / (10 ^ A000040(k) - 1) (see A073668). - _Eric Desbiaux_, Jan 20 2014

%C The average order of a(n): sum_{1<=k<=n} a(k) ~ sum_{1<=k<=n} log log k. - _Daniel Forgues_, Aug 13-16 2015

%D M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 844.

%D J. Peters, A. Lodge and E. J. Ternouth, E. Gifford, Factor Table (n<100000) (British Association Mathematical Tables Vol.V), Burlington House/Cambridge University Press London 1935.

%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="/A001221/b001221.txt">Table of n, a(n) for n = 1..100000</a> (first 10000 from NJAS)

%H M. Abramowitz and I. A. Stegun, eds., <a href="http://apps.nrbook.com/abramowitz_and_stegun/index.html">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].

%H H. Bottomley, <a href="http://www.se16.info/js/factor.htm">Prime factors calculator</a>

%H J. Brennen, <a href="http://www.brennen.net/primes/FactorApplet.html">Prime Factoring Applet</a>

%H J. Britton, <a href="http://britton.disted.camosun.bc.ca/jbprimefactor.htm">Prime Factorization Machine</a>

%H A. Dendane, <a href="http://www.analyzemath.com/Calculators_3/prime_factors.html">Prime Factors Calculator</a>

%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 J. Flament, <a href="http://jocelyn.smoofy.net/np/decomposition.php">Decomposition d'un nombre en facteurs premiers</a>

%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 A. Hodges, <a href="http://www.cryptographic.co.uk/factorise.html">Java Applet for Factorisation</a>

%H M. Kac, <a href="http://www.gibbs.if.usp.br/~marchett/estocastica/MarkKac-Statistical-Independence.pdf">Statistical Independence in Probability, Analysis and Number Theory</a>, Carus Monograph 12, Math. Assoc. Amer., 1959, see p. 64.

%H S. O. S. Math, <a href="http://www.sosmath.com/tables/factor/factor.html">Prime factorization of the first 1000 integers</a>

%H K. Matthews, <a href="http://www.numbertheory.org/php/factor.html">Factorization and calculating phi(n),omega(n),d(n),sigma(n) and mu(n)</a>

%H J. Moyer, <a href="http://www.rsok.com/~jrm/factor.html">"Prime Factors of Integers" server for numbers up to 10^36</a>

%H Primefan, <a href="http://primefan.tripod.com/500factored.html">The First 2500 Integers,Factored</a>

%H Primefan, <a href="http://primefan.tripod.com/Factorer.html">Factorer</a>

%H F. Richman, <a href="http://math.fau.edu/Richman/mla/factor-f.htm">Factoring into Primes</a>

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

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

%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/PrimeZetaFunction.html">Prime zeta function primezeta(s)</a>.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Prime_factor">Prime factor</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Table_of_prime_factors">Table of prime factors</a>

%H D. Williams, <a href="http://www.louisville.edu/~dawill03/crypto/Factoring.html">Factoring</a>

%H G. Xiao, WIMS server, <a href="http://wims.unice.fr/~wims/en_tool~algebra~factor.en.html">Factoris</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>

%F G.f.: sum(k>=1, x^prime(k)/(1-x^prime(k))). - _Benoit Cloitre_, Apr 21 2003

%F G.f.: sum(i>=1, isprime(i)*x^i/(1-x^i)), where isprime(n) returns 1 is n is prime, 0 otherwise. - _Jon Perry_, Jul 03 2004

%F Dirichlet generating function: zeta(s)*primezeta(s). - _Franklin T. Adams-Watters_, Sep 11 2005

%F Additive with a(p^e) = 1.

%F a(1) = 0, a(p) = 1, a(pq) = 2, a(pq...z) = k, a(p^k) = 1, where p, q,...,z are k distinct primes and k natural numbers. - _Jaroslav Krizek_, May 04 2009

%F a(n) = log_2(Sum(d|n, mu(d)^2)). - _Enrique PĂ©rez Herrero_, Jul 09 2012

%F a(A002110(n)) = n, i.e., a(prime(n)#) = n. - _Jean-Marc Rebert_, Jul 23 2015

%F a(n) = A091221(A091202(n)) = A069010(A156552(n)). - _Antti Karttunen_, circa 2004 & Mar 06 2017

%p A001221 := proc(n) local t1, i; if n = 1 then return 0 else t1 := 0; for i to n do if n mod ithprime(i) = 0 then t1 := t1 + 1 end if end do end if; t1 end proc;

%p A001221 := proc(n) nops(numtheory[factorset](n)) end proc: # _Emeric Deutsch_

%t Array[ Length[ FactorInteger[ # ] ]&, 100 ]

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

%o (MuPAD) func(nops(numlib::primedivisors(n)), n):

%o (MuPad) numlib::omega(n)$ n=1..110 // _Zerinvary Lajos_, May 13 2008

%o (PARI) a(n)=omega(n)

%o (Sage)

%o def A001221(n) : return len(filter(is_prime, divisors(n)))

%o [A001221(n) for n in (1..80)] # _Peter Luschny_, Feb 01 2012

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

%o (Haskell)

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

%o a001221 = length . snd . unzip . factorise

%o -- _Reinhard Zumkeller_, Nov 28 2015

%o (Python)

%o from sympy.ntheory import primefactors

%o print [len(primefactors(n)) for n in xrange(1, 10001)] # _Indranil Ghosh_, Mar 19 2017

%Y Cf. A001222 (primes counted with multiplicity), A046660. Partial sums give A013939.

%Y Cf. A069010, A087624, A091202, A091221, A143519, A144494, A158210, A156542, A156552.

%K nonn,easy,nice,core

%O 1,6

%A _N. J. A. Sloane_

%E G.f. corrected by _Franklin T. Adams-Watters_, Sep 01 2009

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 December 13 01:33 EST 2017. Contains 295954 sequences.