Sum of Powers of Three

Notice that $2\times3^j<3^{j+1}$ . This implies that $\displaystyle\sum_{i=0}^j3^i<3^{j+1}$ . This means that the function which accepts a binary integer $\overline{a_ja_{j-1}\dots a_1a_0}_2$ and returns $\displaystyle\sum_{i=0}^ja_i\times3^i$ is a strictly increasing function. The binary representation of 50 is $110010_2$ , so the 50th smallest positive integer that can be written as the sum of distinct non-negative integer powers of 3 is $3^5+3^4+3^1=327$ .

[Slight edits for clarity - Calvin]

Consider the base 3 representation of all such elements. Since all the powers are distinct, they consist of the numbers 1 or 0. Thus, there is a bijection between such numbers, and the natural numbers written in binary, by changing the base from $3$ to $2$ , and vice versa. This function is an increasing function, so to find the 50th smallest number, we take $50 =110010_2$ , and convert it to ternary to obtain $110010_3 = 243 + 81 + 3= 327$ .

The natural number can be represented as $3^{x1}+3^{x2}+...+3^{xn}$ where x1<x2<...<xn. First consider all the natural numbers which have 3^xn in their representation as the highest power of 3. The no. of such numbers = nC0+nC1+nC2+...+nCn=2^n. Let us call the group of such numbers as n-bracket. Apart from these brackets we have one more element i.e. 3^0=1. Now we arrange the brackets in the ascending order of their S.No. i.e. 1,1-bracket,2-bracket,... smallest element of n-bracket=3^n. Largest element of (n-1)-bracket= $3^1+3^2+...+3^{n-1}=\frac {3^n-3}{2}$ which is smaller than 3^n. So as a whole the (n-1)-bracket is smaller than the n-bracket. So by arranging the individual elements of all the brackets and by arranging the brackets serial wise we will actually arrange all the elements in a sorted manner. No. of elements before n-bracket= $1+2^1+2^2+....+2^{n-1}=2^n-1$ . Interestingly, all the elements(except 3^n) of n-bracket can be obtained by adding 3^n to all the elements of the preceding brackets i.e. 1-bracket, 2-bracket,...,(n-1)-bracket. .......(1) Now, suppose we wish to find the k-th smallest number. In order to find the bracket to which the number belongs find n such that $2^n \leq number \leq 2^{n+1}-1$ . The number belongs to n-bracket. After finding the bracket we only have to find the k-(2^n-1)th smallest number in the bracket. ........(2) Using fact (1) we can again break the n-bracket into its constituent brackets by ignoring 3^n. Once we find the number of the correct order we will simply add 3^n to it. ........(3) Care must be taken that after applying steps (2) and (3) once, we will have to look for (k-2^n)th smallest number in the smaller brackets. ........(4) We can reduce our search space by recursively using steps (2) & (3). But we need to define a reference point where we will end our recursive process. Let us have the following reference(sorted in ascending order): 1)0(in order to accommodate 3^n). 2)1 3)3 4)4 (1-bracket) 5)9 6)10 7)12 8)13 (2-bracket) So, if in our recursive process we are required to find the m-th smallest number $(1\leq m \leq 7)$ we simply look for the number corresponding to m-th serial number in the above reference list and accordingly add powers of 3 to it(as was stated in step 3). Care must be taken if the starting value of k is less than 9. In that case we should look for the (k+1)th element from the reference list. In case of k=8 the required number will obviously be 3^3=27. Now we pick up our case i.e. we find the 50th smallest number. note that $2^5 \leq 50 \leq 2^6-1$ . So, the 50th smallest number is in 5-bracket. Now $50-(2^5-1)=19 and 2^4 \leq 19 \leq 2^5-1$ . Inside the 5-bracket 50th smallest number is in the 4-bracket at the $19-2^4=3 position$ . We reach the terminating condition 3 corresponds to 3. So, our required number is $3^5+3^4+3 = 327$ .

$The\ representation\ of\ the\ 50th\ smallest\ such\ number\ will$

$therefore\ be\ the\ same\ as\ the\ representation\ of\ the\ number\ 50\ in$

$base\ 2$

$50_{10}$ = $110010_{2}$

$110010_{3}$ = $3^{5} + 3^{4} + 3^{1} = \boxed{327_{10}}$

Realised that each power of three can have all previously worked out answers added to it to make a new valid answer. Thirty-second value is 243 (3 to power 5) then find 18th number in original sequence (84) to add on

Since we need the sum as of powers of 3, it can be written as $a_n=[b_0]*3^0+[b_1]*3^1+...+[b_l]*3^l$ , where $a_n$ is the nth smallest number possible and that $b_k$ (for any real k )= 0 or 1. To get the correct combination of { $b_0,...,b_l$ } for each $a_n$ , we need to write n in terms of base 2. Now 50 in base 2=110010, so $b_5=1, b_4=1, b_3=0, b_2=0, b_1=1$ and $b_0=0$ and $b_m=0$ for m>5. So $a_{50}=3^5+3^4+3=327$

I did it just like Calvin said..

N=a0.3^0 +a1.3^1+a2.3^2+....+an.3^n+.....
ai=0 or 1 (ai-->i'th coefficient of above polynomial)
the No.s should to fit into this description...

since ai=0 or 1--> I used python to find (a0,a1,a2...)=bin(50)[:1;-1]

(coz the coeficients are either 1 or 0, combination of lower powers of 3 can't overtake higher powers of 3) hence 50thsmallest combination of powers of 3 is virtually given by bin(50)

==>(a0,a1,a2...)=tuple(bin(50)[:1:-1])=('0', '1', '0', '0', '1', '1')

==>50th smallest N=0* 3^0+1* 3^1+0* 3^2+0* 3^3+1* 3^4+1* 3^5= 327