10
$\begingroup$

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:

  1. Is $z(x)$ always positive? If so, then how do we prove this?
  2. 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.

enter image description here

enter image description here

Is there any reason for this sinusoidal and fractal nature?

$\endgroup$
  • 1
    $\begingroup$ The efficient calculation is based on the formula for $d(n):=r(n)-r(n-1)$ , which is $$d(n)=2n-1-\sigma(n)$$ for even $n$ and $$d(n)=\frac{3n-1}{2}-\sigma(n)$$ for odd $n$ and the fact that $\sigma(n)$ is odd if and only if $n=k^2$ or $n=2k^2$ for some positive integer $k$. $\endgroup$ – Peter Mar 19 at 21:50
  • 1
    $\begingroup$ $r(n)$ and $r(n-1)$ have the same parity if and only if $n$ is of the form $k^2,2k^2$ or $4k+3$ for some positive integer $k$ (in the case $4k+3$ , $k=0$ is also possible). $\endgroup$ – Peter Mar 19 at 21:54
  • 2
    $\begingroup$ If my calculation is correct, we have $z(31988856^2)=80$ and the function does not really feel like it would be bounded from above. $\endgroup$ – Peter Košinár Mar 29 at 2:02
  • 1
    $\begingroup$ @PeterKošinár thanks for the calculation. Was $z(n)$ ever negative in that range? $\endgroup$ – Mathphile Mar 29 at 4:48
  • 2
    $\begingroup$ @Mathphile No, I have not found any case where $z(n)$ would be negative or zero. It has reached $1$ on multiple occasions, though. (again, assuming my computation was correct). $\endgroup$ – Peter Košinár Mar 29 at 16:43
5
+50
$\begingroup$

I can't prove/disprove your conjectures, but I proved a claim which might be useful to prove/disprove your conjectures.

This answer proves the following claim :

Claim :

$$\small\begin{align}z(8m)&=(-1)^{c(8m)}+S(m) \\\\z(8m+1)&=(-1)^{c(8m)}-(-1)^{c(8m+1)}+S(m) \\\\z(8m+2)&=(-1)^{c(8m)}-(-1)^{c(8m+1)}+(-1)^{c(8m+2)}+S(m) \\\\z(8m+3)&=(-1)^{c(8m)}-(-1)^{c(8m+1)}+2(-1)^{c(8m+2)}+S(m) \\\\z(8m+4)&=(-1)^{c(8m)}-(-1)^{c(8m+1)}+2(-1)^{c(8m+2)}-(-1)^{c(8m+4)}+S(m) \\\\z(8m+5)&=(-1)^{c(8m)}-(-1)^{c(8m+1)}+2(-1)^{c(8m+2)}-(-1)^{c(8m+4)}+(-1)^{c(8m+5)}+S(m) \\\\z(8m+6)&=(-1)^{c(8m)}-(-1)^{c(8m+1)}+2(-1)^{c(8m+2)}-(-1)^{c(8m+4)}+S(m) \\\\z(8m+7)&=(-1)^{c(8m)}-(-1)^{c(8m+1)}+2(-1)^{c(8m+2)}-(-1)^{c(8m+4)}-(-1)^{c(8m+7)}+S(m)\end{align}$$ where $$c(n)=\#\{x:\text{ $1\le x\le n$, and $x$ is either a square or twice a square}\}$$ and $$S(m):=\sum_{k=0}^{m-1}\bigg((-1)^{c(8k)}-(-1)^{c(8k+1)}+2(-1)^{c(8k+2)}-(-1)^{c(8k+4)}-(-1)^{c(8k+7)}\bigg)$$

According to oeis.org/A071860, one has $$c(n)=\lfloor\sqrt{n}\rfloor+\left\lfloor\sqrt{\frac n2}\right\rfloor$$ which might make the problem easier to deal with.

Also, it follows from the above claim that $$z(8m+4)=z(8m+6)$$ for every non-negative integer $m$.


The claim follows from the following lemmas :

Lemma 1 : $$r(n)=n^2-\frac{1}{2}\bigg(\left\lfloor\frac{n-3}{2}\right\rfloor+2\bigg)\bigg(\left\lfloor\frac{n-3}{2}\right\rfloor +1\bigg)-\sum_{k=1}^{n}\sigma(k)$$

Lemma 2 : $$r(n)\stackrel{\text{mod $2$}}\equiv\begin{cases}\displaystyle\sum_{k=1}^{n}\sigma(k)&\text{if $n\equiv 0,2,3,5\pmod 8$}\\\\1+\displaystyle\sum_{k=1}^{n}\sigma(k)&\text{if $n\equiv 1,4,6,7\pmod 8$}\end{cases}$$

Lemma 3 : $$\text{$\sigma(n)$ is odd $\iff$ $n$ is either a square or twice a square}$$

Lemma 4 : $$\sum_{k=1}^{n}\sigma(k)\equiv c(n)\pmod 2$$where $$c(n)=\#\{x:\text{ $1\le x\le n$, and $x$ is either a square or twice a square}\}$$

Lemma 5 : If $n\equiv 3\pmod 4$, then $c(n)=c(n-1)$.

Lemma 6 : $$z(x)=\sum_{k=0}^{\lfloor x/8\rfloor}(-1)^{c(8k)}-\sum_{k=0}^{\lfloor (x-1)/8\rfloor}(-1)^{c(8k+1)}+\sum_{k=0}^{\lfloor (x-2)/8\rfloor}(-1)^{c(8k+2)}+\sum_{k=0}^{\lfloor (x-3)/8\rfloor}(-1)^{c(8k+2)}-\sum_{k=0}^{\lfloor (x-4)/8\rfloor}(-1)^{c(8k+4)}+\sum_{k=0}^{\lfloor (x-5)/8\rfloor}(-1)^{c(8k+5)}-\sum_{k=0}^{\lfloor (x-6)/8\rfloor}(-1)^{c(8k+5)}-\sum_{k=0}^{\lfloor (x-7)/8\rfloor}(-1)^{c(8k+7)}$$

Lemma 7 :

$$\small\begin{align}z(8m)&=(-1)^{c(8m)}+S(m) \\\\z(8m+1)&=(-1)^{c(8m)}-(-1)^{c(8m+1)}+S(m) \\\\z(8m+2)&=(-1)^{c(8m)}-(-1)^{c(8m+1)}+(-1)^{c(8m+2)}+S(m) \\\\z(8m+3)&=(-1)^{c(8m)}-(-1)^{c(8m+1)}+2(-1)^{c(8m+2)}+S(m) \\\\z(8m+4)&=(-1)^{c(8m)}-(-1)^{c(8m+1)}+2(-1)^{c(8m+2)}-(-1)^{c(8m+4)}+S(m) \\\\z(8m+5)&=(-1)^{c(8m)}-(-1)^{c(8m+1)}+2(-1)^{c(8m+2)}-(-1)^{c(8m+4)}+(-1)^{c(8m+5)}+S(m) \\\\z(8m+6)&=(-1)^{c(8m)}-(-1)^{c(8m+1)}+2(-1)^{c(8m+2)}-(-1)^{c(8m+4)}+S(m) \\\\z(8m+7)&=(-1)^{c(8m)}-(-1)^{c(8m+1)}+2(-1)^{c(8m+2)}-(-1)^{c(8m+4)}-(-1)^{c(8m+7)}+S(m)\end{align}$$

where $$S(m):=\sum_{k=0}^{m-1}\bigg((-1)^{c(8k)}-(-1)^{c(8k+1)}+2(-1)^{c(8k+2)}-(-1)^{c(8k+4)}-(-1)^{c(8k+7)}\bigg)$$


Lemma 1 : $$r(n)=n^2-\frac{1}{2}\bigg(\left\lfloor\frac{n-3}{2}\right\rfloor+2\bigg)\bigg(\left\lfloor\frac{n-3}{2}\right\rfloor +1\bigg)-\sum_{k=1}^{n}\sigma(k)$$

Proof : For $n=1$, it is true. In the following, let us use $$r(n+1)-r(n)=\begin{cases}2n+1-\sigma(n+1)&\text{if $n$ is odd}\\\\\frac{3n+2}{2}-\sigma(n+1)&\text{if $n$ is even}\end{cases}$$

Suppose that it is true for $n=2m+1$. Then, we get $$\begin{align}&r(n+1) \\\\&=r(n)+2n+1-\sigma(n+1) \\\\&=n^2-\frac{1}{2}\bigg(\left\lfloor\frac{n-3}{2}\right\rfloor+2\bigg)\bigg(\left\lfloor\frac{n-3}{2}\right\rfloor +1\bigg) -\sum_{k=1}^{n}\sigma(n)+2n+1-\sigma(n+1) \\\\&=(2m+1)^2-\frac{m(m+1)}{2}+2(2m+1)+1-\sum_{k=1}^{n+1}\sigma(k) \\\\&=(2m+2)^2-\frac{m(m+1)}{2}-\sum_{k=1}^{n+1}\sigma(k) \\\\&=(2m+2)^2-\frac{1}{2}\bigg(\left\lfloor\frac{2m-1}{2}\right\rfloor+2\bigg)\bigg(\left\lfloor\frac{2m-1}{2}\right\rfloor +1\bigg)-\sum_{k=1}^{n+1}\sigma(k) \\\\&=(n+1)^2-\frac{1}{2}\bigg(\left\lfloor\frac{n+1-3}{2}\right\rfloor+2\bigg)\bigg(\left\lfloor\frac{n+1-3}{2}\right\rfloor +1\bigg)-\sum_{k=1}^{n+1}\sigma(k)\end{align}$$

Suppose that it is true for $n=2m$. Then, we get $$\begin{align}&r(n+1) \\\\&=r(n)+\frac{3n+2}{2}-\sigma(n+1) \\\\&=n^2-\frac{1}{2}\bigg(\left\lfloor\frac{n-3}{2}\right\rfloor+2\bigg)\bigg(\left\lfloor\frac{n-3}{2}\right\rfloor +1\bigg) -\sum_{k=1}^{n}\sigma(k)+\frac{3n+2}{2}-\sigma(n+1) \\\\&=(2m)^2-\frac{m(m-1)}{2}+3m+1-\sum_{k=1}^{n+1}\sigma(k) \\\\&=(2m+1)^2-\frac{(m+1)m}{2}-\sum_{k=1}^{n+1}\sigma(k) \\\\&=(2m+1)^2-\frac{1}{2}\bigg(\left\lfloor\frac{2m+1-3}{2}\right\rfloor+2\bigg)\bigg(\left\lfloor\frac{2m+1-3}{2}\right\rfloor +1\bigg)-\sum_{k=1}^{n+1}\sigma(k) \\\\&=(n+1)^2-\frac{1}{2}\bigg(\left\lfloor\frac{n+1-3}{2}\right\rfloor+2\bigg)\bigg(\left\lfloor\frac{n+1-3}{2}\right\rfloor +1\bigg)-\sum_{k=1}^{n+1}\sigma(k)\end{align}$$

So, it is also true for $n+1$.$\quad\square$


Lemma 2 : $$r(n)\stackrel{\text{mod $2$}}\equiv\begin{cases}\displaystyle\sum_{k=1}^{n}\sigma(k)&\text{if $n\equiv 0,2,3,5\pmod 8$}\\\\1+\displaystyle\sum_{k=1}^{n}\sigma(k)&\text{if $n\equiv 1,4,6,7\pmod 8$}\end{cases}$$

Proof : It follows from Lemma 1 that$$r(8m)=64m^2-2m(4m-1)-\sum_{k=1}^{8m}\sigma(k)\equiv \sum_{k=1}^{8m}\sigma(k)\pmod 2$$

$$r(8m+1)=(8m+1)^2-2m(4m+1)-\sum_{k=1}^{8m+1}\sigma(k)\equiv 1+\sum_{k=1}^{8m+1}\sigma(k)\pmod 2$$

$$r(8m+2)=(8m+2)^2-2m(4m+1)-\sum_{k=1}^{8m+2}\sigma(k)\equiv \sum_{k=1}^{8m+2}\sigma(k)\pmod 2$$

$$r(8m+3)=(8m+3)^2-(2m+1)(4m+1)-\sum_{k=1}^{8m+3}\sigma(k)\equiv \sum_{k=1}^{8m+3}\sigma(k)\pmod 2$$

$$r(8m+4)=(8m+4)^2-(2m+1)(4m+1)-\sum_{k=1}^{8m+4}\sigma(k)\equiv 1+\sum_{k=1}^{8m+4}\sigma(k)\pmod 2$$

$$r(8m+5)=(8m+5)^2-(2m+1)(4m+3)-\sum_{k=1}^{8m+5}\sigma(k)\equiv \sum_{k=1}^{8m+5}\sigma(k)\pmod 2$$

$$r(8m+6)=(8m+6)^2-(2m+1)(4m+3)-\sum_{k=1}^{8m+6}\sigma(k)\equiv 1+\sum_{k=1}^{8m+6}\sigma(k)\pmod 2$$

$$r(8m+7)=(8m+7)^2-(2m+2)(4m+3)-\sum_{k=1}^{8m+7}\sigma(k)\equiv 1+\sum_{k=1}^{8m+7}\sigma(k)\pmod2$$ So, the claim follows.$\quad\square$


Lemma 3 : $$\text{$\sigma(n)$ is odd $\iff$ $n$ is either a square or twice a square}$$

Proof : See here or here.


Lemma 4 : $$\sum_{k=1}^{n}\sigma(k)\equiv c(n)\pmod 2$$where $$c(n)=\#\{x:\text{ $1\le x\le n$, and $x$ is either a square or twice a square}\}$$

Proof : It follows from Lemma 3 that $$\sum_{k=1}^{n}\sigma(k)=\underbrace{\sum_{k\in A}\sigma(k)}_{\text{sum of odd numbers}}+\underbrace{\sum_{k\not\in A}\sigma(k)}_{\text{sum of even numbers $=$ even}}\equiv \sum_{k\in A}\sigma(k)=c(n)\pmod 2$$ where $A=\{n\ :\ \text{$n$ is either a square or twice a square}\}$.


Lemma 5 : If $n\equiv 3\pmod 4$, then $c(n)=c(n-1)$.

Proof : Since we have $$\text{(a square)}\equiv 0,1\pmod 4\qquad\text{and}\qquad \text{(twice a square)}\equiv 0,2\pmod 4$$ we see that if $n\equiv 3\pmod 4$, then $n$ is neither a square nor twice a square.


Lemma 6 : $$z(x)=\sum_{k=0}^{\lfloor x/8\rfloor}(-1)^{c(8k)}-\sum_{k=0}^{\lfloor (x-1)/8\rfloor}(-1)^{c(8k+1)}+\sum_{k=0}^{\lfloor (x-2)/8\rfloor}(-1)^{c(8k+2)}+\sum_{k=0}^{\lfloor (x-3)/8\rfloor}(-1)^{c(8k+2)}-\sum_{k=0}^{\lfloor (x-4)/8\rfloor}(-1)^{c(8k+4)}+\sum_{k=0}^{\lfloor (x-5)/8\rfloor}(-1)^{c(8k+5)}-\sum_{k=0}^{\lfloor (x-6)/8\rfloor}(-1)^{c(8k+5)}-\sum_{k=0}^{\lfloor (x-7)/8\rfloor}(-1)^{c(8k+7)}$$

Proof : It follows from Lemma $1,2,3,4,5$ that $$z(x)=\sum_{k=1}^{x}(-1)^{r(k)}=\sum_{k=0}^{\lfloor x/8\rfloor}(-1)^{r(8k)}+\sum_{k=0}^{\lfloor (x-1)/8\rfloor}(-1)^{r(8k+1)}+\sum_{k=0}^{\lfloor (x-2)/8\rfloor}(-1)^{r(8k+2)}+\sum_{k=0}^{\lfloor (x-3)/8\rfloor}(-1)^{r(8k+3)}+\sum_{k=0}^{\lfloor (x-4)/8\rfloor}(-1)^{r(8k+4)}+\sum_{k=0}^{\lfloor (x-5)/8\rfloor}(-1)^{r(8k+5)}+\sum_{k=0}^{\lfloor (x-6)/8\rfloor}(-1)^{r(8k+6)}+\sum_{k=0}^{\lfloor (x-7)/8\rfloor}(-1)^{r(8k+7)}$$

$$=\sum_{k=0}^{\lfloor x/8\rfloor}(-1)^{c(8k)}-\sum_{k=0}^{\lfloor (x-1)/8\rfloor}(-1)^{c(8k+1)}+\sum_{k=0}^{\lfloor (x-2)/8\rfloor}(-1)^{c(8k+2)}+\sum_{k=0}^{\lfloor (x-3)/8\rfloor}(-1)^{c(8k+3)}-\sum_{k=0}^{\lfloor (x-4)/8\rfloor}(-1)^{c(8k+4)}+\sum_{k=0}^{\lfloor (x-5)/8\rfloor}(-1)^{c(8k+5)}-\sum_{k=0}^{\lfloor (x-6)/8\rfloor}(-1)^{c(8k+6)}-\sum_{k=0}^{\lfloor (x-7)/8\rfloor}(-1)^{c(8k+7)}$$

$$=\sum_{k=0}^{\lfloor x/8\rfloor}(-1)^{c(8k)}-\sum_{k=0}^{\lfloor (x-1)/8\rfloor}(-1)^{c(8k+1)}+\sum_{k=0}^{\lfloor (x-2)/8\rfloor}(-1)^{c(8k+2)}+\sum_{k=0}^{\lfloor (x-3)/8\rfloor}(-1)^{c(8k+2)}-\sum_{k=0}^{\lfloor (x-4)/8\rfloor}(-1)^{c(8k+4)}+\sum_{k=0}^{\lfloor (x-5)/8\rfloor}(-1)^{c(8k+5)}-\sum_{k=0}^{\lfloor (x-6)/8\rfloor}(-1)^{c(8k+5)}-\sum_{k=0}^{\lfloor (x-7)/8\rfloor}(-1)^{c(8k+7)}$$


Lemma 7 :

$$\small\begin{align}z(8m)&=(-1)^{c(8m)}+S(m) \\\\z(8m+1)&=(-1)^{c(8m)}-(-1)^{c(8m+1)}+S(m) \\\\z(8m+2)&=(-1)^{c(8m)}-(-1)^{c(8m+1)}+(-1)^{c(8m+2)}+S(m) \\\\z(8m+3)&=(-1)^{c(8m)}-(-1)^{c(8m+1)}+2(-1)^{c(8m+2)}+S(m) \\\\z(8m+4)&=(-1)^{c(8m)}-(-1)^{c(8m+1)}+2(-1)^{c(8m+2)}-(-1)^{c(8m+4)}+S(m) \\\\z(8m+5)&=(-1)^{c(8m)}-(-1)^{c(8m+1)}+2(-1)^{c(8m+2)}-(-1)^{c(8m+4)}+(-1)^{c(8m+5)}+S(m) \\\\z(8m+6)&=(-1)^{c(8m)}-(-1)^{c(8m+1)}+2(-1)^{c(8m+2)}-(-1)^{c(8m+4)}+S(m) \\\\z(8m+7)&=(-1)^{c(8m)}-(-1)^{c(8m+1)}+2(-1)^{c(8m+2)}-(-1)^{c(8m+4)}-(-1)^{c(8m+7)}+S(m)\end{align}$$

where $$S(m):=\sum_{k=0}^{m-1}\bigg((-1)^{c(8k)}-(-1)^{c(8k+1)}+2(-1)^{c(8k+2)}-(-1)^{c(8k+4)}-(-1)^{c(8k+7)}\bigg)$$

Proof : This immediately follows from Lemma 6.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

Claim: For every positive integer $b$ we have $r(b)\equiv r(b-1)\pmod{2}$ if and only if either

  1. $b\equiv3\pmod{4}$, or
  2. $b=k^2$ for some integer $k$, or
  3. $b=2k^2$ for some integer $k$.

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ It seems that $r(b)\equiv r(b+1)\pmod{2}\iff\sigma(b+1)\equiv1\pmod{2}$ is false. Take $b=6$. $\endgroup$ – mathlove Mar 23 at 15:24
  • $\begingroup$ @mathlove I had spotted the same inconsistency. I have removed the error in my argument. I will try to complete this answer soon (likely tomorrow). $\endgroup$ – Servaes Mar 23 at 15:53

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.