OFFSET
1,48
COMMENTS
This is the inverse Moebius transform of A101637. If we take the prime factorization of n = (p1^e1)*(p2^e2)* ... * (pj^ej) then a(n) = |{k: ek>=4}| + ((j-1)/2)*|{k: ek>=3}| + C(|{k: ek>=2}|,2) + C(j,4). The first term is the number of distinct 4th powers of primes in the factors of n (the first way of finding a 4-almost prime). The second term is the number of distinct cubes 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 4-almost prime). The third term is the number of distinct pairs of squares of primes in the factors of n (the third way of finding a 4-almost prime). The 4th term is the number of distinct products of 4 distinct primes, which is the number of combinations of j primes in the factors of n taken 4 at a time, A000332(j), (the 4th way of finding a 4-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
Charles R Greathouse IV, 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..
EXAMPLE
a(96) = 2 because 96 = 16 * 6 hence divisible by the 4-almost prime 16 and also 96 = 24 * 4 hence divisible by the 4-almost prime 24.
PROG
(PARI) a(n)=my(f=factor(n)[, 2], v=apply(k->sum(i=1, #f, f[i]>k), [0..3])); v[4] + v[3]*(v[1]-1) + binomial(v[2], 2) + v[2]*binomial(v[1]-1, 2) + binomial(v[1], 4) \\ Charles R Greathouse IV, Sep 14 2015
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Jonathan Vos Post, Dec 10 2004
STATUS
approved