# Finding the $100$-th term of $1,3,4,9,10,12,13\dots$ (powers of $3$, or sums of distinct powers of $3$)

The increasing sequence $$1,3,4,9,10,12,13\dots$$ consists of all positive integers which are power of $$3$$ or sums of distinct powers of $$3$$. Find the $$100$$-th term of this sequence.

• What's a hundred in base $2$? – Lord Shark the Unknown Nov 7 '18 at 4:46
• @Lord Shark the Unknown: Bet you think that you are clever. Well, you are. So there! – marty cohen Nov 7 '18 at 5:40

It's clear the numbers are:

$$1, 3, 3^2, 3^3, .....$$

$$1+3, 1+ 3^2, 1 + 3^3, ...$$

$$1 + 3 +3^2, 1 + 3 + 3^2,....$$

the only issue is what order do we put them in?

The thing to note is that we can't have anything $$+ 3^k$$ until we have $$3^k$$ first and $$1 + 3 + 3^2 + .... + 3^k < 3^{k+1}$$ so we must got through everything $$+ 3^k$$ before we can get to $$3^{k+1}$$.

So we have a rather recursive pattern.

$$k = 0$$; First term: $$1$$

$$k = 1$$;Term 2-3; $$3; 3+1$$

$$k = 2$$; Term 4-7: $$3^2; 3^2 + 1; 3^2 + 3; 3^2 + 3 + 1$$

$$k = 3$$; Term 8-15: $$3^3; 3^3 + 1; 3^3 + 3; 3^3 + 3 + 1; 3^3 + 3^2; 3^3 + 3^2 + 1; 3^3 + 3^2 + 3; 3^3 + 3^2 + 3 + 1$$.

....etc.

So of the group $$k=k$$ we have stuff $$+3^k$$ and the "stuff" can be for each $$0\le i < k$$ that we either add $$3^i$$ or .. we don't. So there are $$2^{k}$$ in the $$k$$ group. And $$2^{k-1}$$ in the $$k-1$$ group.

And before the $$k$$th group we have $$1 + 2 + 2^2 + ... + 2^{k-1} =2^k - 1$$ terms. So the $$k$$th group starts and $$2^k$$ and goes to for $$2^k$$ terms to end at $$2^k + (2^k -1) = 2^{k+1} -1$$.

And we stuff the $$k$$ group in order of fitting the subgroups of lower values than $$k$$ in them first.

$$3^k, 1+3^k, 3+3^k, 1+3 + 3^k , 3^2 + 3^k, etc;$$

And each sum in the $$k$$ group is of the form $$b_0*1 + b_1*3 + b_2*3^2 + ..... + b_{k-1}*3^{k-1} + 3^k; b_i = \{0,1\}$$ with the $$b_0*1 + b_1*3 + b_2*3^2 + ..... + b_{k-1}*3^{k-1}$$ terms ordered as they were in the $$k-1$$ group.

So as $$64 < 100< 128$$ so the 100th term is $$3^6 + something$$.

So the $$1$$st term is $$1$$. The second is $$3$$. The $$4$$th is $$3^2$$ and the $$64$$ is $$3^6$$. Then $$64 + 32=96$$th term is $$3^6+3^5$$ and $$64+32 + 4=100$$ is $$3^6 + 3^5 + 3^2$$.

Then we give ourselves a giant dope slap to the head because this is clearly just binary representation.

That is: If $$n = \sum_{i = 0}^m b_i*2^i; b_i=\{0,1\}$$ be the binary representation of $$n$$ then $$a_n$$ is $$\sum_{i=0} b_i 3^i$$ And that preserves order.

Note that, if you represent the numbers in base $$3$$, that you get the numbers $$1, 10, 11, 100 ...$$ which are numbers in base $$3$$ such that each of the digits is either $$1$$ or $$0$$.

Therefore, we just need to find the $$100$$th number in the series and convert it from base $$3$$ to base $$10$$. This is equivalent to finding the $$100$$th binary number, which is $$1100100$$. Therefore, because we express this number in base 3 the $$100$$th term in the series is $$1100100$$ in base 3, which is $$981$$.

• you are talking about base 3 then using binary ? – maveric Nov 7 '18 at 7:12
• Andin last line it should not be 11001003 but 1100100 – maveric Nov 7 '18 at 7:18

Try this question first: how many numbers can be derived with $$3^i$$ for $$i$$ from $$0$$ to $$n$$ using the way described in OP? Or a different but very similar question how many such numbers are there that are less then $$3^n$$

You have

$$3^0, 3^1, 3^2, \cdots, 3^n$$

The nature of the numbers present in the sequence determines that however you pick numbers from it, a different combination (of the numbers you picked) will result in a different sum. For each number in the sequence, you either pick it or leave it. So numbers derived from the sequence, including numbers already in it, are $$2^n-1$$, minus $$1$$ because we are not allow to picking no numbers at all.

This is what Lord Shark the Unknown meant by the binary representation of 100.

\begin{align} \text{Seq}\hspace{1cm} &\text{Binary} & n\text{th Number}&\\ 1\hspace{1cm}& 1& 1\hspace{0.5cm}&\\ 2\hspace{1cm}& 10 &3\hspace{0.5cm}& \text{bin.rep 1 with 1 trailing zero}=3^1\\ 3\hspace{1cm}& 11 &4\hspace{0.5cm}& \\ 4\hspace{1cm}& 100 &9\hspace{0.5cm}& \text{bin.rep. 1 with 2 trailing zero} =3^2\\ 5\hspace{1cm}& 101 &10\hspace{0.5cm}& 10=9+1\\ 6\hspace{1cm}& 110 &12\hspace{0.5cm}& \text{binary 100+binary 10, sum of corresponding numbers } 9+3=12\\ 7\hspace{1cm}& 111 &13\hspace{0.5cm}& \text{binary 100+binary 11, sum of corresponding numbers }9+4=13\\ 8\hspace{1cm}& 1000 &27\hspace{0.5cm}& \text{binary rep 1 with 3 trailing zero}=3^3\\ \end{align}

$$100=64+32+4=2^6+2^5+2^2$$ so the number you are looking at is $$3^6+3^5+3^2$$

This technique also applies if a different base is used.