cp's OEIS Frontend

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

%I A001221 M0056 N0019 #206 Jul 15 2025 21:40:26
%S A001221 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 A001221 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 A001221 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 A001221 Number of distinct primes dividing n (also called omega(n)).
%C A001221 From Peter C. Heinig (algorithms(AT)gmx.de), Mar 08 2008: (Start)
%C A001221 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 A001221 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 A001221 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 A001221 Equals double inverse Mobius transform of A143519, where A051731 = the inverse Mobius transform. - _Gary W. Adamson_, Aug 22 2008
%C A001221 a(n) is the number of unitary prime power divisors of n (not including 1). - _Jaroslav Krizek_, May 04 2009 [corrected by _Ilya Gutkovskiy_, Oct 09 2019]
%C A001221 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 A001221 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 A001221 The average order of a(n): Sum_{k=1..n} a(k) ~ Sum_{k=1..n} log log k. - _Daniel Forgues_, Aug 13-16 2015
%C A001221 From _Peter Luschny_, Jul 13 2023: (Start)
%C A001221 We can use A001221 and A001222 to classify the positive integers as follows.
%C A001221    A001222(n) = A001221(n) = 0 singles out {1}.
%C A001221 Restricting to n > 1:
%C A001221    A001222(n)^A001221(n) = 1: A000040, prime numbers.
%C A001221    A001221(n)^A001222(n) = 1: A246655, prime powers.
%C A001221    A001222(n)^A001221(n) > 1: A002808, the composite numbers.
%C A001221    A001221(n)^A001222(n) > 1: A024619, complement of A246655.
%C A001221    n^(A001222(n) - A001221(n)) = 1: A144338, products of distinct primes. (End)
%C A001221 Inverse Möbius transform of the characteristic function of primes (A010051). - _Wesley Ivan Hurt_, Jun 22 2024
%C A001221 Dirichlet convolution of A010051(n) and 1. - _Wesley Ivan Hurt_, Jul 15 2025
%D A001221 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 A001221 G. H. Hardy, Ramanujan: twelve lectures on subjects suggested by his life and work, Cambridge, University Press, 1940, pp. 48-57.
%D A001221 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 A001221 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001221 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A001221 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 A001221 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 A001221 Henry Bottomley, <a href="http://www.se16.info/js/factor.htm">Prime factors calculator</a>
%H A001221 J. Brennen, <a href="http://www.brennen.net/primes/FactorApplet.html">Prime Factoring Applet</a>
%H A001221 J. Britton, <a href="http://britton.disted.camosun.bc.ca/jbprimefactor.htm">Prime Factorization Machine</a>
%H A001221 A. Dendane, <a href="http://www.analyzemath.com/Calculators_3/prime_factors.html">Prime Factors Calculator</a>
%H A001221 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 A001221 J. Flament, <a href="http://jocelyn.smoofy.net/np/decomposition.php">Decomposition d'un nombre en facteurs premiers</a>
%H A001221 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 A001221 A. Hodges, <a href="http://www.cryptographic.co.uk/factorise.html">Java Applet for Factorisation</a>
%H A001221 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 A001221 S. O. S. Math, <a href="http://www.sosmath.com/tables/factor/factor.html">Prime factorization of the first 1000 integers</a>
%H A001221 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 A001221 J. Moyer, <a href="http://www.rsok.com/~jrm/factor.html">"Prime Factors of Integers" server for numbers up to 10^36</a>
%H A001221 Primefan, <a href="http://primefan.tripod.com/500factored.html">The First 2500 Integers,Factored</a>
%H A001221 Primefan, <a href="http://primefan.tripod.com/Factorer.html">Factorer</a>
%H A001221 F. Richman, <a href="http://math.fau.edu/Richman/mla/factor-f.htm">Factoring into Primes</a>
%H A001221 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/DistinctPrimeFactors.html">Distinct Prime Factors</a>
%H A001221 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/MoebiusTransform.html">Moebius Transform</a>
%H A001221 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PrimeFactor.html">Prime Factor</a>
%H A001221 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PrimeZetaFunction.html">Prime zeta function primezeta(s)</a>.
%H A001221 Wikipedia, <a href="http://en.wikipedia.org/wiki/Prime_factor">Prime factor</a>
%H A001221 Wikipedia, <a href="http://en.wikipedia.org/wiki/Table_of_prime_factors">Table of prime factors</a>
%H A001221 G. Xiao, WIMS server, <a href="http://wims.unice.fr/~wims/en_tool~algebra~factor.en.html">Factoris</a>
%H A001221 <a href="/index/Cor#core">Index entries for "core" sequences</a>
%H A001221 <a href="/index/Eu#epf">Index entries for sequences computed from exponents in factorization of n</a>
%F A001221 G.f.: Sum_{k>=1} x^prime(k)/(1-x^prime(k)). - _Benoit Cloitre_, Apr 21 2003; corrected by _Franklin T. Adams-Watters_, Sep 01 2009
%F A001221 Dirichlet generating function: zeta(s)*primezeta(s). - _Franklin T. Adams-Watters_, Sep 11 2005
%F A001221 Additive with a(p^e) = 1.
%F A001221 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 A001221 a(n) = log_2(Sum_{d|n} mu(d)^2). - _Enrique Pérez Herrero_, Jul 09 2012
%F A001221 a(A002110(n)) = n, i.e., a(prime(n)#) = n. - _Jean-Marc Rebert_, Jul 23 2015
%F A001221 a(n) = A091221(A091202(n)) = A069010(A156552(n)). - _Antti Karttunen_, circa 2004 & Mar 06 2017
%F A001221 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
%F A001221 a(n) = log_2(Sum_{k=1..n} mu(gcd(n,k))^2/phi(n/gcd(n,k))) = log_2(Sum_{k=1..n} mu(n/gcd(n,k))^2/phi(n/gcd(n,k))), where phi = A000010 and mu = A008683. - _Richard L. Ollerton_, May 13 2021
%F A001221 Sum_{k=1..n} 2^(-a(gcd(n,k)) - A001222(n/gcd(n,k)))/phi(n/gcd(n,k)) = Sum_{k=1..n} 2^(-A001222(gcd(n,k)) - a(n/gcd(n,k)))/phi(n/gcd(n,k)) = 1, where phi = A000010. - _Richard L. Ollerton_, May 13 2021
%F A001221 a(n) = A005089(n) + A005091(n) + A059841(n) = A005088(n) +A005090(n) +A079978(n). - _R. J. Mathar_, Jul 22 2021
%F A001221 From _Wesley Ivan Hurt_, Jun 22 2024: (Start)
%F A001221 a(n) = Sum_{p|n, p prime} 1.
%F A001221 a(n) = Sum_{d|n} c(d), where c = A010051. (End)
%p A001221 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 A001221 := proc(n) nops(numtheory[factorset](n)) end proc: # _Emeric Deutsch_
%p A001221 omega := n -> NumberTheory:-NumberOfPrimeFactors(n, 'distinct'): # _Peter Luschny_, Jun 15 2025
%t A001221 Array[ Length[ FactorInteger[ # ] ]&, 100 ]
%t A001221 PrimeNu[Range[120]]  (* _Harvey P. Dale_, Apr 26 2011 *)
%o A001221 (MuPAD) func(nops(numlib::primedivisors(n)), n):
%o A001221 (MuPAD) numlib::omega(n)$ n=1..110 // _Zerinvary Lajos_, May 13 2008
%o A001221 (PARI) a(n)=omega(n)
%o A001221 (Sage)
%o A001221 def A001221(n): return sum(1 for p in divisors(n) if is_prime(p))
%o A001221 [A001221(n) for n in (1..80)] # _Peter Luschny_, Feb 01 2012
%o A001221 (SageMath) [sloane.A001221(n) for n in (1..111)] # _Giuseppe Coppoletta_, Jan 19 2015
%o A001221 (SageMath) [gp.omega(n) for n in range(1,101)] # _G. C. Greubel_, Jul 13 2024
%o A001221 (Haskell)
%o A001221 import Math.NumberTheory.Primes.Factorisation (factorise)
%o A001221 a001221 = length . snd . unzip . factorise
%o A001221 -- _Reinhard Zumkeller_, Nov 28 2015
%o A001221 (Python)
%o A001221 from sympy.ntheory import primefactors
%o A001221 print([len(primefactors(n)) for n in range(1, 1001)])  # _Indranil Ghosh_, Mar 19 2017
%o A001221 (Magma) [#PrimeDivisors(n): n in [1..120]]; // _Bruno Berselli_, Oct 15 2021
%o A001221 (Julia)
%o A001221 using Nemo
%o A001221 function NumberOfPrimeFactors(n; distinct=true)
%o A001221     distinct && return length(factor(ZZ(n)))
%o A001221     sum(e for (p, e) in factor(ZZ(n)); init=0)
%o A001221 end
%o A001221 println([NumberOfPrimeFactors(n) for n in 1:60]) # _Peter Luschny_, Jan 02 2024
%Y A001221 Cf. A001222 (primes counted with multiplicity), A046660, A285577, A346617. Partial sums give A013939.
%Y A001221 Cf. also A125666, A069010, A087624, A091202, A091221, A143519, A144494, A158210, A156542, A156552, A000010, A008683.
%Y A001221 Sum of the k-th powers of the primes dividing n for k=0..10: this sequence (k=0), A008472 (k=1), A005063 (k=2), A005064 (k=3), A005065 (k=4), A351193 (k=5), A351194 (k=6), A351195 (k=7), A351196 (k=8), A351197 (k=9), A351198 (k=10).
%Y A001221 Sequences of the form n^k * Sum_{p|n, p prime} 1/p^k for k=0..10: this sequence (k=0), A069359 (k=1), A322078 (k=2), A351242 (k=3), A351244 (k=4), A351245 (k=5), A351246 (k=6), A351247 (k=7), A351248 (k=8), A351249 (k=9), A351262 (k=10).
%K A001221 nonn,easy,nice,core
%O A001221 1,6
%A A001221 _N. J. A. Sloane_