# Why is this sequence a good prime-generator?

For $$n \in \mathbb N$$ we can observe the $$n$$ remainders $$b_1,...,b_n$$ by writing $$n$$ as $$n=a_k \cdot k+b_k$$ for $$1 \leq k \leq n$$.

Because of the familiar division-with-remainder theorem we have $$0 \leq b_k

Then the function $$r(n)=\sum_{k=1}^{\lfloor{\frac {n-1}{2}}\rfloor}b_k$$ can be defined well.

I came to the idea of doing the research of the function $$d(n)=|r(n)-r(n-1)|$$ because I thought it would have interesting properties.

Peter computed the following after I typed to him to check of the odd values of $$d$$ how many primes are there for some ranges:

For the range of $$n$$ from $$1$$ to $$10 000$$ there are $$7330$$ odd numbers and $$2371$$ of them are primes.

For the range of $$n$$ from $$1$$ to $$100 000$$ there are $$74461$$ odd numbers and $$19065$$ of them are primes.

For the range of $$n$$ from $$1$$ to $$1000 000$$ there are $$748293$$ odd numbers and $$155800$$ of them are primes.

For the range of $$n$$ from $$1$$ to $$10000 000$$ there are $$7494602$$ odd numbers and $$1314246$$ of them are primes.

Yes, some primes, as is expected, occur more than once, but this seems to me to be a very high percentage (which tends to decrease as can be seen from the data) and because of that I typed in the title good prime-generator.

Do you think that this is a good prime-generator, and how to explain such a high percentage of primes?

Simply because $$d(n)$$ is concentrated on smaller numbers (remember that the proportion of primes among numbers smaller than $$N$$ is $$1/ \ln N$$ by Prime Number Theorem, and is $$2/\ln N$$ if you restrict to odd numbers). (made with Python and Excel)

Closed form of $$d(n)$$:

Denote $$b_k$$ by $$n \% k$$ ($$n$$ modulo $$k$$).

Then: $$(n \% k) - ((n-1) \% k) = \begin{cases} 1-k & \text{n is divisible by k} \\ 1 & \text{otherwise} \end{cases}$$

If $$n$$ is even, then $$\left\lfloor \frac {n-1} 2 \right\rfloor = \left\lfloor \frac {(n-1)-1} 2 \right\rfloor$$, so: $$d(n) = \left| \frac n 2 - 1 - \sum_{k \mid n, k \le \frac n 2 - 1} k \right| = \left| \frac n 2 - 1 + n + \frac n 2 - \sum_{k \mid n} k \right| = \left| 2n - 1 - \sum_{k \mid n} k \right|$$

Otherwise we have an extra term $$n \% \left\lfloor \frac {n-1} 2 \right\rfloor = 1$$, so: $$d(n) = \left| \frac {n-1} 2 + 1 - \sum_{k \mid n, k \le \frac{n-1}2-1} k \right| = \left| \frac {n-1} 2 + 1 + (n-1) - \sum_{k \mid n} k \right| = \left| \frac{3(n-1)}2 + 1 - \sum_{k \mid n} k \right|$$