A046660 Excess of n = number of prime divisors (with multiplicity) - number of prime divisors (without multiplicity).

0, 0, 0, 1, 0, 0, 0, 2, 1, 0, 0, 1, 0, 0, 0, 3, 0, 1, 0, 1, 0, 0, 0, 2, 1, 0, 2, 1, 0, 0, 0, 4, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 1, 1, 0, 0, 3, 1, 1, 0, 1, 0, 2, 0, 2, 0, 0, 0, 1, 0, 0, 1, 5, 0, 0, 0, 1, 0, 0, 0, 3, 0, 0, 1, 1, 0, 0, 0, 3, 3, 0, 0, 1, 0, 0, 0, 2, 0, 1, 0, 1, 0, 0, 0, 4, 0, 1, 1, 2, 0, 0, 0, 2, 0, 0, 0, 3, 0, 0, 0

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

a(n) depends only on prime signature of n (cf. A025487). So a(24) = a(375) since 24 = 2^3 * 3 and 375 = 3 * 5^3 both have prime signature (3, 1).

a(n) = 0 for squarefree n.

A162511(n) = (-1)^a(n). - Reinhard Zumkeller, Jul 08 2009

a(n) = the number of divisors of n that are each a composite power of a prime. - Leroy Quet, Dec 02 2009

a(A005117(n)) = 0; a(A060687(n)) = 1; a(A195086(n)) = 2; a(A195087(n)) = 3; a(A195088(n)) = 4; a(A195089(n)) = 5; a(A195090(n)) = 6; a(A195091(n)) = 7; a(A195092(n)) = 8; a(A195093(n)) = 9; a(A195069(n)) = 10. - Reinhard Zumkeller, Nov 29 2015

References

• G. H. Hardy, Ramanujan: twelve lectures on subjects suggested by his life and work, Cambridge, University Press, 1940, pp. 51-52.

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
• Mark Kac, Statistical Independence in Probability, Analysis and Number Theory, Carus Monograph 12, Math. Assoc. Amer., 1959, see p. 64.

Crossrefs

Not the same as A066301.

Cf. A001222, A001221, A003557, A056170, A136141, A257851, A261256, A264959, A005117, A060687, A195086, A195087, A195088, A195089, A195090, A195091, A195092, A195093, A195069, A275699, A275812.

Programs

Haskell

import Math.NumberTheory.Primes.Factorisation (factorise)
a046660 n = sum es - length es where es = snd $ unzip $ factorise n
-- Reinhard Zumkeller, Nov 28 2015, Jan 09 2013

Maple

with(numtheory); A046660 := n -> bigomega(n)-nops(factorset(n)):
seq(A046660(k), k=1..100); # Wesley Ivan Hurt, Oct 27 2013
# Or:
with(NumberTheory): A046660 := n -> NumberOfPrimeFactors(n) - NumberOfPrimeFactors(n, 'distinct'):  # Peter Luschny, Jul 14 2023

Mathematica

Table[PrimeOmega[n] - PrimeNu[n], {n, 50}] (* or *) muf[n_] := Module[{fi = FactorInteger[n]}, Total[Transpose[fi][[2]]] - Length[fi]]; Array[muf, 50] (* Harvey P. Dale, Sep 07 2011. The second program is several times faster than the first program for generating large numbers of terms. *)

PARI

a(n)=bigomega(n)-omega(n) \\ Charles R Greathouse IV, Nov 14 2012

PARI

a(n)=my(f=factor(n)[,2]); vecsum(f)-#f \\ Charles R Greathouse IV, Aug 01 2016

Python

from sympy import factorint
def A046660(n): return sum(e-1 for e in factorint(n).values()) # Chai Wah Wu, Jul 18 2023

Formula

a(n) = Omega(n) - omega(n) = A001222(n) - A001221(n).

Additive with a(p^e) = e - 1.

a(n) = Sum_{k = 1..A001221(n)} (A124010(n,k) - 1). - Reinhard Zumkeller, Jan 09 2013

G.f.: Sum_{p prime, k>=2} x^(p^k)/(1 - x^(p^k)). - Ilya Gutkovskiy, Jan 06 2017

Asymptotic mean: lim_{m->oo} (1/m) Sum_{k=1..m} a(k) = Sum_{p prime} 1/(p*(p-1)) = 0.773156... (A136141). - Amiram Eldar, Jul 28 2020

a(n) = Sum_{p|n} A286563(n/p,p), where p is prime. - Ridouane Oudra, Sep 13 2023

a(n) = A275812(n) - A056170(n). - Amiram Eldar, Jan 09 2024

a(n) = A001222(A003557(n)). - Peter Munn, Feb 06 2024

Extensions

More terms from David W. Wilson