Conjecture: For almost all $n$, the sum of $n \bmod k$ for $k<n$ is unique.

Question

It looks to me like $$f(n):= \sum_{k=1}^{n}{(n\bmod k)}$$ is almost unique to $n$, with the only systematic exceptions being $(2^m-1, 2^m)$ pairs, which share a value for any $m \in \mathbb N$. In other words, the set $\{f(n): n\in\mathbb N\land n\neq 2^m \ \forall m\in\mathbb N\}$ shouldn't have many duplicate values.

As discussed in the answers, a handful of counterexamples have been found, but they seem more sparse than one would expect, and nobody has yet suggested why that might be, or what's special about the counterexamples found, apart from a moderate preponderance of small factors in the mean of the pair.

Although there's not much data to go on, it also looks like counterexamples may come in the form $(n,n+2i)$, or possibly even $(n,n+2^i)$, and I would be interested if anyone can find a case outside of those. The latter form would also include the $(2^m-1,2^m)$ exceptions, which seems elegant.

---

Also, if someone could set me straight on this: My understanding is that the term 'almost all' in this context means approaching $0$ density in the limit; so if one could show that the exceptions aren't necessarily finite, but they are less common than powers of two, would that be sufficient?

Answer 1

The approach above can be simplified to following general case.

Let $f(n):= \sum_{i=1}^{n}{(n\bmod i)}$ as described.

Given any pair of natural numbers $(n,k)$, we have $f(n)=f(n+k)$ if and only if

$$\sum_{i=1}^{k}{\sigma(n+i)}=2kn+k^2.$$

This seems to fit all known examples, including the $(2^m-1,2^m)$ pairs.

Answer 2

Nope, not unique.

I hadn't checked far enough. The first counterexample is at $$f(38183)=f(38185)=258840858.$$

It could plausibly still have only finitely many counterexamples, though, making the 'almost all' claim true. There are three more found so far through $n< 6 \times 10^8$ with the form $(n,n+2)$: $458009$, $776111$, and $65675407$. As stated below, there was also one example of form $(n,n+4)$: $113393278$.

Note $f(x)$ grows as the square of $x$, so this may be what one would probabilistically expect. It's tough to say, but my guess is counterexamples may be very sparse, yet probably still infinite.

Answer 3

This is just a comment on the counterexample in the OP's answer, noting a relatively quick way to verify that $f(38183)=f(38185)$ without computing each to equal $258840858$.

A formula at the OEIS entry for the OP's sequence says

$$f(n)=n^2-\sum_{k=1}^n\sigma(k)$$

where $\sigma(k)$ is the sum of the divisors of $k$. To show that $f(m)=f(n)$ with $m\lt n$, then, it suffices to show that

$$\sum_{k=m+1}^n\sigma(k)=n^2-m^2=(n-m)(n+m)$$

For $m=38183$ and $n=38185$, we have $(n-m)(n+m)=2\cdot76368=152736$ while

$$\begin{align} \sigma(38184)+\sigma(38185) &=\sigma(2^3\cdot3\cdot37\cdot43)+\sigma(5\cdot7\cdot1091)\\ &=15\cdot4\cdot38\cdot44+6\cdot8\cdot1092\\ &=100320+52416\\ &=152736 \end{align}$$

Remark: The trickiest part of the verification is the factorization into primes (in particular, recognizing $1091$ as a prime number).

Answer 4

I feel this is worth an answer, using Barry Cipra's technique, to report the first such equality over a gap of more than $2$:

$$f(113393278)=f(113393282)$$

with:
$\sigma(113393278)=171694080$ with $113393278 = 2\cdot 179\cdot 383\cdot 827$ (not needed)
$\sigma(113393279)=117765120$ with $113393279 = 43\cdot 67\cdot 39359$
$\sigma(113393280)=493516800$ with $113393280 = 2^7\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 59$
$\sigma(113393281)=123621120$ with $113393281 = 17\cdot 47\cdot 139\cdot 1021$ $\sigma(113393282)=172243200$ with $113393282 = 2\cdot 79\cdot 717679$