# Arithmetic & Geometry

Standard

After a month of the unexpected break from mathematics, I will resume the regular weekly blog posts. It’s a kind of relaunch of this blog, and I  will begin with the discussion of an arithmetic problem with a geometric solution.  This is problem 103 from  The USSR Olympiad Problem Book:

Prove that
$\displaystyle{t_1+t_2+\ldots + t_n = \left\lfloor\frac{n}{1}\right\rfloor + \left\lfloor\frac{n}{2}\right\rfloor + \left\lfloor\frac{n}{3}\right\rfloor + \ldots + \left\lfloor\frac{n}{n}\right\rfloor}$
where $t_k$ is the number of divisors of the natural number $k$.

One can solve this problem by using the principle of mathematical induction or using the fact that the number of integers of the sequence $1,2,3,\ldots , n$ which are divisible by any chosen integer $k$ is equal to $\left\lfloor \frac{n}{k}\right\rfloor$. The second approach of counting suggests an elegant geometric solution.

Consider the equilateral hyperbola $\displaystyle{y = \frac{k}{x}}$ , (of which we shall take only the branches in the first quadrant):

We note all the points in the first quadrant which have integer coordinates as the intersection point of the dotted lines. Now, if an integer $x$ is a divisor of the integer $k$, then the point $(x,y)$ is a point on the graph of the hyperbola $xy=k$. Conversely, if the hyperbola $xy=k$ contains an integer point, then the x-coordinate is a divisor of $k$. Hence the number of integers $t_k$ is  equal to the number of the integer points lying on the hyperbola $xy=k$. The number $t_k$ is thus equal to the number of absciassas of integer points lying on the hyperbola $xy=k$. Now, we make use of the fact that the hyperbola $xy=n$ lies “farther out” in the quadrant than do $xy=1, xy=2, xy=3, \ldots, xy=n-1$. The following implication hold:

The sum $t_1+t_2\ldots + t_n$ is equal to the number of integer points lying under or on the hyperbola $xy=n$. Each such point will lie on a hyperbola $xy=k$, where $k\leq n$. The number of integer points with abscissa $k$ located under the hyperbola is equal to the integer part of the length of the segment $\overline{AB}$ [in figure above $k=3$]. That is $\left\lfloor\frac{n}{k}\right\rfloor$, since $\displaystyle{|\overline{AB}|=\frac{n}{k}}$, i.e. ordinate of point $A$ on hyperbola $xy=n$ for abscissa $k$. Thus, we obtain

$\displaystyle{t_1+t_2+\ldots + t_n = \left\lfloor\frac{n}{1}\right\rfloor + \left\lfloor\frac{n}{2}\right\rfloor + \left\lfloor\frac{n}{3}\right\rfloor + \ldots + \left\lfloor\frac{n}{n}\right\rfloor}$

Caution: Excess of anything is harmful, even mathematics.

$\displaystyle{\sum_{k=2}^{n} \frac{1}{k}}$  can never be an  integer for any value of $n$.
Firstly, observe that among the natural numbers from 2 to $n$ there is exactly one natural number which has the highest power of 2 as its divisor. Now, while summing up the reciprocals of these natural numbers we will get a fraction as the answer. In that fraction, the denominator will be an even number since it’s the least common multiple of all numbers from 2 to $n$. And the numerator will be an odd number since it’s the sum of $(n-2)$ even numbers with one odd number (corresponding to the reciprocal of the number with the highest power of 2 as the factor). Since under no circumstances an even number can completely divide an odd number, denominator can’t be a factor of the numerator. Hence the fraction can’t be reduced to an integer and the sum can never be an integer.