A074946 -id:A074946 - cp's OEIS frontend

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

N. J. A. Sloane

Maximal number of terms in any factorization of n.
Number of prime powers (not including 1) that divide n.
Sum of exponents in prime-power factorization of n. - Daniel Forgues, Mar 29 2009
Sum_{d|n} 2^(-A001221(d) - a(n/d)) = Sum_{d|n} 2^(-a(d) - A001221(n/d)) = 1 (see Dressler and van de Lune link). - Michel Marcus, Dec 18 2012
Row sums in A067255. - Reinhard Zumkeller, Jun 11 2013
Conjecture: Let f(n) = (x+y)^a(n), and g(n) = x^a(n), and h(n) = (x+y)^A046660(n) * y^A001221(n) with x, y complex numbers and 0^0 = 1. Then f(n) = Sum_{d|n} g(d)*h(n/d). This is proved for x = 1-y (see Dressler and van de Lune link). - Werner Schulte, Feb 10 2018
Let r, s be some fixed integers. Then we have:
  (1) The sequence b(n) = Dirichlet convolution of r^bigomega(n) and s^bigomega(n) is multiplicative with b(p^e) = (r^(e+1)-s^(e+1))/(r-s) for prime p and e >= 0. The case r = s leads to b(p^e) = (e+1)*r^e.
  (2) The sequence c(n) = Dirichlet convolution of r^bigomega(n) and mu(n)*s^bigomega(n) is multiplicative with c(p^e) = (r-s)*r^(e-1) and c(1) = 1 for prime p and e > 0 where mu(n) = A008683(n). - Werner Schulte, Feb 20 2019
a(n) is also the length of the composition series for every solvable group of order n. - Miles Englezou, Apr 25 2024

			16=2^4, so a(16)=4; 18=2*3^2, so a(18)=3.

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.

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

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. A000120, A020639, A091202, A091222, A156552, A267116, A268387.
Cf. A027748 (without repetition).
Cf. A000010.

Concatenation([0],List([2..150],n->Length(Factors(n)))); # Muniru A Asiru, Feb 21 2019

import Math.NumberTheory.Primes.Factorisation (factorise)
a001222 = sum . snd . unzip . factorise
-- Reinhard Zumkeller, Nov 28 2015

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

[n eq 1 select 0 else &+[p[2]: p in Factorization(n)]: n in [1..120]]; // Bruno Berselli, Nov 27 2013

with(numtheory): seq(bigomega(n), n=1..111);

Array[ Plus @@ Last /@ FactorInteger[ # ] &, 105]
PrimeOmega[Range[120]] (* Harvey P. Dale, Apr 25 2011 *)

PARI
```
vector(100,n,bigomega(n))
```

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

[sloane.A001222(n) for n in (1..120)] # Giuseppe Coppoletta, Jan 19 2015

[gp.bigomega(n) for n in range(1,131)] # G. C. Greubel, Jul 13 2024

(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

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
a(n) = Sum_{k=1..A001221(n)} A124010(n,k). - Reinhard Zumkeller, Aug 27 2011
a(n) = A022559(n) - A022559(n-1).
G.f.: Sum_{p prime, k>=1} x^(p^k)/(1 - x^(p^k)). - Ilya Gutkovskiy, Jan 25 2017
a(n) = A091222(A091202(n)) = A000120(A156552(n)). - Antti Karttunen, circa 2004 and Mar 06 2017
a(n) >= A267116(n) >= A268387(n). - Antti Karttunen, Apr 12 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
a(n) = a(A046523(n)) = A007814(A108951(n)) = A061395(A122111(n)) = A056239(A181819(n)) = A048675(A293442(n)). - Antti Karttunen, Apr 30 2022

More terms from David W. Wilson

A075592 Numbers n such that number of distinct prime divisors of n is a divisor of n.

Original entry on oeis.org

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 34, 36, 37, 38, 40, 41, 42, 43, 44, 46, 47, 48, 49, 50, 52, 53, 54, 56, 58, 59, 60, 61, 62, 64, 66, 67, 68, 71, 72, 73, 74, 76, 78, 79, 80, 81, 82, 83, 84, 86, 88, 89, 90

Offset: 1

Amarnath Murthy, Sep 26 2002

Numbers n such that omega(n) divides n.

The asymptotic density of this sequence is 0 (Cooper and Kennedy, 1989). - Amiram Eldar, Jul 10 2020

Christian N. K. Anderson, Table of n, a(n) for n = 1..10000
Curtis N. Cooper, Robert E. Kennedy, Chebyshev's inequality and natural density, Amer. Math. Monthly 96 (1989), no. 2, 118-124.

Different from A070776: 78 belongs to this sequence but not to A070776.

Cf. A185307 (complement), A001221, A001222, A074946 (BigOmega(n) divides n).

Select[Range[2,100],Divisible[#,Length[Select[Divisors[#], PrimeQ]]]&]  (* Harvey P. Dale, Mar 17 2011 *)

isok(n) = iferr(!(n % omega(n)), E, 0); \\ Michel Marcus, Oct 06 2017

library(gmp); omega<-function(x) length(unique(as.numeric(factorize(x))))
which(c(F,vapply(2:100,function(n) isint(n/omega(n)),T))) # Christian N. K. Anderson, Apr 25 2013

More terms from David Wasserman, Jan 20 2005

"Distinct" added to name by Christian N. K. Anderson, Apr 23 2013

A134334 Numbers which are not divisible by the number of their prime factors (counted with multiplicity).

Original entry on oeis.org

8, 9, 15, 20, 21, 25, 28, 32, 33, 35, 39, 44, 48, 49, 50, 51, 52, 54, 55, 57, 64, 65, 68, 69, 70, 72, 76, 77, 81, 85, 87, 90, 91, 92, 93, 95, 98, 108, 110, 111, 112, 115, 116, 119, 121, 123, 124, 125, 126, 128, 129, 130, 133, 135, 141, 143, 145, 148, 150, 154, 155, 159

Offset: 1

Hieronymus Fischer, Oct 23 2007

nonn

The asymptotic density of this sequence is 1 (Erdős and Pomerance, 1990). - Amiram Eldar, Jul 10 2020

			a(1) = 8, since 8 = 2*2*2 has 3 prime factors and 8 is not divisible by 3.
a(3) = 15, since 15 = 3*5 has 2 prime factors and 15 is not divisible by 2.

Hieronymus Fischer, Table of n, a(n) for n = 1..10000
Paul Erdős and Carl Pomerance, On a theorem of Besicovitch: values of arithmetic functions that divide their arguments, Indian J. Math., Vol. 32 (1990), pp. 279-287.

Cf. A000040, A001222, A074946 (complement), A100118, A046363, A133620, A133621.

Cf. A133880, A133890, A133900, A133910, A133911, A046346, A134331, A134332, A134333, A134335, A134344, A134376.

Select[Range[2,200],Mod[#,PrimeOmega[#]]!=0&] (* Harvey P. Dale, May 13 2023 *)

isok(n) = (n % bigomega(n)) \\ Michel Marcus, Jul 15 2013

A336064 Numbers divisible by the maximal exponent in their prime factorization (A051903).

Original entry on oeis.org

2, 3, 4, 5, 6, 7, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 27, 28, 29, 30, 31, 33, 34, 35, 36, 37, 38, 39, 41, 42, 43, 44, 46, 47, 48, 50, 51, 52, 53, 54, 55, 57, 58, 59, 60, 61, 62, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 76, 77, 78, 79

Offset: 1

Amiram Eldar, Jul 07 2020

nonn

The asymptotic density of this sequence is A336065 = 0.848957... (Schinzel and Šalát, 1994).

			4 = 2^2 is a term since A051903(4) = 2 is a divisor of 4.

József Sándor and Borislav Crstici, Handbook of Number theory II, Kluwer Academic Publishers, 2004, chapter 3, p. 331.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Andrzej Schinzel and Tibor Šalát, Remarks on maximum and minimum exponents in factoring, Mathematica Slovaca, Vol. 44, No. 5 (1994), pp. 505-514.

Cf. A051903, A124184, A336065.
A005117 (except for 1) is subsequence.
Similar sequences: A033950, A005349, A006446, A074946, A075592, A007694, A112249, A336063.

H[1] = 0; H[n_] := Max[FactorInteger[n][[;; , 2]]]; Select[Range[2, 100], Divisible[#, H[#]] &]

isok(m) = if (m>1, (m % vecmax(factor(m)[,2])) == 0); \\ Michel Marcus, Jul 08 2020

A185307 Numbers not divisible by the number of their distinct prime factors.

Original entry on oeis.org

1, 15, 21, 33, 35, 39, 45, 51, 55, 57, 63, 65, 69, 70, 75, 77, 85, 87, 91, 93, 95, 99, 110, 111, 115, 117, 119, 123, 129, 130, 133, 135, 140, 141, 143, 145, 147, 153, 154, 155, 159, 161, 170, 171, 175, 177, 182, 183, 185, 187, 189, 190, 201, 203, 205, 207, 209

Offset: 1

Christian N. K. Anderson and Kevin L. Schwartz, Apr 23 2013

nonn

The complement of A075592 (omega(n) divides n).
Though initially sparse, the sequence increases in density. There are more numbers divisible by omega(n) than not from [3,9265], but there are always more indivisible numbers thereafter.
There are 308 more numbers divisible than indivisible in the range from 1 to 2754, 2778, and 2880. This three values are the global maxima.
The asymptotic density of this sequence is 1 (Cooper and Kennedy, 1989). - Amiram Eldar, Jul 10 2020

			The distinct prime factors of 45 are 3 and 5, but 45 is not divisible by 2.

Christian N. K. Anderson, Table of n, a(n) for n = 1..10000
Curtis N. Cooper and Robert E. Kennedy, Chebyshev's inequality and natural density, Amer. Math. Monthly, Vol. 96, No. 2 (1989), pp. 118-124.

Cf. A075592 (complement), A001221, A001222, A074946, A134334.

Join[{1},Select[Range[2,300],Mod[#,PrimeNu[#]]!=0&]] (* Harvey P. Dale, Jun 05 2023 *)

isok(n) = iferr(n % omega(n), E, 1); \\ Michel Marcus, Jul 10 2020

library(numbers); isint<-function(x) x==as.integer(x); which(!vapply(1:500,function(n) isint(n/omega(n)),T))

A187778 Numbers k dividing psi(k), where psi is the Dedekind psi function (A001615).

Original entry on oeis.org

1, 6, 12, 18, 24, 36, 48, 54, 72, 96, 108, 144, 162, 192, 216, 288, 324, 384, 432, 486, 576, 648, 768, 864, 972, 1152, 1296, 1458, 1536, 1728, 1944, 2304, 2592, 2916, 3072, 3456, 3888, 4374, 4608, 5184, 5832, 6144, 6912, 7776, 8748, 9216, 10368, 11664, 12288, 13122, 13824, 15552, 17496, 18432, 20736, 23328

Offset: 1

Enrique Pérez Herrero, Jan 05 2013

nonn

This sequence is closed under multiplication.
Also 1 and the numbers where psi(n)/n = 2, or n/phi(n)=3, or psi(n)/phi(n)=6.
Also 1 and the numbers of the form 2^i*3^j with i, j >= 1 (A033845).
If M(n) is the n X n matrix whose elements m(i,j) = 2^i*3^j, with i, j >= 1, then det(M(n))=0.
Numbers n such that Product_{i=1..q} (1 + 1/d(i)) is an integer where q is the number of the distinct prime divisors d(i) of n. - Michel Lagneau, Jun 17 2016

			psi(48) = 96 and 96/48 = 2 so 48 is in this sequence.

S. Ramanujan, Collected Papers, Ed. G. H. Hardy et al., Cambridge 1927; Chelsea, NY, 1962, p. xxiv.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..191 from Vincenzo Librandi)
R. Blecksmith, M. McCallum and J. L. Selfridge, 3-smooth representations of integers, Amer. Math. Monthly, 105 (1998), 529-543.
E. Deutsch, Tree statistics from Matula numbers, arXiv:1111.4288 [math.CO], 2011.
Eric Weisstein's World of Mathematics, Smooth Number
Wikipedia, Closure

Cf. A003586, A001615, A007694, A033950, A074946, A075592.

[6*n: n in [1..3000] | PrimeDivisors(n) subset [2, 3]]; // Vincenzo Librandi, Jan 11 2019

Select[Range[10^4],#/EulerPhi[#]==3 || #==1&]
Join[{1}, 6 Select[Range@4000, Last@Map[First, FactorInteger@#]<=3 &]] (* Vincenzo Librandi, Jan 11 2019 *)

dedekindpsi(n) = if( n<1, 0, direuler( p=2, n, (1 + X) / (1 - p*X)) [n]);
k=0; n=0; while(k<10000,n++; if( dedekindpsi(n) % n== 0, k++; print1(n, ", ")));

For n > 1, a(n) = 6 * A003586(n).

Sum_{n>0} 1/a(n)^k = 1 + Sum_{i>0} Sum_{j>0} 1/(2^i * 3^j)^k = 1 + 1/((2^k-1)*(3^k-1)).

A336066 Numbers k such that the exponent of the highest power of 2 dividing k (A007814) is a divisor of k.

Original entry on oeis.org

2, 4, 6, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 34, 36, 38, 42, 44, 46, 48, 50, 52, 54, 58, 60, 62, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 90, 92, 94, 98, 100, 102, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124, 126, 130, 132, 134, 138, 140, 142, 144

Offset: 1

Amiram Eldar, Jul 07 2020

nonn

All the terms are even by definition.
If m is a term then m*(2*k+1) is a term for all k>=1.
Šalát (1994) proved that the asymptotic density of this sequence is 0.435611... (A336067).

			2 is a term since A007814(2) = 1 is a divisor of 2.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Tibor Šalát, On the function a_p, p^a_p(n) || n (n > 1), Mathematica Slovaca, Vol. 44, No. 2 (1994), pp. 143-151.

A001146 and A039956 are subsequences.
Cf. A007814, A336067.
Similar sequences: A033950, A005349, A006446, A074946, A075592, A007694, A112249, A336068.

Select[Range[2, 150, 2], Divisible[#, IntegerExponent[#, 2]] &]

isok(m) = if (!(m%2), (m % valuation(m,2)) == 0); \\ Michel Marcus, Jul 08 2020

from itertools import count, islice
def A336066_gen(startvalue=2): # generator of terms >= startvalue
    return filter(lambda n:n%(~n&n-1).bit_length()==0,count(max(startvalue+startvalue&1,2),2))
A336066_list = list(islice(A336066_gen(startvalue=3),30)) # Chai Wah Wu, Jul 10 2022

cp's OEIS Frontend

A001222 Number of prime divisors of n counted with multiplicity (also called big omega of n, bigomega(n) or Omega(n)).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Julia

Magma

Maple

Mathematica

PARI

Python

SageMath

SageMath

Scheme

Formula

Extensions

A075592 Numbers n such that number of distinct prime divisors of n is a divisor of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

R

Extensions

A134334 Numbers which are not divisible by the number of their prime factors (counted with multiplicity).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A336064 Numbers divisible by the maximal exponent in their prime factorization (A051903).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

A185307 Numbers not divisible by the number of their distinct prime factors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

R

A187778 Numbers k dividing psi(k), where psi is the Dedekind psi function (A001615).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs