Word Problem Involving Generating Functions

Question

Question

Let $(a_n)_{n\geq 0}$ be an increasing sequence of non-negative integers such that every non-negative integer can be expressed uniquely in the form $a_i+2a_j+4a_k$ where $i,j,k$ are not necessarily distinct. Compute $a_{1998}$.

My attempt

Put $A(x)=\sum_{j\geq 0}x^{a_j}$ and translate the given condition in the language of generating functions to yield that $$ \frac{1}{1-x}=A(x)A(x^2)A(x^4).\tag{0} $$ Substituting $x^2$ in place of $x$ in $(0)$ yields that $$ \frac{A(x)A(x^2)A(x^4)}{1+x}=\frac{1}{1-x^2}=A(x^2)A(x^4)A(x^8)\tag{1} $$ So $A(x)=(1+x)A(x^8)$. Iterating we get that $$ A(x)=\prod_{j\geq0}(1+x^{8^j})=\sum_{j\geq0}x^{a_j}.\tag{2} $$ My Problem

But I am do not know how to deduce $a_{1998}$ from $(2)$. Any help is appreciated.

Answer 1

Nice approach! To finish, first check that your expression is compatible with the condition that the $a_j$ strictly increase with $j$. You can do this by proving that all coefficients in the finite product $$ P_k(x)=\prod_{j=0}^k\left(1+x^{8^j}\right)=(1+x)\left(1+x^8\right)\left(1+x^{64}\right)\ldots\left(1+x^{8^k}\right) $$ equal $0$ or $1$, using induction on $k$. (You will use that $1+8+64+\ldots+8^k<8^{k+1}$.). You will, in fact, have accomplished more, in having shown that the $a_j$ are precisely the non-negative integers whose base-$8$ representation uses only the digits $0$ and $1$.

So now you need the $1998^\text{th}$ such integer (with $0$ being the zeroth). The first will be $1_8=1$; the second will be $10_8=8$; the third will be $11_8=9$. You should now see the the prescription in jmerry's answer applies.

Answer 2

If your formula for A(x) is correct, then $a_j$ is the sum of distinct powers of eight. But 1998 is congruent to 6 mod 8 And so cannot be written in this way.

Therefore $a_{1998} = 0$.

Answer 3

I'd rather go low-tech on this one - find a few values, then look for a pattern. We clearly have $a_0=0$ as $0+2\cdot 0+4\cdot 0$ is the only way to get zero, then $a_1=1$. We get everything up to $7$ that way, but $8$ is too big, so $a_2=8$. What's next? Well, we can't get $9$; we need a copy of $8$ in there, but the remaining $1$ can't be found from the $2$ and $4$ multiples left over. Thus $a_3=9$.

After that, it's a long time - everything up to $63=9+2\cdot 9+4\cdot 9$ works. That leaves $x_4=64$ - and, similar to how we needed $9$, we need $x_5=65$.

OK, I see the pattern now - we take everything with a base-8 expansion that consists entirely of zeros and ones. Checking... we can build a sum for an arbitrary nonnegative integer "digit" by "digit", using what we already know about building $0$ through $7$ out of zeros and ones. Package everything with the same multiplier together, and there it is.

All right, how do we extract an element of the sequence of a particular index? Write it down in base $2$, read it out in base $8$. For $1998$, that's $$8^{10}+8^9+8^8+8^7+8^6+8^3+8^2+8^1 = 1227096648$$