Divisibility criteria for 3 in sum of power of sum of digits

280 Views Asked by At

Following things motivated by previous post.

Consider $a, b$ and $c$ are integer with $a\ge1$ and $b\ge 2$.

Function $D(a, b)$ define as sum of digit of $a$ in base $b$. Example $D(5,2)=2$.

Let $$f(a,b,c)=\sum_{k=1}^ac^{D(k, b)}$$

Example $f(5,2,-1)=(-1)^{D(1,2)}+(-1)^{D(2,2)}+(-1)^{D(3,2)}+(-1)^{D(4,2)}+(-1)^{D(5,2)}=(-1)+(-1)+1+(-1)+1=-1.$

Clearly If $c\equiv 0\pmod3$ then $f(a, b, c)\equiv 0\pmod3$.

Questions; are the following claims true

  1. If $c\equiv 1\pmod3$ then $f(a, b, c)\equiv a\pmod3$?

  2. If $c\equiv 2\pmod3$ and $a\equiv1\pmod2$ then $f(a, b, c)\equiv2\pmod3$?

  3. what is criteria for $f(a, b, c)\pmod3$ when $c\equiv2\pmod3$ and $a\equiv 0\pmod2$?

Source code PARI/GP

for(a=1,100,print([a, a%3,sum(k=1,a,(-2)^sumdigits(k, 2))%3]))

Table, note we take $c=10,-2\equiv 1\pmod3$

$$\begin{array}{|c |c |c|c|c|c|} \hline a & a\pmod3 & f(a, 10,10) &f(a, 2,10)&f(a, 10,-2)&f\pmod3 \\ \hline 1& 1& 10&10&-2& 1 \\ \hline 2& 2& 110&20&2& 2\\ \hline 3& 0& 1110&120&-6& 0\\ \hline 4& 1& 11110&130&10& 1\\ \hline 5& 2& 111110&230&-22& 2\\ \hline 6& 0& 1111110&330&42& 0\\ \hline 13& 1& 1111122220&3640&-332& 1\\ \hline 14& 2& 1111222220&4640&-364& 2\\ \hline 15& 0& 1112222220&14640&-300& 0\\ \hline 16& 1& 1122222220&14650&-428& 1\\ \hline 17& 2& 1222222220&14750&-172& 2\\ \hline 18& 0& 2222222220&14850&-684& 0\\ \hline 19& 1& 12222222220&15850&340& 1\\ \hline \end{array}$$

Similarly, we can check more calculations to confirm.


The solution to 1st claim

Note $(3u+1)^x\equiv 1\pmod3$ thus, when $c\equiv 1\pmod3$ then $f(a, b, c)\equiv 1+1+...+1(a \text{times})\equiv a\pmod3$

Now $2^{nd}$ and $3^{rd}$ questions are left.

1

There are 1 best solutions below

4
On BEST ANSWER

The second claim is true.

First of all, let us prove the following lemma :

Lemma : If $b$ is odd, then for every positive integer $\ell$, $$(-1)^{D(\ell,b)}+(-1)^{D(\ell+1,b)}=0\tag1$$

Proof :

Let $a_i$ be the $i$-th digit (from the right) of $\ell$ in base $b$. Let $n$ be the number of the digits of $\ell$ in base $b$. Also, let $c_i$ be the $i$-th digit (from the right) of $\ell+1$ in base $b$. Let $N$ be the number of the digits of $\ell+1$ in base $b$.

Then, we can write $$\ell=\overline{a_na_{n-1}\cdots a_2a_1}\qquad\text{and}\qquad \ell+1=\overline{c_Nc_{N-1}\cdots c_2c_1}$$ (For example, if $\ell=19$ and $b=3$, then $n=3$ and $a_1=1,a_2=0$ and $a_3=2$.)

  • If $a_1\not=b-1$, then we have $N=n$ and $c_1=a_1+1$. Also, $c_i=a_i$ holds for every $2\le i\le n$. So, we have $D(\ell+1,b)-D(\ell,b)=1$ from which $(1)$ follows.

  • If there is a positive integer $s\ (\lt n)$ such that $a_1=a_2=\cdots=a_s=b-1$ and $a_{s+1}\not=b-1$, then we have $N=n$ with $c_{s+1}=a_{s+1}+1$. Also, $c_i=0$ holds for every $1\le i\le s$. Also, $c_{i}=a_i$ holds for every $s+2\le i\le n$. So, we have $$\begin{align}&D(\ell+1,b)-D(\ell,b) \\\\&=\bigg(s(b-1)+a_{s+1}+a_{s+2}+a_{s+3}+\cdots+a_n\bigg) \\&\qquad\qquad -\bigg((a_{s+1}+1)+a_{s+2}+a_{s+3}+\cdots +a_n\bigg) \\\\&=s(\underbrace{b-1}_{\text{even}})-1\equiv 1\pmod 2\end{align}$$from which $(1)$ follows.

  • If $a_i=b-1$ for every $1\le i\le n$, then $N=n+1$ and $c_{N}=1$. Also, $c_i=0$ holds for every $1\le i\le N-1$. So, we have $$D(\ell+1,b)-D(\ell,b)=n(\underbrace{b-1}_{\text{even}})-1\equiv 1\pmod 2$$ from which $(1)$ holds.$\quad\blacksquare$

It follows from the lemma that if both $a$ and $b$ are odd, then $\displaystyle\sum_{k=1}^a(-1)^{D(k, b)}=-1$.

This answer has proved that if $a$ is odd and $b$ is even, then $\displaystyle\sum_{k=1}^a(-1)^{D(k, b)}=-1$.

Therefore, we can say that if $a$ is odd, then $\displaystyle\sum_{k=1}^a(-1)^{D(k, b)}=-1$.

So, if $c\equiv 2\pmod3$ and $a\equiv1\pmod2$, then we have $$\begin{align}f(a,b,c)&=\sum_{k=1}^ac^{D(k, b)} \\\\&\equiv\sum_{k=1}^a(-1)^{D(k, b)}\pmod 3 \\\\&\equiv 2\pmod 3\end{align}$$

So, the second claim is true.


  1. what is criteria for $f(a, b, c)\pmod3$ when $c\equiv2\pmod3$ and $a\equiv 0\pmod2$?

It follows from the lemma that if $a$ is even and $b$ is odd, then $\displaystyle\sum_{k=1}^a(-1)^{D(k, b)}=0$.

This answer has proved that if both $a$ and $b$ are even, then $\displaystyle\sum_{k=1}^a(-1)^{D(k, b)}=-1-(-1)^{D(a+1,b)}$.

So, if $c\equiv 2\pmod 3$ and $a\equiv 0\pmod 2$, then we have $$\begin{align}f(a,b,c)&=\sum_{k=1}^ac^{D(k, b)} \\\\&\equiv \sum_{k=1}^a(-1)^{D(k, b)}\pmod 3 \\\\&\equiv \begin{cases}-1-(-1)^{D(a+1,b)}\pmod 3&\text{if $b$ is even} \\\\0\pmod 3&\text{if $b$ is odd}\end{cases} \\\\&\equiv\begin{cases}1\pmod 3&\text{if both $b$ and $D(a+1,b)$ are even}\\\\ 0\pmod 3&\text{otherwise}\end{cases}\end{align}$$