1
$\begingroup$

Show that there exists infinitely many positive integers $n$ such that $f(n)=f(n-1)$ where $f(n)$ is the sum of all the remainders when $n$ is divided by each of $1,2,3,\cdots, n-1,n$.

Here are some of my observations. If $m$ divides $k$, then it leaves a remainder of $m-1$ when it divides $k-1$. Similarly, if $j$ divides $k-1$, it leaves a remainder of $1$ when it divides $k$. (Let's consider for $1<j,m<k-1$ to ease up the process). Now, including $1$, every other divisor of $k$ is coprime to that of $k-1$.

I cannot solve it however. I have found a relation between $k$ and $k-1$ however but that might have a calculation error, so, I am not exactly sure if that holds. Here's the relation : $$2\tau{(n)}+2\tau{(n-1)}+(n-4)=\sigma{(n)}$$ where $\tau(k)$ denotes the number of divisors which divide $k$ and $\sigma(k)$ denotes the sum of all divisors of $k$ (including $1$ and $k$)

$\endgroup$
2
  • $\begingroup$ Usually a good start is to produce several examples of the phenomenon for small or modest $n$....maybe there is a recognizable pattern. $\endgroup$
    – lulu
    Jun 12, 2018 at 9:34
  • 2
    $\begingroup$ Experiment suggests $f(2^n)=f(2^n-1)$ I've verified this for $1\le n\le20$ $\endgroup$
    – saulspatz
    Jun 12, 2018 at 9:42

2 Answers 2

1
$\begingroup$

What @saulspatz found to hold numerically for small values is actually true:

We have $f(2^m)=f(2^m-1)$ for all natural $m$. Here is why:

By definition, we have $$ f(n)=\sum_{k=1}^n \left(n-k\lfloor\frac{n}{k}\rfloor\right) $$ and thus (notice that the last term of the sum is equal to $0$) $$ f(n)-f(n-1) = \sum_{k=1}^{n-1} \left(\left[n-k\lfloor\frac{n}{k}\rfloor\right]-\left[n-1-k\lfloor\frac{n-1}{k}\rfloor\right]\right) = \sum_{k=1}^{n-1}\left(1-k\left[\lfloor\frac{n}{k}\rfloor-\lfloor\frac{n-1}{k}\rfloor\right]\right). $$ Now notice that $\lfloor\frac{n}{k}\rfloor-\lfloor\frac{n-1}{k}\rfloor=1$ if $k$ divides $n$, and $\lfloor\frac{n}{k}\rfloor-\lfloor\frac{n-1}{k}\rfloor=0$ otherwise. Therefore $$ f(n)-f(n-1) = \sum_{\substack{1\leq k<n \\ k\ |\ n}}\left(1-k\right) = n-1-(\sigma(n)-n) = 2n-1-\sigma(n). $$ Hence it sufficies to take $n$ such that $\sigma(n)=2n-1$, which can be seen to hold, for example, for $n=2^m$ with $m\in\mathbb{N}$ arbitrary.

EDIT: I'll give a bounty of $500$ reputation points and $50$ dollars to the person who proves the slightly altered version that there are infinitely many natural numbers $n$ for which $f(n)=f(n-1)-1$. Or maybe you can find an odd solution? Should be feasible, right? ;-)

$\endgroup$
2
  • $\begingroup$ Hang on, this is just $\sigma(n)=2n$, i.e. $n$ is a perfect number. It's an open problem whether there are infinite perfect numbers... $\endgroup$ Jun 12, 2018 at 13:00
  • $\begingroup$ @SharkyKesa Thats kind of the joke... ;) $\endgroup$ Jun 14, 2018 at 8:09
1
$\begingroup$

Note that if $n=2^k$, then we have the remainder when $n$ is divided by a power of $2$ is $0$, and the remainder, when divided by non-powers of two, is never $0$.

If $n=2^k-1$, then we have the remainder when $n$ is divided by a power of $2$ is $2^i-1$ (for power $2^i$), and the remainder, when divided by non-powers of two, is just $1$ less than the remainder from the $n=2^k$ case.

Now, just notice that there are strictly $2^i-1$ terms between $2^i$ and $2^{i+1}$ exclusive, so we have the sum of the remainders decrease by $2^i-1$ from the power of $2$, and increase by $2^i-1$ terms all with remainder $1$ increase as we transition from $f(2^k-1)$ to $f(2^k)$ (This can be inducted on $i$ to be completely shown if necessary), so we have no overall change in the sum of the remainders.

Therefore, $f(2^k-1)=f(2^k)$.

$\endgroup$
2
  • $\begingroup$ How did you think of $n=2^k$? Is it from one of the comments above or in some other way? $\endgroup$ Jun 12, 2018 at 10:15
  • $\begingroup$ @Mathbg Well, just notice that from $f(n-1)$ to $f(n)$, the remainders from $1$ to $n-1$ jump by $1$, and the remainder for $n$ should be $n$, so the overall remainder increase is $2n-1$. Thus, you want the sum of the factors (which should reduce the remainder back to $0$ to have $f(n-1)=f(n)$ to be $2n-1$, which works when $n$ is a power of $2$ (though it is not known whether only powers of $2$ satisfy this, it's an open problem). $\endgroup$ Jun 12, 2018 at 12:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .