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,6

Comments

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

Links

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

Formula

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

Example

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.

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 *)

Prog

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

Crossrefs

Cf. A066680, A099104.

Sequence in context: A325759 A292286 A341596 * A140774 A345345 A056924

Adjacent sequences: A099039 A099040 A099041 * A099043 A099044 A099045

Keyword

nonn

Author

Reinhard Zumkeller, Sep 23 2004

Status

approved