Finding $a_1^2+a_2^2+a_3^2+\cdots+a_n^2 \pmod{1000}$ where $a_1, \ldots, a_n$ are numbers in a set $\mathcal{S}$ relating to base $3.$

Question

Let set $\mathcal{S}$ define the positive integers $a_1, a_2, \ldots, a_n < 3^{2019}$ which contain only $0$'s and $1$'s in their ternary base representation. Compute $$a_1^2+a_2^2+a_3^2+\cdots+a_n^2 \pmod{1000}.$$

I started by converting $1, 10, 100, \ldots$ base $3$ to base $10.$ This clearly gives $3^0, 3^1, 3^2, \ldots$ in base $10.$ Then I considered the the possible numbers in base $3$ that weren't just a $1$ with a bunch of trailing zeroes, and split them into sections. We get $(1), (10, 11), (100, 101, 110, 111), (1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111), \ldots.$ Then I counted the numbers in each of the pairs and noted that they were simply powers of $2,$ specifically for some $3^n,$ there would be $2^n-1$ more consecutive numbers that would also be in $\mathcal{S}.$ However, I am not sure how to use this information, especially because the sum of the squares of every element in $\mathcal{S}$ seems tricky to deal with, and taking mod $1000$ will be very tricky with such large numbers. Is it possible to manipulate the question in some way to make it easy? May I have some help? Thanks in advance.

Answer 1

Most of the way there. One big step remaining.

Let $U=\{0,1,2,\dots,2018\}.$ Then the elements of $\mathcal S$ correspond to the subset sets $T\subseteq U,$ with $a_{T}=\sum_{k\in T}3^k.$

Then $$a_T^2=\sum_{(j,k)\in T^2} 3^{j+k}$$

So your sum is:

$$\sum_{T\subseteq U} \sum_{(j,k)\in T^2}3^{j+k}$$

Rearranging this, we get: $$2^{2018}\sum_{k=0}^{2018} 3^{2k}+2^{2017}\sum_{j\neq k}3^{j+k}\\=2^{2017}\sum_{k=0}^{2018}3^{2k}+2^{2017}\left(\sum_{k=0}^{2018} 3^k\right)^2\\=2^{2014}(9^{2019}-1)+2^{2015}\left(3^{2019}-1\right)^2$$ Where there are $2^{2018}$ subsets $T$ containing each $k$ and $2^{2017}$ subsets containing any pair $j,k$ when each $j\neq k.$

This number is obviously $0$ modulo $8.$

Modulo $125,$ $2^{100}\equiv 3^{100}\equiv 1,$ so you need to figure out:

$$2^{14}(9^{19}-1)+2^{15}\left(3^{19}-1\right)^2\pmod {125}$$

You can take common factors out and get:

$$2^{14}(3^{19}-1)\left((3^{19}+1)+2(3^{19}-1)\right)=2^{14}(3^{19}-1)\left(3^{20}-1\right)$$ I’ll leave it for you to calculate that last step and the Chinese remainder theorem to calculate the remainder modulo $1000.$