A059851 a(n) = n - floor(n/2) + floor(n/3) - floor(n/4) + ... (this is a finite sum).

0, 1, 1, 3, 2, 4, 4, 6, 4, 7, 7, 9, 7, 9, 9, 13, 10, 12, 12, 14, 12, 16, 16, 18, 14, 17, 17, 21, 19, 21, 21, 23, 19, 23, 23, 27, 24, 26, 26, 30, 26, 28, 28, 30, 28, 34, 34, 36, 30, 33, 33, 37, 35, 37, 37, 41, 37, 41, 41, 43, 39, 41, 41, 47, 42, 46, 46, 48, 46, 50, 50, 52, 46, 48, 48

Offset: 0

Author

Avi Peretz (njk(AT)netvision.net.il), Feb 27 2001

Keywords

• nonn
• easy

Comments

As n goes to infinity we have the asymptotic formula: a(n) ~ n * log(2).

More precisely, a(n) = n * log(2) + O(n^(131/416) * (log n)^(26947/8320)). - V Sai Prabhav, Jun 02 2025

Examples

			a(5) = 4 because floor(5) - floor(5/2) + floor(5/3) - floor(5/4) + floor(5/5) - floor(5/6) + ... = 5 - 2 + 1 - 1 + 1 - 0 + 0 - 0 + ... = 4.
		

Links

• T. D. Noe, Table of n, a(n) for n = 0..10000
• V Sai Prabhav, Asymptotic Expansion of a(n)

Crossrefs

Cf. A000005, A075997, A271860, A263086.

Partial sums of A048272.

Sums of the form Sum_{k=1..n} q^(k-1)*floor(n/k): A344820 (q=-n), A344819 (q=-4), A344818 (q=-3), A344817 (q=-2), this sequence (q=-1), A006218 (q=1), A268235 (q=2), A344814 (q=3), A344815 (q=4), A344816 (q=5), A332533 (q=n).

Programs

Magma

A059851:= func< n | (&+[Floor(n/j)*(-1)^(j-1): j in [1..n]]) >;
[A059851(n): n in [1..80]]; // G. C. Greubel, Jun 27 2024

Maple

for n from 0 to 200 do printf(`%d,`, sum((-1)^(i+1)*floor(n/i), i=1..n)) od:

Mathematica

f[list_, i_] := list[[i]]; nn = 200; a = Table[1, {n, 1, nn}]; b =
Table[If[OddQ[n], 1, -1], {n, 1, nn}];Table[DirichletConvolve[f[a, n], f[b, n], n, m], {m, 1, nn}] // Accumulate (* Geoffrey Critzer, Mar 29 2015 *)
Table[Sum[Floor[n/k] - 2*Floor[n/(2*k)], {k, 1, n}], {n, 0, 100}] (* Vaclav Kotesovec, Dec 23 2020 *)

PARI

{ for (n=0, 10000, s=1; d=2; a=n; while ((f=floor(n/d)) > 0, a-=s*f; s=-s; d++); write("b059851.txt", n, " ", a); ) } \\ Harry J. Smith, Jun 29 2009

Python

from math import isqrt
def A059851(n): return ((t:=isqrt(m:=n>>1))**2<<1)-(s:=isqrt(n))**2+(sum(n//k for k in range(1,s+1))-(sum(m//k for k in range(1,t+1))<<1)<<1) # Chai Wah Wu, Oct 23 2023

SageMath

def A059851(n): return sum((n//j)*(-1)^(j-1) for j in range(1,n+1))
[A059851(n) for n in range(81)] # G. C. Greubel, Jun 27 2024

Formula

From Vladeta Jovovic, Oct 15 2002: (Start)

a(n) = A006218(n) - 2*A006218(floor(n/2)).

G.f.: 1/(1-x)*Sum_{n>=1} x^n/(1+x^n). (End)

a(n) = Sum_{n/2 < k < =n} d(k) - Sum_{1 < =k <= n/2} d(k), where d(k) = A000005(k). Also, a(n) = number of terms among {floor(n/k)}, 1<=k<=n, that are odd. - Leroy Quet, Jan 19 2006

From Ridouane Oudra, Aug 15 2019: (Start)

a(n) = Sum_{k=1..n} (floor(n/k) mod 2).

a(n) = (1/2)*(n + A271860(n)).

a(n) = Sum_{k=1..n} round(n/(2*k)) - floor(n/(2*k)), where round(1/2) = 1. (End)

a(n) = 2*A263086(n) - 3*A006218(n). - Ridouane Oudra, Aug 17 2024

Extensions

More terms from James Sellers and Larry Reeves (larryr(AT)acm.org), Feb 27 2001