

A101638


Number of distinct 4almost primes A014613 which are factors of n.


14



0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 2, 0, 0, 0, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)



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} + ((j1)/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 4almost 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 doublecounts (the second way of finding a 4almost 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 4almost 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 4almost prime).


REFERENCES

Bender, E. A. and Goldman, J. R. "On the Applications of Moebius Inversion in Combinatorial Analysis." Amer. Math. Monthly 82, 789803, 1975.
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
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226228 (1995), 5772; erratum 320 (2000), 210.
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 4almost prime 16 and also 96 = 24 * 4 hence divisible by the 4almost 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

Cf. A101638, A014613, A000332, A086971, A100605, A000040, A001358, A014612, A014614.
Sequence in context: A277148 A194024 A082786 * A070141 A088722 A122180
Adjacent sequences: A101635 A101636 A101637 * A101639 A101640 A101641


KEYWORD

easy,nonn


AUTHOR

Jonathan Vos Post, Dec 10 2004


STATUS

approved



