A001221 - OEIS (original) (raw)

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, 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, 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

COMMENTS

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

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.

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.

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)

Equals double inverse Mobius transform of A143519, where A051731 = the inverse Mobius transform. - Gary W. Adamson, Aug 22 2008

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]

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

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

We can use A001221 and A001222 to classify the positive integers as follows.

Restricting to n > 1:

Inverse Möbius transform of the characteristic function of primes (A010051). - Wesley Ivan Hurt, Jun 22 2024

REFERENCES

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.

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.

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).

LINKS

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].

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.

Eric Weisstein's World of Mathematics, Prime Factor

FORMULA

Additive with a(p^e) = 1.

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

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

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

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

a(n) = Sum_{p|n, p prime} 1.

a(n) = Sum_{d|n} c(d), where c = A010051. (End)

MAPLE

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;

MATHEMATICA

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

PROG

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

(MuPAD) numlib::omega(n)$ n=1..110 // Zerinvary Lajos, May 13 2008

(PARI) a(n)=omega(n)

(Sage)

def A001221(n): return sum(1 for p in divisors(n) if is_prime(p))

(SageMath) [gp.omega(n) for n in range(1, 101)] # G. C. Greubel, Jul 13 2024

(Haskell)

import Math.NumberTheory.Primes.Factorisation (factorise)

a001221 = length . snd . unzip . factorise

(Python)

from sympy.ntheory import primefactors

print([len(primefactors(n)) for n in range(1, 1001)]) # Indranil Ghosh, Mar 19 2017

(Magma) [#PrimeDivisors(n): n in [1..120]]; // Bruno Berselli, Oct 15 2021

(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) for n in 1:60]) # Peter Luschny, Jan 02 2024

CROSSREFS

Cf. also A125666, A069010, A087624, A091202, A091221, A143519, A144494, A158210, A156542, A156552, A000010, A008683.

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).

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).