Sorry for my interruption, I am looking for a solution to this question: Calculate
$$\sum_{k=0}^{2001}\left \lfloor \frac{2^k}{2003}\right \rfloor$$ without using computational engines, with $\lfloor x \rfloor$ denoting the largest integer that does not succeed x. I hope you can answer this question. And sorry for my mistakes, English is my second language.
Answer
If we write $2^k=2003q_k+r_k$ you are looking for the sum of the $q_k$. Assume for the moment that we know that $2$ is a primitive root $\bmod 2003$. In that case the $r_k$ run through all the numbers from $1$ through $2002$ and we can write
$$\sum_{k=0}^{2001}\Big \lfloor \frac{2^k}{2003}\Big \rfloor=\sum_{k=0}^{2001} \frac {2^k-r_k}{2003}=\frac {2^{2002}-1}{2003}-\frac {2002\cdot 2003}{2\cdot 2003}=\frac {2^{2002}-1}{2003}-1001$$
This gives an explicit expression without summation or floor functions, but actually computing it is beyond most of our patience as it will have about $600$ digits.
I don't have an easy way to show $2$ is a primitive root. The order of $2$ must divide $2002=2\cdot7\cdot 11 \cdot 13$ so we can just check whether $2$ to any of $14$ powers is equivalent to $1 \bmod 2003$. You can generate $2^{2^n}$ by repeated squaring and then multiply them, but it will be tedious.
I realized that all that is needed for this argument to work is to show $2^{1001}\equiv -1 \pmod {2003}$, which will be true if $2$ is a primitive root but might be otherwise. With repeated squaring that is more within the range of hand computation, but still tedious.
No comments:
Post a Comment