|
%I #17 Oct 05 2017 11:34:36
%S 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,
%T 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,
%U 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
%N Number of distinct 4-almost primes A014613 which are factors of n.
%C 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).
%D 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.
%H Charles R Greathouse IV, <a href="/A101638/b101638.txt">Table of n, a(n) for n = 1..10000</a>
%H E. A. Bender and J. R. Goldman, <a href="https://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/BenderGoldman.pdf">On the Applications of Moebius Inversion in Combinatorial Analysis</a>, Amer. Math. Monthly 82, 789-803, 1975.
%H M. Bernstein and N. J. A. Sloane, <a href="http://arXiv.org/abs/math.CO/0205301">Some canonical sequences of integers</a>, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to arXiv version]
%H M. Bernstein and N. J. A. Sloane, <a href="/A003633/a003633_1.pdf">Some canonical sequences of integers</a>, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/AlmostPrime.html">Almost Prime.</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MoebiusTransform.html">Moebius Transform.</a>.
%e 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.
%o (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
%Y Cf. A101638, A014613, A000332, A086971, A100605, A000040, A001358, A014612, A014614.
%K easy,nonn
%O 1,48
%A _Jonathan Vos Post_, Dec 10 2004
|
