A weird sequence

Question

Let the given sequence be,

$$1,6,9,11,16,19,61,66,69,91,96,99,111,116...$$

If $A_n$ represents the $n^{th}$ term of this sequence then calculate:

1. $A_{100}$
2. $A_k=16619,$ find $k$?

---

My Attempt :

I was able to hardwire the solution, but I don't find it decent enough and I think that there must be a more mathematical solution to this.

I saw that the sequence was of type,

$$1,6,9$$ $$(A_1)1,(A_1)6,(A_1)9$$ $$(A_2)1,(A_2)6,(A_2)9$$ $$(A_3)1...$$

To calculate $A_{100}$, I was able to conclude that

$$A_{100}=(A_{33})1$$

Further, $A_{33}=(A_{10})9$

$A_{10}=(A_3)1=91 \implies A_{33}=(A_{10})9=919 $

$$A_{100}=9191$$

---

For the second part, I started breaking up the $n^{th}$ term,

$$A_k=16619=(A_m)9$$

$$A_m=1661=(A_n)1$$

$$A_n=166=(A_p)6$$

$$A_p=16 \implies p=5 $$

$$A_n=(A_5)6 \implies n=5*3+2=17$$

$$A_m=(A_{17})1 \implies n=17*3+1=52$$

$$A_k=(A_{52})9 \implies n=52*3+3=159$$

$$k=159$$

---

I know that both the solutions are correct. But how do I approach it more professionally?

Answer 1

If you rewrite the numbers with the substitution $169\leftrightarrow012$, the sequence

$$0,1,2,00,01,02,10,11,12,20,21,22,000,001...$$

is enumerating all the base-$3$ numbers with $1,2,3,\cdots$ digits.

The starting indexes of the subsequences of $d$ digits are

$$1,1+3,1+3+3^2,1+3+3^2+3^3,\cdots=1+\frac32(3^{d-1}-1).$$

Then $a_{100_{10}}$ is a number of $4$ digits (they start at $A_{40_{10}}$), namely $60_{10}$, written $2020_3$, i.e. $9191$.

And $16619$ corresponds to $01102_3=38_{10}$, counting from $121_{10}$, i.e. $k=159_{10}$.

---

The general formula is a little difficult. For the $k^{th}$ term, consider

$$d=\left\lfloor\log_3\left(\frac23(k-1)+1\right)\right\rfloor.$$

Then

$$a_k=k-1-\frac32(3^{d-1}-1),$$

which must be written in base $3$ with $d$ digits, and the digits renamed $012\leftrightarrow169$.

Conversely, to get $k$, rename to a base-$3$ number and take its value, to which you add the offset corresponding to the number of digits.

Answer 2

There are $3^1+3^2+3^3+3^4=3\cdot \frac {3^4-1}{3-1}=120$ numbers in the list that have $1,2,3,4$ digits. Which is now the place for our number of five digits? Replace formally $1\to0$, $6\to1$, $9\to2$, and we need the position of the number $01102$ in the ordered list of p4one numbers $00000$, $00001$, $00002$, $00010$, ... with five digits written in base $3$. The place of $00000$ is $\boxed 1$, the place of $01102$ is $$\boxed 1 + 0\cdot 3^4 + 1\cdot 3^3 + 1\cdot 3^2 + 0\cdot 3^1 + 2\cdot 3^0=39\ ,$$ so the answer is $k=120+39=159$.

---

Later edit. The question about $A_{100}$... have seen it only after the comment, sorry.

$3^1+3^2+3^3=39$, so we need to count further $61$ numbers with four digits among $1,6,9$. There are $3^3+3^3$ such numbers of the shape $1xyz$ and/or $6xyz$, so far we have $93$ numbers in the list. The next ones are $91xy$ where $xy$ runs in

$11$, $16$, $19$ ; $61$, $66$, $69$ ; $\boxed{91}$, $96$, $99$ .

So $A_{100}=9191$, corresponding to the boxed number above.

---

Computer check, here sagemath, in a lazy implementation:

sage: A = [0] + [k for k in [1..10^5] if Set( k.digits() ).issubset( Set([1,6,9]) ) ]
....: A[100]
....: A[159]
....: 
9191
16619

Answer 3

One possible way of tidying up the proof could be to express the terms of the sequence in a closed form, as:

$A_n$ is the base-$3$ representation of $B_n$, written as a string of length $i$ with the substitutions $0,1,2\rightarrow 1,6,9$.

Where $B_n=n-\frac{3^i-1}{2}$ and $i={\lfloor\log_3(2n+1)\rfloor}$.

Substituting $n=100$ into these formulae immediately gives an answer to the first question, as $B_{100}=60$ and $A_{100}=9191$.

For the second question, if $A_k=16619$, the length of the string tells us that $i=5$. Then, we find $B_n=01102_3\rightarrow 38_{10}$ so we have to solve $n-\frac{1}{2}\left(3^5-1\right)=38$. Hence, $n=159$.

---

I derived this formula as follows: Using the other answers' suggestion to rewrite the series in terms of $0,1,2$ and then order the terms into descending columns by their number of digits:

$$\begin{aligned}&0&00&&000\\ &1&01&&001\\ &2&02&&002\\ &&10&&010\\ &&11&&011\\ &&12&&012\\ &&\vdots&&\vdots\\\end{aligned}$$

We can see that one way of expressing the sequence could be that each column is counting up in base $3$ but the count is reset when you transition to the next column. It's not hard to see that there are $3^n$ terms with $n$ digits. So the count is reset on the $1$st, $4$th, $13$th, $40$th, … elements. This is equivalent to $\frac{3^i-1}{2}$, where $i$ is the column number.

Hence another way of expressing term $A_n$ could be "the base-$3$ representation of $\left(n-\frac{3^i-1}{2}\right)$, where $i$ is the largest natural number such that $\left(n-\frac{3^i-1}{2}\right)$ is nonnegative." If $\left(n-\frac{3^i-1}{2}\right)\geq0$ then $\log_3(2n+1)\geq i$, so $i=\lfloor\log_3(2n+1)\rfloor$.

Answer 4

Decimal to Code

1. The number of digits needed to represent $n$ is $d=\lfloor\log_3(2n+1)\rfloor$.
2. Add $n-\frac{3^d-1}2$ in base $3$ to $\overbrace{11\dots1}^\text{$d$ ones}$.
3. Convert digits $\left\{\begin{align}1&\mapsto1\\2&\mapsto6\\3&\mapsto9\end{align}\right.$

For example:
1. $n=100\implies d=4$ and $n-\frac{3^d-1}2=60$.
2. Thus, we get $\overbrace{2020}^{60}+\overbrace{1111}^{d=4}=3131$.
3. Finally, $3131\mapsto9191$.

---

Code to Decimal

1. Convert digits $\left\{\begin{align}1&\mapsto1\\6&\mapsto2\\9&\mapsto3\end{align}\right.$
2. Apply base $3$ place values to the digits.

For example:
1. $16619\mapsto12213$.
2. Thus, we get $n=1\cdot3^4+2\cdot3^3+2\cdot3^2+1\cdot3^1+3\cdot3^0=159$.