# The asymptotic of $|\{1\leq n\leq x|\gcd(n,S(n))=1\}|$, with $S(n)$ the sum of remainders, and get idea for other miscellany problem

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)$$.

Question.

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$$.

• Thanks you very much @Lspice – user142929 Jan 30 at 8:38

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.