Slightly odd

Number Theory Level 5

$\large S_n=\sum_{i=1}^n \left \lfloor{\frac{n}{i}}\right \rfloor$

$S_n$ is defined as of above, for all positive integers $n$ . Determine the number of positive integers $1<a<1616$ for which the value of the expression

$\large S_{a-1}+S_{a}$

is an odd positive integer.

The answer is 39.

2 solutions

Abhishek Sinha
Sep 13, 2015

First note that $S_n$ denotes (equivalence follows by a simple double-counting argument) the sum of number of divisors of natural numbers up to the number $n$ , i.e. $S_n=\sum_{k=1}^{n}\sigma_0(k).$ Hence $S_{a-1}+S_{a}$ will be odd iff $\sigma_0(a)$ is odd, i.e., $a$ is a perfect square. Now there are $39$ perfect squares in the given range.

Can you please tell me how the summation of the number of divisors is equal to the summation of greatest integer function of [n / i]

Wasif Jawad Hussain - 5 years, 9 months ago

Think of it - how many numbers from $1$ to $n$ does a number $i$ divide? Clearly, the answer is $\lfloor \frac{n}{i} \rfloor$ .

Abhishek Sinha - 3 years, 9 months ago

Rajdeep Brahma
Jun 11, 2018

Slightly odd

The answer is 39.

2 solutions

0 pending reports