Why is this sequence a good prime-generator?

Question

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

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?

Answer 1

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