# 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.$

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.

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}$$

$$\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.$$

• Thanks very much for the insightful response! I think I can take it from here :) Commented Apr 20, 2022 at 1:54
• No, $$x\equiv 100\pmod{125}\\x\equiv 0\pmod{8}$$ so what is $x\pmod{1000}?$ @mathisfun Commented Apr 20, 2022 at 2:48
• i got it, thank you! Commented Apr 20, 2022 at 3:37