This site is supported by donations to The OEIS Foundation.



(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://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].

%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

%F L.g.f.: -log(Product_{k>=1} (1 - x^prime(k))^(1/prime(k))) = Sum_{n>=1} a(n)*x^n/n. - _Ilya Gutkovskiy_, Jul 30 2018

%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 August 20 13:30 EDT 2018. Contains 313917 sequences. (Running on oeis4.)