A001222 Number of prime divisors of n counted with multiplicity (also called big omega of n, bigomega(n) or Omega(n)).
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, 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, 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
Offset: 1
Examples
16=2^4, so a(16)=4; 18=2*3^2, so a(18)=3.
References
- L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 119, #12, omega(n).
- G. H. Hardy, Ramanujan: twelve lectures on subjects suggested by his life and work, Cambridge, University Press, 1940, pp. 48-57.
- M. Kac, Statistical Independence in Probability, Analysis and Number Theory, Carus Monograph 12, Math. Assoc. Amer., 1959, see p. 64.
- N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
- James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 92.
Links
- Daniel Forgues, Table of n, a(n) for n = 1..100000 (first 10000 terms from N. J. A. Sloane)
- M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy], p. 844.
- Benoit Cloitre, A tauberian approach to RH, arXiv:1107.0812 [math.NT], 2011.
- Robert E. Dressler and Jan van de Lune, Some remarks concerning the number theoretic functions omega and Omega, Proc. Amer. Math. Soc. 41 (1973), 403-406.
- G. H. Hardy and S. Ramanujan, The normal number of prime factors of a number, Quart. J. Math. 48 (1917), 76-92. Also Collected papers of Srinivasa Ramanujan, AMS Chelsea Publ., Providence, RI (2000): 262-275.
- Douglas E. Iannucci and Urban Larsson, Game values of arithmetic functions, arXiv:2101.07608 [math.NT], 2021. Section 1.1.1. pp. 4-5.
- Amarnath Murthy and Charles Ashbacher, Generalized Partitions and Some New Ideas on Number Theory and Smarandache Sequences, Hexis, Phoenix; USA 2005. See Section 1.4, 1.10.
- Eric Weisstein's World of Mathematics, Prime Factor
- Eric Weisstein's World of Mathematics, Roundness
- Wolfram Research, First 50 numbers factored
- Index entries for "core" sequences
- Index entries for sequences computed from exponents in factorization of n
- Index entries for sequences computed from indices in prime factorization
Crossrefs
Cf. A001221 (omega, primes counted without multiplicity), A008836 (Liouville's lambda, equal to (-1)^a(n)), A046660, A144494, A074946, A134334.
Bisections give A091304 and A073093. A086436 is essentially the same sequence. Cf. A022559 (partial sums), A066829 (parity), A092248 (parity of omega).
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
Cf. A079149 (primes adj. to integers with at most 2 prime factors, a(n)<=2).
Cf. A027748 (without repetition).
Cf. A000010.
Programs
-
GAP
Concatenation([0],List([2..150],n->Length(Factors(n)))); # Muniru A Asiru, Feb 21 2019
-
Haskell
import Math.NumberTheory.Primes.Factorisation (factorise) a001222 = sum . snd . unzip . factorise -- Reinhard Zumkeller, Nov 28 2015
-
Julia
using Nemo function NumberOfPrimeFactors(n; distinct=true) distinct && return length(factor(ZZ(n))) sum(e for (p, e) in factor(ZZ(n)); init=0) end println([NumberOfPrimeFactors(n, distinct=false) for n in 1:60]) # Peter Luschny, Jan 02 2024 -
Magma
[n eq 1 select 0 else &+[p[2]: p in Factorization(n)]: n in [1..120]]; // Bruno Berselli, Nov 27 2013
-
Maple
with(numtheory): seq(bigomega(n), n=1..111);
-
Mathematica
Array[ Plus @@ Last /@ FactorInteger[ # ] &, 105] PrimeOmega[Range[120]] (* Harvey P. Dale, Apr 25 2011 *)
-
PARI
vector(100,n,bigomega(n))
-
Python
from sympy import primeomega def a(n): return primeomega(n) print([a(n) for n in range(1, 112)]) # Michael S. Branicky, Apr 30 2022
-
SageMath
[sloane.A001222(n) for n in (1..120)] # Giuseppe Coppoletta, Jan 19 2015
-
SageMath
[gp.bigomega(n) for n in range(1,131)] # G. C. Greubel, Jul 13 2024
-
Scheme
(define (A001222 n) (let loop ((n n) (z 0)) (if (= 1 n) z (loop (/ n (A020639 n)) (+ 1 z))))) ;; Requires also A020639 for which an equally naive implementation can be found under that entry. - Antti Karttunen, Apr 12 2017
Formula
n = Product_(p_j^k_j) -> a(n) = Sum_(k_j).
Dirichlet g.f.: ppzeta(s)*zeta(s). Here ppzeta(s) = Sum_{p prime} Sum_{k>=1} 1/(p^k)^s. Note that ppzeta(s) = Sum_{p prime} 1/(p^s-1) and ppzeta(s) = Sum_{k>=1} primezeta(k*s). - Franklin T. Adams-Watters, Sep 11 2005
Totally additive with a(p) = 1.
a(n) = if n=1 then 0 else a(n/A020639(n)) + 1. - Reinhard Zumkeller, Feb 25 2008
G.f.: Sum_{p prime, k>=1} x^(p^k)/(1 - x^(p^k)). - Ilya Gutkovskiy, Jan 25 2017
Sum_{k=1..n} 2^(-A001221(gcd(n,k)) - a(n/gcd(n,k)))/phi(n/gcd(n,k)) = Sum_{k=1..n} 2^(-a(gcd(n,k)) - A001221(n/gcd(n,k)))/phi(n/gcd(n,k)) = 1, where phi = A000010. - Richard L. Ollerton, May 13 2021
Extensions
More terms from David W. Wilson
Comments