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

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

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

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

Example

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.

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

Prog

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

Crossrefs

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

Sequence in context: A128582 A213185 A285716 * A257469 A275947 A337976

Adjacent sequences: A101603 A101604 A101605 * A101607 A101608 A101609

Keyword

easy,nonn

Author

Jonathan Vos Post, Dec 09 2004

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

Status

approved