# Euler phi Function and Floor Function

Let $\phi(x)$ be the Euler phi function and $\lfloor x\rfloor$ the floor function

Count the sum of $$\phi(1)\cdot\lfloor \frac{2015}{1} \rfloor + \phi(2)\cdot\lfloor \frac{2015}{2} \rfloor + \phi(3)\cdot\lfloor \frac{2015}{3} \rfloor + \phi(4)\cdot\lfloor \frac{2015}{4} \rfloor + \cdots + \phi(2014)\cdot\lfloor \frac{2015}{2014} \rfloor + \phi(2015)\cdot\lfloor \frac{2015}{2015} \rfloor$$

I have do for $1,2, \ldots, 10$ but I can see no pattern there.

Let

$$f(n)=\sum_{k=1}^n\varphi(k)\left\lfloor\frac{n}k\right\rfloor\;,$$

so that you’re interested in $f(2015)$. Calculate the first few values:

\begin{align*} f(1)&=1\\ f(2)&=2+1=3\\ f(3)&=3+1+2=6\\ f(4)&=4+2+2+2=10\\ f(5)&=5+2+2+2+4=15 \end{align*}

There is a very clear pattern here: at least for $n=1,2,3,4,5$ we have the very familiar triangular numbers, suggesting that

$$f(n)=\sum_{k=1}^nk=\frac{n(n+1)}2=\binom{n+1}2\;.\tag{1}$$

Another way to put it is that it appears that we might have $f(1)=1$ and $f(n)=f(n-1)+n$ for $n>1$. We know that $f(1)=1$, so we’d prove $(1)$ if we could show that the recurrence $f(n)=f(n-1)+n$ really does hold for $n>1$. That would mean proving that

$$\sum_{k=1}^n\varphi(k)\left\lfloor\frac{n}k\right\rfloor=n+\sum_{k=1}^{n-1}\varphi(k)\left\lfloor\frac{n-1}k\right\rfloor\tag{2}$$

or, equivalently, that

$$\sum_{k=1}^{n-1}\varphi(k)\left(\left\lfloor\frac{n}k\right\rfloor-\left\lfloor\frac{n-1}k\right\rfloor\right)=n-\varphi(n)\;.\tag{3}$$

• Justify the assertion that $(3)$ is equivalent to $(2)$.
• $n-\varphi(n)$ is the number of integers in $\{1,2,\ldots,n\}$ with what property?

Note that $$\left\lfloor\frac{n}k\right\rfloor-\left\lfloor\frac{n-1}k\right\rfloor\tag{4}$$

is always $0$ or $1$.

• For which values of $k$ is the difference in $(4)$ equal to $1$?