Let us define,
$$r(b)=\sum_{k=1}^{\lfloor \frac{b-1}{2} \rfloor} (b \bmod{k})$$
After reading the posts Surprising fact about a certain number-theoretic function and Do primes have special sums… I decided to play around with the $r(b)$ function and after performing some computations using PARI/GP, I found some very interesting patterns.
- $r(a^n)-r(a^n-1)=0$ when $a\in {2, 3}$ for any $n\in \Bbb{N}$. (Proved by user Haran in the first post)
- For fixed $a$ and any $n\in \Bbb{N}$, $r(a^n)-r(a^n-1)$ is either always positive or always negative when $a$ is not of the form $2p$ or $3q$ where $p,q$ are prime and $p\gt 3, q\gt 7$.
- For fixed $a$, $r(a^n)-r(a^n-1)$ is initially postive and then becomes negative as $n\in \Bbb{N}$ increases when $a$ is the form of $2p$ or $3q$ where $p,q$ are prime and $p\gt 3, q\gt 7$.
- If $a \notin \{2p, 3p\}$ is prime or semiprime then $r(a^n)-r(a^n-1)$ is positive for all $n\in \Bbb{N}$. (edit)
What is the reason for these weird characteristics or $r(a^n)-r(a^n-1)$? I would really appreciate if someone could prove/disprove any of the last 3 observations.
Here is some of the initial data from where I made my observations. The first column gives the $a$ values, the second gives the $n$ values, and the third gives the corresponding values of $r(a^n)-r(a^n-1)$.
1 1 0
1 2 0
1 3 0
1 4 0
1 5 0
2 1 0
2 2 0
2 3 0
2 4 0
2 5 0
3 1 0
3 2 0
3 3 0
3 4 0
3 5 0
4 1 0
4 2 0
4 3 0
4 4 0
4 5 0
5 1 1
5 2 6
5 3 31
5 4 156
5 5 781
6 1 -1
6 2 -20
6 3 -169
6 4 -1160
6 5 -7381
7 1 2
7 2 16
7 3 114
7 4 800
7 5 5602
8 1 0
8 2 0
8 3 0
8 4 0
8 5 0
9 1 0
9 2 0
9 3 0
9 4 0
9 5 0
10 1 1
10 2 -18
10 3 -341
10 4 -4212
10 5 -46079
11 1 4
11 2 48
11 3 532
11 4 5856
11 5 64420
12 1 -5
12 2 -116
12 3 -1625
12 4 -20360
12 5 -247445
13 1 5
13 2 70
13 3 915
13 4 11900
13 5 154705
14 1 3
14 2 -8
14 3 -513
14 4 -10000
14 5 -159657
15 1 -2
15 2 -66
15 3 -1178
15 4 -18564
15 5 -282722
16 1 0
16 2 0
16 3 0
16 4 0
16 5 0
17 1 7
17 2 126
17 3 2149
17 4 36540
17 5 621187
18 1 -4
18 2 -200
18 3 -4732
18 4 -95120
18 5 -1800964
19 1 8
19 2 160
19 3 3048
19 4 57920
19 5 1100488
20 1 -3
20 2 -162
20 3 -3813
20 4 -79092
20 5 -1595583
21 1 -1
21 2 -80
21 3 -2109
21 4 -47200
21 5 -1011161
22 1 7
22 2 36
22 3 -665
22 4 -30744
22 5 -853565
23 1 10
23 2 240
23 3 5530
23 4 127200
23 5 2925610
24 1 -13
24 2 -500
24 3 -13273
24 4 -327560
24 5 -7929493
25 1 6
25 2 156
25 3 3906
25 4 97656
25 5 2441406
26 1 9
26 2 70
26 3 -549
26 4 -45220
26 5 -1577991
27 1 0
27 2 0
27 3 0
27 4 0
27 5 0
28 1 -1
28 2 -200
28 3 -6897
28 4 -202000
28 5 -5716841
29 1 13
29 2 390
29 3 11323
29 4 328380
29 5 9523033
30 1 -13
30 2 -1022
30 3 -39601
30 4 -1309532
30 5 -40972393
31 1 14
31 2 448
31 3 13902
31 4 430976
31 5 13360270
32 1 0
32 2 0
32 3 0
32 4 0
32 5 0
33 1 1
33 2 -96
33 3 -4655
33 4 -169824
33 5 -5781695
Best Answer
We have the following for $n \in \mathbb{N}$ : $$r(a^n)-r(a^n-1)= \begin{cases} 2a^n-1-\sigma(a^n) & \text{if $2 \mid a$} \\ \frac{3a^n-1}{2}-\sigma(a^n) & \text{if $2 \nmid a$} \end{cases}$$
Question $1$
We have: $$r(2^n)-r(2^n-1)=2(2^n)-1-\sigma(2^n)=2^{n+1}-1-(2^{n+1}-1)=0$$ $$r(3^n)-r(3^n-1)=\frac{3(3^n)-1}{2}-\sigma(3^n)=\frac{3^{n+1}-1}{2}-\bigg(\frac{3^{n+1}-1}{2}\bigg)=0$$ This solves Question $1$.
Question $2$
As mathlove points out, this is false. $110$ is a counterexample. A weaker version of this can be proven:
I personally feel that this is the heart of the problem. We have: $$a=\prod_{i=1}^k p_i^{a_i} \implies \sigma(a^n)=\prod_{i=1}^k \frac{p_i^{a_in+1}-1}{p_i-1}$$ This gives: $$\frac{\sigma(a^n)}{a^n}=\prod_{i=1}^k \frac{p_i-(1/p_i^{a_in})}{p_i-1} \implies \lim_{n \to \infty} \frac{\sigma(a^n)}{a^n}=\prod_{i=1}^k \frac{p_i}{p_i-1}=c_a$$
Now, as $n$ gets large, we can see that $\frac{\sigma(a^n)}{a^n} \to c_a$ which is a constant for $a$. We know: $$r(a^n)-r(a^n-1)= \begin{cases} 2a^n-1-\sigma(a^n) & \text{if $2 \mid a$} \\ \frac{3a^n-1}{2}-\sigma(a^n) & \text{if $2 \nmid a$} \end{cases} $$ This gives: $$r(a^n)-r(a^n-1) \sim \begin{cases} 2a^n-c_a a^n & \text{if $2 \mid a$} \\ \frac{3}{2}a^n-c_aa^n & \text{if $2 \nmid a$} \end{cases} $$
It is clear that this value will eventually become all positive or all negative (which is what we are required to show) when $c_a \neq 2$ and $c_a \neq \frac{3}{2}$.
If $c_a=2$, we have: $$\prod_{i=1}^k \frac{p_i}{p_i-1}=2$$ Clearly, we need an even prime, so let $p_1=1$. Then: $$\prod_{i=2}^k \frac{p_i}{p_i-1}=1$$ But this forces there to be no other primes, since $\frac{p_i}{p_i-1}>1$ for all primes. Since $2$ is the only prime divisor of $a$, $a$ must be a power of $2$ (which is one of the exceptions).
The same argument works for $\frac{3}{2}$ where $p_1=3$ is forced to be the only prime, giving powers of $3$ as an exception. Thus, these are the only exceptions (and we also know that in these cases, the difference is always zero). Hence, we have proven the required.
Thus, we have proven the following lemma-
Question $3$
Let $a=2p \space (p>3)$. Then: $$c_a=\frac{2}{1} \cdot \frac{p}{p-1} > 2$$ Thus, $r(a^n)-r(a^n-1)$ is eventually all negative (from lemma). At $n=1$, $$r(a)-r(a-1)=4p-1-\sigma(2p)=p-4>0$$ Thus, there is an eventual transition from positive to negative.
Let $a=3q \space (q>7)$. Then: $$c_a=\frac{3}{2} \cdot \frac{q}{q-1} > \frac{3}{2}$$ Also, $a$ is odd. Thus, $r(a^n)-r(a^n-1)$ is eventually all negative (from lemma). At $n=1$, $$r(a)-r(a-1)=\frac{9q-1}{2} - \sigma(3q) = \frac{q-9}{2}>0$$ Thus, there is an eventual transition from positive to negative.
Question $4$
We are to simply substitute $a=p$, $a=p^2$ and $a=pq$.
If $a=p$, $$r(a^n)-r(a^n-1)=\frac{3p^n-1}{2}-\sigma(p^n)=\frac{3p^n-1}{2}-\frac{p^{n+1}-1}{p-1}>0$$
If $a=p^2$, $$r(a^n)-r(a^n-1)=\frac{3p^{2n}-1}{2}-\sigma(p^{2n})=\frac{3p^{2n}-1}{2}-\frac{p^{2n+1}-1}{p-1}>0$$
If $a=pq$, $$r(a^n)-r(a^n-1)=\frac{3p^nq^n-1}{2}-\sigma(p^nq^n)=\frac{3p^nq^n-1}{2}-\bigg( \frac{p^{n+1}-1}{p-1} \cdot \frac{q^{n+1}-1}{q-1} \bigg)>0$$
All of these can be shown by expanding (strenuous but straightforward). This completes all $4$ problems.