Does parity of $f(a)$ and $f(a+1)$ are same whenever $a$ is even? Question related to sum of digits

53 Views Asked by At

Let $D(a, b)$ denotes sum of digits of $a$ in base $b$.

Example: $D(5,2)=2,D(1227,10)=1+2+2+7=12$

Define $f(a)=\sum_{i=2}^aD(a, i)$ where $a\ge2$.

Example $f(5)=D(5,2)+D(5,3)+D(5,4)+D(5,5)=2+3+2+1=8$

Can it be shown that

if $a$ is even then $f(a)\equiv f(a+1)\pmod2$

Or parity of $f(a)$ and $f(a+1)$ are same

Table

$$\begin{array}{c | c | c |c | } a & f(a) & f(a)\pmod2 \\ \hline 2 & 1 & 1 \\ \hline 3 & 3 & 1 \\ \hline 4 &4& 0 \\ \hline 5 &8& 0 \\ \hline 6 &10& 0 \\ \hline 7 &16& 0 \\ \hline 8 &17& 1 \\ \hline 9 &21& 1 \\ \hline \vdots &\vdots &\vdots \\ \end{array}$$

I checked up to $a\le5000$ holds the claim true.

Note: $D(odd, odd)=odd$ and $D(even, odd)=even$

Source Code, PARI/GP

for(a=2,100,print([a,sum(i=2,a,sumdigits(a, i))%2]))
1

There are 1 best solutions below

0
On BEST ANSWER

Assume $a$ is even. That means we already know the parity with $i=2j+1$ odd: $D(a, 2j+1)=2k_j$ (even) and $D(a+1,2j+1)=2k'_j+1$ (odd) for all $j=1,...,\frac{a}{2} - 1$.

Now take a look for $i=2j$ even: We don't know the concrete value of $D(a,2j)$, but we can draw a connection between $D(a,2j)$ and $D(a+1,2j)$. As $a$ is even the last digit in any even-numbered system must be even as well (otherwise we will get a contradiction $\text{mod }2$)! This means the last digit can never be $i-1$ so if we add $1$ we will only increase the last digit to a value $\leq i-1$ and no overflow to the next digit is generated. So all digits besides the last one stay untouched.

That means we get $D(a+1,2j) = D(a,2j) + 1$. Summing all information up we can conclude:

$$ f(a) = \sum_{j=1}^{a/2} D(a,2j) + \sum_{j=1}^{a/2-1} D(a,2j+1) \\ f(a+1) = \sum_{j=1}^{a/2} D(a+1,2j) + \sum_{j=1}^{a/2-1} D(a+1,2j+1) + D(a+1,a+1) \\ = \sum_{j=1}^{a/2} D(a,2j) + \frac{a}{2} \cdot 1 + \sum_{j=1}^{a/2-1}D(a+1,2j+1) + 1 $$

Considering everything $\text{mod }2$ we can use that $D(a+1,2j+1) \equiv D(a,2j+1)+1$: $$ f(a+1) \equiv \sum_{j=1}^{a/2} D(a,2j) + \frac{a}{2} \cdot 1 + \sum_{j=1}^{a/2-1}D(a,2j+1) + \left(\frac{a}{2}-1\right) \cdot 1 + 1 \\ \equiv f(a) + \frac{a}{2} + \frac{a}{2} -1 + 1 = f(a) + a \equiv f(a) \mod 2 $$

Here we have it that $$f(a) \equiv f(a+1) \mod 2$$ if $a$ is even.