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.

  • $\begingroup$ Write $n$ in base two, and then think of it as being a base three integer after all :-) $\endgroup$ – 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


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.