Cross-posted on Math Overflow too
Let us define, $$r(b)=\sum_{k=1}^{\lfloor \frac{b-1}{2} \rfloor} (b \bmod{k})$$ After playing around with the $r(b)$ function for sometime I noticed that $r(b)$ appreared to be more even than odd. So to see the difference between the number of even and odd terms of $r(b)$, I defined a function, $$z(x)=\sum_{n=1}^x(-1)^{r(n)}$$ When user Peter ran a program for computing values of $z(x)$ in PARI, I observed that for $x\le 10^{10}$, $z(x)\gt 0$. This suggests that there are always more even terms of $r(n)$ than odd terms for any $x$.
This leads to my two questions:
- Is $z(x)$ always positive? If so, then how do we prove this?
- Is $|z(x)|$ bounded by some maximum value? If so, then what is this maximum value? Till now the maximum value of $|z(x)|$ found was $49$ for $x = 5424027859$. I find it odd that $|z(x)|$ goes to these large values and then returns back to small values as small as $1$.
Edit:
With the help of user Vepir I was able to plot $z(x)$ and noticed that the function has a sinusoidal-fractal-like appearance and it seems to grow without bounds, although very very slowly.
Is there any reason for this sinusoidal and fractal nature?
Claim: For every positive integer $b$ we have $r(b)\equiv r(b-1)\pmod{2}$ if and only if either
The main ingredient in proving this claim is the following lemma:
Lemma: For every positive integer $b$ we have $$r(b)-r(b-1)=c(b)-\sigma(b),$$ where $\sigma(b)$ denotes the sum of all positive divisors of $b$, and $$c(b):=\begin{cases} 2b-1&\text{ if }\ b\equiv0\pmod{2},\\ \tfrac{3b-1}{2}&\text{ if }\ b\equiv1\pmod{2}\ \text{ and }\ b\neq3,\\ 4&\text{ if }\ b=3. \end{cases}$$
This reduces the question to a question on the parity of $\sigma(b)$.
Proof. For every pair of positive integers $b$ and $k$ there exist unique nonnegative integers $q(b,k)$ and $r(b,k)$ such that $r(b,k)<k$ and $$b=q(b,k)\cdot k+r(b,k).$$ This is simply dividing $b$ by $k$ with remainder $r(b,k)$. With this, your function $r$ can be expressed as $$r(b)=\sum_{k=1}^{\lfloor\frac{b-1}{2}\rfloor}r(b,k).$$ To find a more manageable form for $r(b)$, note that $q(b,k)=\lfloor\frac bk\rfloor$, so that \begin{eqnarray*} r(b)&=&\sum_{k=1}^{\lfloor\frac{b-1}{2}\rfloor}r(b,k) =\sum_{k=1}^{\lfloor\frac{b-1}{2}\rfloor}\Big(b-q(b,k)k\Big)=\big\lfloor\tfrac{b-1}{2}\big\rfloor b -\sum_{k=1}^{\lfloor\frac{b-1}{2}\rfloor}\big\lfloor\tfrac{b}{k}\big\rfloor k. \end{eqnarray*} Then the difference of two consecutive terms can be simplified. If $b$ is even: \begin{eqnarray*} r(b)-r(b-1)&=&\left(\big\lfloor\tfrac{b-1}{2}\big\rfloor b -\sum_{k=1}^{\lfloor\frac{b-1}{2}\rfloor}\big\lfloor\tfrac{b}{k}\big\rfloor k\right) -\left(\big\lfloor\tfrac{b-2}{2}\big\rfloor(b-1) -\sum_{k=1}^{\lfloor\frac{b-2}{2}\rfloor}\big\lfloor\tfrac{b-1}{k}\big\rfloor k\right)\\ &=&\left(\frac{b-2}{2}b -\sum_{k=1}^{\frac{b-2}{2}}\big\lfloor\tfrac{b}{k}\big\rfloor k\right) -\left(\left(\frac{b-2}{2}\right)(b-1) -\sum_{k=1}^{\frac{b-2}{2}}\big\lfloor\tfrac{b-1}{k}\big\rfloor k\right)\\ &=&\frac{b-2}{2}-\sum_{k=1}^{\frac{b-2}{2}}\left(\big\lfloor\tfrac{b}{k}\big\rfloor-\big\lfloor\tfrac{b-1}{k}\big\rfloor\right)k,\\ \end{eqnarray*} and similarly if $b$ is odd: \begin{eqnarray*} r(b)-r(b-1)&=&\left(\big\lfloor\tfrac{b-1}{2}\big\rfloor b -\sum_{k=1}^{\lfloor\frac{b-1}{2}\rfloor}\big\lfloor\tfrac{b}{k}\big\rfloor k\right) -\left(\big\lfloor\tfrac{b-2}{2}\big\rfloor(b-1) -\sum_{k=1}^{\lfloor\frac{b-2}{2}\rfloor}\big\lfloor\tfrac{b-1}{k}\big\rfloor k\right)\\ &=&\left(\frac{b-1}{2}b -\sum_{k=1}^{\frac{b-1}{2}}\big\lfloor\tfrac{b}{k}\big\rfloor k\right) -\left(\frac{b-3}{2}(b-1) -\sum_{k=1}^{\frac{b-3}{2}}\big\lfloor\tfrac{b-1}{k}\big\rfloor k\right)\\ &=&\frac{3}{2}(b-1)-\big\lfloor\tfrac{2b}{b-1}\big\rfloor\frac{b-1}{2}-\sum_{k=1}^{\frac{b-3}{2}}\left(\big\lfloor\tfrac{b}{k}\big\rfloor-\big\lfloor\tfrac{b-1}{k}\big\rfloor\right)k, \end{eqnarray*} where the extra term $-\big\lfloor\tfrac{2b}{b-1}\big\rfloor\frac{b-1}{2}$ appears because the summation in $r(b)$ has one more term than the summation in $r(b-1)$, with $k=\tfrac{b-1}{2}$. For odd $b>3$ this further simplifies to $$r(b)-r(b-1)=\frac{b-1}{2}-\sum_{k=1}^{\frac{b-3}{2}}\left(\big\lfloor\tfrac{b}{k}\big\rfloor-\big\lfloor\tfrac{b-1}{k}\big\rfloor\right)k.$$ Now these inner summations have more familiar closed forms; to see this, note that $$\big\lfloor\tfrac{b}{k}\big\rfloor-\big\lfloor\tfrac{b-1}{k}\big\rfloor=\begin{cases} 0&\text{ if }\ k\nmid b\\ 1&\text{ if }\ k\mid b\\ \end{cases}.$$ So effectively these summations sum precisely the divisors of $b$, up to $\lfloor\tfrac{b-2}{2}\rfloor$. A routine check shows that the only divisors not counted are $b$, and if $b$ is even also $\tfrac{b}{2}$, and if $b=3$ also $1$. Then we can further simplify the differences for even $b$ as \begin{eqnarray*} r(b)-r(b-1)&=&\frac{b}{2}-1-\Big(\sigma(b)-b-\tfrac{b}{2}\Big)\\ &=&2b-1-\sigma(b), \end{eqnarray*} and for odd $b>3$ as \begin{eqnarray*} r(b)-r(b-1)&=&\frac{b-1}{2}-\Big(\sigma(b)-b\Big)\\ &=&\frac{3b-1}{2}-\sigma(b), \end{eqnarray*} and the latter is easily verified to also hold for $b=3$.$\quad\square$
It is a well known fact (or nice exercise) to prove that for a positive integer $m$ with prime factorization $m=\prod_{i=1}^np_i^{a_i}$, where $p_1,\ldots,p_n$ are distinct prime numbers and $a_1,\ldots,a_n$ are positive integers, we have $$\sigma(m)=\prod_{i=1}^n\sum_{j=0}^{a_i}p_i^j.$$ In particular this shows that $\sigma(m)$ is odd if and only if for every odd prime $p_i$ dividing $m$ we have $a_i\equiv0\pmod{2}$, or equivalently either $m=k^2$ or $m=2k^2$ for some integer $k$. In particular we see that if $b\equiv3\pmod{4}$ then $\sigma(b)$ is even and hence $r(b)\equiv r(b-1)\pmod{2}$.
Here are some small values for $r(b)$: $$\begin{array}{r|ccccccccc} b&0&1&2&3&4&5&6&7\\ \hline r(b)&0&0&0&0&0&1&0&2\\ &&&&&&&&\\ b&8&9&10&11&12&13&14&15\\ \hline r(b)&2&2&3&7&2&7&10&8\\ &&&&&&&&\\ b&16&17&18&19&20&21&22&23\\ \hline r(b)&8&15&11&19&16&15&22&32\\ \end{array}$$