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