0
$\begingroup$

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.

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

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.

$\endgroup$
0
$\begingroup$

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

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.