A363341 Number of positive integers k <= n such that round(n/k) is odd.

1, 1, 2, 2, 4, 3, 4, 4, 6, 7, 6, 5, 9, 8, 9, 9, 10, 10, 11, 12, 13, 12, 13, 12, 15, 16, 17, 16, 17, 16, 17, 17, 20, 21, 20, 20, 23, 22, 21, 22, 24, 23, 26, 25, 28, 27, 26, 25, 27, 29, 30, 31, 32, 31, 32, 31, 32, 33, 34, 33, 35, 34, 37, 37, 40, 39, 38, 39, 40

Offset: 1

Author

Caleb M. Shor, May 28 2023

Keywords

• nonn

Comments

Here round(x) = floor(x + 1/2).

a(n) is related to the number of lattice points in a circle. Let C(x) equal the number of square lattice points in a circle of radius sqrt(x) centered at the origin. Then a(n) = (C(2n) - 4n - 1)/4. (Prop 3.5 in Dent & Shor paper)

Examples

			For n=5: round(5/1), round(5/2), round(5/3), round(5/4), round(5/5) = 5, 3, 2, 1, 1 among which 4 are odd so a(5)=4.
		

Links

• Robert Israel, Table of n, a(n) for n = 1..10000
• Nicholas Dent and Caleb M. Shor, On residues of rounded shifted fractions with a common numerator, arXiv:2206.15452 [math.NT], 2022.

Crossrefs

Cf. A059851 (number of k=1..n such that floor(n/k) is odd).

Cf. A330926 (number of k=1..n such that ceiling(n/k) is odd).

Cf. A057655 (number of lattice points in circle).

Cf. A001826 (d_1), A001842 (d_3), A002654 (d_1-d_3).

Cf. A077024 (n + floor(2n/3) + floor(2n/5) + floor(2n/7) + ...).

Programs

Maple

f:= proc(n) local k;
   nops(select(k -> floor(n/k + 1/2)::odd, [$1..n]))
end proc:
map(f, [$1..120]); # Robert Israel, Aug 03 2025

PARI

a(n) = sum(k=1, n, round(n/k)%2) \\ Andrew Howroyd, May 28 2023

Formula

a(n) = n - floor(2n/3) + floor(2n/5) - floor(2n/7) + ...

a(n) = -n + Sum_{k=1..2n} d_1(k) - d_3(k), where d_i(k) is the number of divisors of k that are congruent to i modulo 4.