A071860 Number of k 1<=k<=n such that sigma(k) is odd.

1, 2, 2, 3, 3, 3, 3, 4, 5, 5, 5, 5, 5, 5, 5, 6, 6, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15

Offset: 1

Author

Benoit Cloitre, Jun 09 2002

Keywords

• easy
• nonn

Comments

a(n) = partial sums of A053866(n-1) and A093709(n-1). - Jaroslav Krizek, Oct 18 2009

a(n) = number of points in [0, n*Pi/2] where cos(x) cos(x/2) ... cos(x/n) changes sign. - Robert Israel, Apr 29 2011

References

• Richard Crandall and Carl Pomerance, Prime numbers: a computational perspective. Springer-Verlag, New York, 2001, p. 52.

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000203, A028982, A053866, A093709.

Programs

Mathematica

Accumulate[If[OddQ[DivisorSigma[1,#]],1,0]&/@Range[90]] (* Harvey P. Dale, Jul 15 2012 *)

PARI

for(n=1,100,print1(sum(i=1,n,if(sigma(i)%2,1,0)),","))

Formula

a(n) = floor( C * sqrt(n) ) +- 1, 0 with C = 1+1/sqrt(2) = 1.707...

a(n) = floor(sqrt(n)) + floor(sqrt(n/2)). (Crandall and Pomerance). - Franz Vrabec, Jun 24 2006

Extensions

Offset corrected by Amiram Eldar, May 21 2022