A101606 - OEIS

%I #25 Nov 14 2017 08:44:21

%S 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 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 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 a(n) = number of divisors of n that have exactly three (not necessarily distinct) prime factors.

%C 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 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 Antti Karttunen, <a href="/A101606/b101606.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>.

%H <a href="/index/Eu#epf">Index entries for sequences computed from exponents in factorization of n</a>

%F 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 a(n) = Sum_{d|n} A101605(d). - _Antti Karttunen_, Jul 23 2017

%e 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 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 a[n_] := DivisorSum[n, Boole[PrimeOmega[#] == 3]&];

%t Array[a, 105] (* _Jean-François Alcover_, Nov 14 2017 *)

%o (PARI) A101606(n) = sumdiv(n,d,(3==bigomega(d))); \\ _Antti Karttunen_, Jul 23 2017

%Y Cf. A101605, A014612, A001358, A064911, A001221, A000005, A000010, A004018, A000292.

%K easy,nonn

%O 1,24

%A _Jonathan Vos Post_, Dec 09 2004

%E a(48) replaced with 2 and a(76) replaced with 1 by _R. J. Mathar_, Jan 27 2009

%E Name changed by _Antti Karttunen_, Jul 23 2017