cp's OEIS Frontend

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

%I A101638 #22 May 27 2025 15:00:10
%S A101638 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 A101638 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 A101638 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 A101638 Number of distinct 4-almost primes A014613 which are factors of n.
%C A101638 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 A101638 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 A101638 Charles R Greathouse IV, <a href="/A101638/b101638.txt">Table of n, a(n) for n = 1..10000</a>
%H A101638 E. A. Bender and J. R. Goldman, <a href="https://web.archive.org/web/20240530103859/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 A101638 M. Bernstein and N. J. A. Sloane, <a href="https://arxiv.org/abs/math/0205301">Some canonical sequences of integers</a>, arXiv:math/0205301 [math.CO], 2002; Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to arXiv version]
%H A101638 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 A101638 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/AlmostPrime.html">Almost Prime</a>.
%H A101638 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/MoebiusTransform.html">Moebius Transform</a>.
%e A101638 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 A101638 (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 A101638 Cf. A101638, A014613, A000332, A086971, A100605, A000040, A001358, A014612, A014614.
%K A101638 easy,nonn
%O A101638 1,48
%A A101638 _Jonathan Vos Post_, Dec 10 2004