Vrftsjtryk

Question

Let $(a_n)_{ngeq 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_{jgeq 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_{jgeq0}(1+x^{8^j})=sum_{jgeq0}x^{a_j}.tag{2}
$$
My Problem

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

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}^kleft(1+x^{8^j}right)=(1+x)left(1+x^8right)left(1+x^{64}right)ldotsleft(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.

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+2cdot 0+4cdot 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+2cdot 9+4cdot 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$$

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$.