# Finding out a general formula for the nth term of a sequence

The question is to find out the $nth$ term of the sequence $$1,3,4,9,10,12,13,...$$ which consists of all those positive integers which are powers of 3 or sums of distinct powers of 3.

My attempt

Let $a_n$ denote the sub-sequence which starts from $3^n$.Clearly the subsequence goes as $$3^n,3^n+3^0,3^n+3^1,3^n+3^0+3^1,...3^n+3^{n-1}+3^{n-2}+...+3^0$$ The total number of terms in this subsequence is $2^n$.So the $nth$ term of the sequence is given by

Let i be the greatest integer satisfying $2^{i+1}<n+1$.Then the $nth$ term in the sequence is given by $n-(2^{i+1}-1)$ term in the subsequence starting from $3^{i+1}$.I am not able to proceed further.Any ideas?Thanks.

• Write $n$ in base two, and then think of it as being a base three integer after all :-) – Jyrki Lahtonen Apr 7 '17 at 18:30

You can get $a_n$ by writing $n$ in binary and interpreting it as a base $3$ number. For example, to get $a_{21}$ we note that $21=10101_2$ so $a_{21}=3^4+3^2+3^0=91_{10}$ One way to express this is $$a_n=\sum_{i=0}^\infty3^i\frac {n \bmod {2^{i+1}}}{2^{i}}$$ where we are using integer division. The fraction picks out whether the $i^{th}$ bit in the binary representation of $n$ is a $1$.

Too long for a comment.

I doubt that there is a reasonable answer to your question. You are asking for the integers with no $2$ in their base $3$ expansion.

Erdos studied the asymptotics of the question:

On Arithmetic Properties of Integers with Missing Digits I: Distribution in Residue Classes (http://www.sciencedirect.com/science/article/pii/S0022314X98922296)

Sums of Reciprocals of Integers Missing a Given Digit
Robert Baillie
The American Mathematical Monthly
Vol. 86, No. 5 (May, 1979), pp. 372-374
https://www.jstor.org/stable/2321096?seq=1#page_scan_tab_contents