2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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$?
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.