(Shortlist 1998) Let $a_{1}, a_{2}, \ldots$ be an increasing sequence of natural numbers such that every natural number can be uniquely represented in the form $a_{i}+2 a_{j}+4 a_{k}$, where $i, j, k$ are not necessarily distinct. Determine $\mathrm{a}_{1998}$.
This exercise is a very good example of how a solution using generating functions can inspire a solution that does not use generating functions. Let $f(x)=\sum_{n \geqslant 0} x^{a_{n}}$. By hypothesis, we have

$$
f(x) f\left(x^{2}\right) f\left(x^{4}\right)=\sum_{n \geqslant 0} x^{n}=\frac{1}{1-x}
$$

Indeed, each term on the left is of the form $x^{a_{i}+2 a_{j}+4 a_{k}}$, and by the uniqueness of the representation, there is one and only one term of each degree. Replace $x$ with $x^{2}$: we get

$$
f\left(x^{2}\right) f\left(x^{4}\right) f\left(x^{8}\right)=\frac{1}{1-x^{2}}
$$

and combining the two equations, we have

$$
f(x)=\frac{1-x^{2}}{1-x} f\left(x^{8}\right)=(1+x) f\left(x^{8}\right)
$$

By iterating this, we have

$$
f(x)=\prod_{k \geqslant 0}\left(1+x^{8^{k}}\right)
$$

The only terms of $f(x)$ with a non-zero coefficient are those whose base 8 representation contains only the digits 0 or 1. The $n$-th such number is found by writing $n$ in base 2 and reading the result in base 8. Thus, since $1998=2^{10}+2^{9}+2^{8}+2^{7}+2^{6}+2^{3}+2^{2}+2$, we have

$$
a_{1998}=8^{10}+8^{9}+8^{8}+8^{7}+8^{6}+8^{3}+8^{2}+8=1227096648
$$

Now that we have the result thanks to the theory of generating functions, let's try to find a solution that does not involve them. Since the sequence $a_{n}$ is clearly unique, it suffices to show that the sequence $\left(b_{n}\right)$ whose $n$-th term is the base 2 representation of $n$ read in base 8, that is, the $n+1$-th number that can be written in base 8 with only 0s and 1s, satisfies the condition of the statement.

Let $m$ be a natural number. Consider the integer $c$ such that $0 \leqslant c \leqslant 8^{m}-1$, that is, the base 2 representation of $c$ contains at most $3 \mathrm{~m}$ digits, and show that $c$ can be written in the form $b_{i}+2 b_{j}+4 b_{k}$ with $0 \leqslant b_{i}, b_{j}, b_{k} \leqslant 8^{m}-1$, that is, $0 \leqslant i, j, k \leqslant 2^{m}-1$. In base 2, we have $c=\sum_{i=0}^{3 m-1} c_{i} 2^{i}$ with for all $i, c_{i} \in\{0,1\}$. Then

$$
c=\sum_{p=0}^{m-1}\left(c_{3 p} 2^{3 p}+c_{3 p+1} 2^{3 p+1}+c_{3 p+2} 2^{3 p+2}\right)=\sum_{p=0}^{m-1} c_{3 p} 8^{p}+2 \sum_{p=0}^{m-1} c_{3 p+1} 8^{p}+4 \sum_{p=0}^{m-1} c_{3 p+2} 8^{p}
$$

from which the result, by setting $i=\sum_{p=0}^{m-1} c_{3 p} 2^{p}, j=\sum_{p=0}^{m-1} c_{3 p+1} 2^{p}$ and $k=\sum_{p=0}^{m-1} c_{3 p+2^{p}}$. Thus, the $8^{m}$ integers between 0 and $8^{m}-1$ admit a representation in the form $a_{i}+2 a_{j}+4 a_{k}$ with $0 \leqslant i, j, k \leqslant 2^{m}-1$. On the other hand, all numbers of the form $a_{i}+2 a_{j}+4 a_{k}$ with $0 \leqslant i, j, k \leqslant 2^{m}-1$ are between 0 and $8^{m}-1$, and there are at most $2^{m} \times 2^{m} \times 2^{m}=8^{m}$, so the representation is in fact unique. Thus, the sequences $\left(a_{n}\right)$ and $\left(b_{n}\right)$ coincide, which concludes.