Let $n\geq 1$ be an integer. In this post we denote the sum of remainders function as $$S(n)=\sum_{k=1}^n n \bmod k,$$ for example $S(1)=S(2)=0+0$ and $S(5)=0+1+2+1+0=4$. In the literature there are problems that were studied related to the condition $\gcd(n,f(n))=1$, for a given arithmetic function $f(n)$.


A) Is it possible to provide roughly a cheap bound for the cardinality $$\#\{1\leq n\leq x|\gcd(n,S(n))=1\}$$ as $x$ grows to $\infty$?

B) The sequence of primes $p$ that satisfy the condition $$\gcd(p,S(p))>1$$ starts as $2,11,17,2161,\ldots$. Can you provide us any idea about if this sequence has finitely many terms?

Just to emphasize, since I'm asking two questions, only is required that you provide a cheap bound for A) and a suitable reasoning/heuristic for B), to get idea for these problems.

Computational evidence and documentation for Question B. We've the following script in Pari/GP showing the first few terms

for(n=1, 10000, if(gcd(n,sum(k=1,n,n%k))>1&&isprime(n)==1,print(n)))

that you can evaluate on the website Sage Cell Server choosing as Language GP. Here the string sum(k=1,n,n%k) is our sum of remainders $S(n)$ with n%k coding $n \bmod k$ for each integer $1\leq k\leq n$.

  • $\begingroup$ Thanks you very much @Lspice $\endgroup$
    – user142929
    Jan 30, 2020 at 8:38

1 Answer 1


This observation might be already in the literature, but I have not seen it written down before.

For your second question: Since we do not suspect any "obvious" arithmetical relation between $p$ and $S(p)$, let us guess that $S(p)$ takes a random residue class $\mod p$; that is, it has a probability of $1/p$ of being a multiple of $p$. Then we would expect about $\sim \log \log x$ primes $p$ up to $x$ for which $p$ divides $S(p)$: so, infinitely many of them, but very sparse. I cannot find any beyond $4441$.

For lack of a better guess, let us also stipulate that $S(n)$ is a random integer (of its size, so $\sim cn^2$). In particular, its residue class $\mod n$ should also be random. But there are asimptotically $6/\pi^2$ such classes that are coprime to $n$--at least, if we also sum over $n \leq x$. Hence, $S(n)$ has a probability of $6/\pi^2$ of being coprime to $n$.

I am not saying that these heuristics are in any way well informed; but they agree well with numerical computation. Of course, this is not special to $S(n)$: any arithmetical function which does not have any particular relationship with $n$ itself will behave in the same way. The cases that are usually studied in the literature (say, $S(n)=\textrm{sum of $S$-units}$) are more interesting exactly because of nontrivial arithmetical relationships between $n$ and $S(n)$, which are enough to change the outcome.

  • $\begingroup$ Many thanks for your answer and attention, I'm going to study it. $\endgroup$
    – user142929
    Jan 31, 2020 at 21:03

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.