A101606 a(n) = number of divisors of n that have exactly three (not necessarily distinct) prime factors.

0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 2, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 2, 0, 0, 0, 2, 0, 1, 0, 1, 1, 0, 0, 2, 0, 1, 0, 1, 0, 2, 0, 2, 0, 0, 0, 3, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 3, 0, 0, 1, 1, 0, 1, 0, 2, 1, 0, 0, 3, 0, 0, 0, 2, 0, 3, 0, 1, 0, 0, 0, 2, 0, 1, 1, 2, 0, 1, 0, 2, 1

Offset: 1

Author

Jonathan Vos Post, Dec 09 2004

Keywords

• easy
• nonn

Comments

This is the inverse Moebius transform of A101605. If n = (p1^e1)*(p2^e2)* ... * (pj^ej) then a(n) = |{k: ek>=3}| + ((j-1)/2)*|{k: ek>=2}| + C(j,3). The first term is the number of distinct cubes of primes in the factors of n (the first way of finding a 3-almost prime). The second term is the number of distinct squares of primes, each of which can be multiplied by any of the other distinct primes, halved to avoid double-counts (the second way of finding a 3-almost prime). The third term is the number of distinct products of 3 distinct primes, which is the number of combinations of j primes taken 3 at a time, A000292(j), (the third way of finding a 3-almost prime).

Examples

			a(60) = 3 because of all the divisors of 60 only these three are terms of A014612: 12 = 2 * 2 * 3; 20 = 2 * 2 * 5; 30 = 2 * 3 * 5.
		

References

• Hardy, G. H. and Wright, E. M. Section 17.10 in An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, 1979.

Links

• Antti Karttunen, Table of n, a(n) for n = 1..10000
• E. A. Bender and J. R. Goldman, On the Applications of Moebius Inversion in Combinatorial Analysis, Amer. Math. Monthly 82, 789-803, 1975.
• M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, arXiv:math/0205301 [math.CO], 2002; Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to arXiv version]
• M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]
• Eric Weisstein's World of Mathematics, Almost Prime.
• Eric Weisstein's World of Mathematics, Moebius Transform.
• Index entries for sequences computed from exponents in factorization of n

Crossrefs

Cf. A101605, A014612, A001358, A064911, A001221, A000005, A000010, A004018, A000292.

Programs

Maple

isA014612 := proc(n) option remember ; RETURN( numtheory[bigomega](n) = 3) ; end: A101606 := proc(n) a :=0 ; for d in numtheory[divisors](n) do if isA014612(d) then a := a+1 ; fi; od: a ; end: for n from 1 to 120 do printf("%d,",A101606(n)) ; od: # R. J. Mathar, Jan 27 2009

Mathematica

a[n_] := DivisorSum[n, Boole[PrimeOmega[#] == 3]&];
Array[a, 105] (* Jean-François Alcover, Nov 14 2017 *)

PARI

A101606(n) = sumdiv(n,d,(3==bigomega(d))); \\ Antti Karttunen, Jul 23 2017

Formula

If n = (p1^e1 * p2^e2 * ... * pj^ej) for primes p1, p2, ..., pj and integer exponents e1, e2, ..., ej, then a(n) = a(n) = |{k: ek>=3}| + ((j-1)/2)*|{k: ek>=2}| + C(j, 3). where C(j, 3) is the binomial coefficient A000292(j).

a(n) = Sum_{d|n} A101605(d). - Antti Karttunen, Jul 23 2017

Extensions

a(48) replaced with 2 and a(76) replaced with 1 by R. J. Mathar, Jan 27 2009

Name changed by Antti Karttunen, Jul 23 2017