

A101606


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


16



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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} + ((j1)/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 3almost 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 doublecounts (the second way of finding a 3almost 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 3almost 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, 789803, 1975.
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226228 (1995), 5772; erratum 320 (2000), 210. [Link to arXiv version]
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226228 (1995), 5772; 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} + ((j1)/2)*{k: ek>=2} + C(j, 3). where C(j, 3) is the binomial coefficient A000292(j).
a(n) = Sum_{dn} 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] (* JeanFranç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 A125005
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



