GeneratingFunction IMO Challenging
1998


Problem - 4336

Let $a_0$, $a_1$, $a_2$, $\cdots$ be an increasing sequence of non-negative integers such that every non-negative integer can be expressed uniquely in the form of $(a_i + 2a_j+4a_k)$ where $i$, $j$, and $k$ are not necessarily distinct. Determine $a_{1998}$.


Let $$f(x)=\sum_{i=0}^{\infty}x^{a_i}$$

Then the given condition implies $$f(x)f(x^2)f(x^4)=\sum_{n=0}^{\infty}x^n=\frac{1}{1-x}$$

Replacing $x$ with $x^2$ gives $$f(x^2)f(x^4)f(x^8)=\frac{1}{1-x^2}$$

These two relationships above imply $$f(x)=(1+x)f(x^8)$$

Repeating this process recursively will give $$f(x)=\left(1+x\right)\left(1+x^8\right)\left(1+x^{8^2}\right)\left(1+x^{8^3}\right)\cdots$$

$$\therefore\quad \sum_{i=0}^{\infty}x^{a_i} =\left(1+x\right)\left(1+x^8\right)\left(1+x^{8^2}\right)\left(1+x^{8^3}\right)\cdots $$

Expanding the right side shows that $a_i$ are those non-negative integers whose base $8$ representation has only digit $0$ or $1$.

As $1998 = 2+2^2 + 2^3 + 2^6 + 2^7+2^8+2^9+2^{10}$, therefore $$a_{1998}=\boxed{8+8^2 + 8^3 + 8^6 + 8^7+8^8+8^9+8^{10}}$$

report an error