# 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.