|
%I M0056 N0019 #191 Jan 03 2024 05:05:52
%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) 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 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_{k=1..n} a(k) ~ Sum_{k=1..n} log log k. - _Daniel Forgues_, Aug 13-16 2015
%C From _Peter Luschny_, Jul 13 2023: (Start)
%C We can use A001221 and A001222 to classify the positive integers as follows.
%C A001222(n) = A001221(n) = 0 singles out {1}.
%C Restricting to n > 1:
%C A001222(n)^A001221(n) = 1: A000040, prime numbers.
%C A001221(n)^A001222(n) = 1: A246655, prime powers.
%C A001222(n)^A001221(n) > 1: A002808, the composite numbers.
%C A001221(n)^A001222(n) > 1: A024619, complement of A246655.
%C n^(A001222(n) - A001221(n)) = 1: A144338, products of distinct primes. (End)
%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 Henry 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 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; corrected by _Franklin T. Adams-Watters_, Sep 01 2009
%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
%F 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 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 a(n) = A005089(n) + A005091(n) + A059841(n) = A005088(n) +A005090(n) +A079978(n). - _R. J. Mathar_, Jul 22 2021
%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 sum(1 for p in divisors(n) if is_prime(p))
%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 range(1, 1001)]) # _Indranil Ghosh_, Mar 19 2017
%o (Magma) [#PrimeDivisors(n): n in [1..120]]; // _Bruno Berselli_, Oct 15 2021
%o (Julia)
%o using Nemo
%o function NumberOfPrimeFactors(n; distinct=true)
%o distinct && return length(factor(ZZ(n)))
%o sum(e for (p, e) in factor(ZZ(n)); init=0)
%o end
%o println([NumberOfPrimeFactors(n) for n in 1:60]) # _Peter Luschny_, Jan 02 2024
%Y Cf. A001222 (primes counted with multiplicity), A046660, A285577, A346617. Partial sums give A013939.
%Y Cf. also A125666, A069010, A087624, A091202, A091221, A143519, A144494, A158210, A156542, A156552, A000010, A008683.
%Y 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 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 nonn,easy,nice,core
%O 1,6
%A _N. J. A. Sloane_
|
