cp's OEIS Frontend

A101606 a(n) = number of divisors of n that have exactly three (not necessarily distinct) prime factors.

%I A101606 #30 May 27 2025 15:00:06
%S A101606 0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,2,0,0,1,1,0,1,0,1,0,0,
%T A101606 0,2,0,0,0,2,0,1,0,1,1,0,0,2,0,1,0,1,0,2,0,2,0,0,0,3,0,0,1,1,0,1,0,1,
%U A101606 0,1,0,3,0,0,1,1,0,1,0,2,1,0,0,3,0,0,0,2,0,3,0,1,0,0,0,2,0,1,1,2,0,1,0,2,1
%N A101606 a(n) = number of divisors of n that have exactly three (not necessarily distinct) prime factors.
%C A101606 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).
%D A101606 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 A101606 Antti Karttunen, <a href="/A101606/b101606.txt">Table of n, a(n) for n = 1..10000</a>
%H A101606 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 A101606 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 A101606 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 A101606 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/AlmostPrime.html">Almost Prime</a>.
%H A101606 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/MoebiusTransform.html">Moebius Transform</a>.
%H A101606 <a href="/index/Eu#epf">Index entries for sequences computed from exponents in factorization of n</a>
%F A101606 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).
%F A101606 a(n) = Sum_{d|n} A101605(d). - _Antti Karttunen_, Jul 23 2017
%e A101606 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.
%p A101606 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
%t A101606 a[n_] := DivisorSum[n, Boole[PrimeOmega[#] == 3]&];
%t A101606 Array[a, 105] (* _Jean-François Alcover_, Nov 14 2017 *)
%o A101606 (PARI) A101606(n) = sumdiv(n,d,(3==bigomega(d))); \\ _Antti Karttunen_, Jul 23 2017
%Y A101606 Cf. A101605, A014612, A001358, A064911, A001221, A000005, A000010, A004018, A000292.
%K A101606 easy,nonn
%O A101606 1,24
%A A101606 _Jonathan Vos Post_, Dec 09 2004
%E A101606 a(48) replaced with 2 and a(76) replaced with 1 by _R. J. Mathar_, Jan 27 2009
%E A101606 Name changed by _Antti Karttunen_, Jul 23 2017