A099042 Number of badly sieved (A066680) divisors of n.

0, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 2, 2, 1, 3, 1, 2, 2, 2, 1, 4, 1, 2, 2, 2, 1, 4, 1, 2, 2, 2, 2, 4, 1, 2, 2, 3, 1, 3, 1, 2, 3, 2, 1, 4, 1, 3, 2, 2, 1, 4, 2, 3, 2, 2, 1, 5, 1, 2, 3, 2, 2, 3, 1, 2, 2, 4, 1, 5, 1, 2, 3, 2, 2, 3, 1, 4, 2, 2, 1, 4, 2, 2, 2, 3, 1, 6, 2, 2, 2, 2, 2, 4, 1, 3, 2, 3, 1, 3, 1, 3, 4

Offset: 1

Author

Reinhard Zumkeller, Sep 23 2004

Keywords

• nonn

Comments

A001221(n) <= a(n) <= A000005(n).

Examples

			a(24) = #{2,3,8,12} = 4; A099043(24) = 2+3+8+12 = 25;
a(25) = #{5} = 1; A099043(25) = 5;
a(26) = #{2,13} = 2; A099043(26) = 2+13 = 15.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..65537

Crossrefs

Cf. A066680, A099104.

Programs

Mathematica

b[n_] := b[n] = If[n == 1, 0, Product[If[n > d^2, 1, 1 - b[d]], {d, Select[Range[n - 1], Mod[n, #] == 0&]}]]; (* b is A099104 *)
a[n_] := Sum[b[d], {d, Divisors[n]}];
Array[a, 105] (* Jean-François Alcover, Dec 06 2021 *)

PARI

A099104(n) = if(1==n,0,my(m=1); fordiv(n,d,if((d=n),m *= (1-A099104(d)))); (m));
A099042(n) = sumdiv(n,d,A099104(d)); \\ Antti Karttunen, Jul 02 2018

Formula

a(n) = Sum_{d|n} A099104(d). - Antti Karttunen, Jul 02 2018