# Number theory Challenge

If the sequence is the ordered set of sum of distinct powers of 2, then it will be

$2^0, 2^1, 2^0 + 2^1, 2^2, 2^2+2^0, 2^2+2^1,2^2+2^1+2^0,....= 1, 2, 3, 4, 5, 6, 7 = 1_2, 10_2, 11_2, 100_2, 101_2, 110_2, 111_2, ...$

So, find out the $100^{th}$ in binary notation and calculate the value in base 3 will be the answer for the ordered set of sum of distinct powers of 3.

sum of distinct powers of 3 means you can either use 0 or 1 in each digit.

$100 = 64 + 32 + 4 = 1100100_2 \\ 1100100_3 = 729 + 243 + 9 = 981.$

To my friend, Shevy Monte Carlo...

Facts:

1- Your numbers would be of form $\sum_{t=0}^{\infty} a_t \cdot 3^t , a_t\in \{0,1\}$ , such that $\{a_t\}_{t=0}^{\infty}$ is the binary representation $x$ . More precisely, any sequence of $S_x=\{a_t\}_{t=0}^{\infty}$ is in a one-to-one correspondence to a member of the original sequence, using the map $f(S_x)=\sum_{t=0}^{\infty} a_t \cdot 3^t$

2- $x$ is greater than $y$ iff $f(S_x)$ is greater than $f(S_y)$ .

3- Now that we know the ordering of the sequences, the $100$ -th number in the original sequence is same a the $100$ -th sequence

$f(S_{100})=0\cdot3^0+0\cdot3^1+1\cdot3^2+0\cdot3^3+0\cdot3^4+1\cdot3^5+1\cdot3^6$

The number of terms before n-th power of three will be $2^n-1$ (because it is same as the number of non empty subsets of the set of n integers) so the number of terms before $3^6$ is $2^6-1=63$ and the number of terms before $3^5$ is $2^5-1=31$ so the number of terms before $3^6+3^5$ is $63+1+31=95$ , thus 97th term is $3^6+3^5+1$ , 98th term is $3^6+3^5+3$ , 99th term is $3^6+3^5+3+1$ , 100th term is $3^6+3^5+3^2=981$ .

So the answer given is a little bit weird, can some one please give a better solution...

Solution: Write the numbers from 1 to 100 in binary notation. They are then your first 100 numbers in ternary notation (base 3). So the solution is (1100100)3 = 729 + 243 + 9 = 981.