Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

I have my doubts about this since I might have rushed into it a bit, but here it goes: Let $f:[0,1),\ f(x):=x^{a_0}+x^{a_1}+x^{a_2}+\ldots$. Since $0$ can be represented in the mentioned way, we must have $a_0=0$ (this will be important a bit later). We have $f(x)f(x^2)f(x^4)=1+x+x^2+\ldots=\frac 1{1-x}$. We do this again for $x\to x^2$ and we get $f(x^2)f(x^4)f(x^8)=\frac 1{1-x^2}$. Divide the first relation by the second one to get $\frac {f(x)}{f(x^8)}=1+x\ (*)$. In the same way we get $\frac{f(x^8)}{f(x^{8^2})}=1+x^8$, and so on. Since $f(0)=1$, for a certain $x$ we have $\lim_{n\to\infty}f(x^{8^n})=f(0)=1$, so, by fixing $x$ and multiplying the relations of the type $(*)$, we get $f(x)=(1+x)(1+x^8)(1+x^{8^2})\ldots$. What we need to find is the $1998$'th positive exponent (in increasing order) from this infinite series. In order to finish it, take $1998$, write it in base $2$, and read the result in base $8$. What we get is $a_{1998}$. I guess that, if I didn't make any mistakes, it should be $8+8^2+8^3+8^6+8^7+8^8+8^9+8^{10}$. The answer looks really strange, and that's what makes me have doubts .

Could somebody explain this a bit more, because i dont really get the solution.

I have a bit different solution: $ \sum_{i,j,k=0}^{n-1} a_i + 2a_j + 4a_k$ is the sum of the first $ n^3$ numbers. So $ \sum_{i,j,k=0}^{n-1} a_i + 2a_j + 4a_k = 0 + 1 + ... + (n^3-1) = \frac{n^3(n^3-1)}{2}$ On the other hand: $ \sum_{i,j,k=0}^{n-1} a_i + 2a_j + 4a_k = \sum_{i,j,k=0}^{n-1} 7a_i = \sum_{i=0}^{n-1} n^27a_i$ And we have $ \sum_{i=0}^{n-1} n^27a_i = \frac{n^3(n^3-1)}{2}$ So $ \sum_{i=0}^{2009-1} n^27a_i - \sum_{i=0}^{2008-1} n^27a_i = \frac{2009^3(2009^3-1)}{2}-\frac{2008^3(2008^3-1)}{2}$. On the other hand $ \sum_{i=0}^{2009-1} n^27a_i - \sum_{i=0}^{2008-1} n^27a_i = 2008^2*7*a_{2008}$ So $ a_{2008}= \frac{\frac{2009^3(2009^3-1)}{2}-\frac{2008^3(2008^3-1)}{2}}{2008^2*7}$. I have a fealing that i've made a mistake somewhere..

Mathias_DK wrote: $ \sum_{i,j,k = 0}^{n - 1} a_i + 2a_j + 4a_k$ is the sum of the first $ n^3$ numbers. I cannot understand this part..

gks921217 wrote: Mathias_DK wrote: $ \sum_{i,j,k = 0}^{n - 1} a_i + 2a_j + 4a_k$ is the sum of the first $ n^3$ numbers. I cannot understand this part.. I don't really understand it either, because it is totally wrong Sorry

A good warm-up problem for studying formal series! Let us define the formal series $f(z)$ as $$f(z) := \sum_{i \ge 0} z^{a_i}$$and observe that this formal series is defined at all values $0<z<1$ of the variable. The given relation is equivalent to $$f(z)\cdot f(z^2)\cdot f(z^4)=\sum_{i \ge 0} z^i=\frac{1}{1-z}.$$Replacing $z$ by $z^2$ reveals that $f(z)=(1+z)f(z^8)$ and we conclude that the formal series $f$ is given by $$f(z)=\prod_{k \ge 0} \left(1+z^{8^k}\right)$$Thus, $a_n$ is the $n$ the natural number with digits only $0,1$ when written in base $8$. We conclude that $a_{1998}=\sum a_i8^i$ where $1998=\sum a_i2^i$, as the desired value.

Claim: If $n$ has the binary representation of $\sum_{i\geq 0} e_i\cdot 2^{i}$. Then we have that \[a_n = \sum_{i\geq 0} e_i\cdot 8^{i}\] Proof: The uniqueness is easy to show. For any nonnegative integer $M$, consider its binary representation, and then split up the powers of two into three sets based on the exponent mod 3. $A$ is the sum of those with $\equiv 0 \pmod{3}$, $B$ for $\equiv 1 \pmod{3}$, and $C$ for $\equiv 2 \pmod{3}$. Thus, $M=A+B+C = \text{(sum of powers of 8)}+2\cdot \text{(sum of powers of 8)} + 4\cdot \text{(sum of powers of 8)}$, which is doable with $a_n$, and we clearly cannot express $M$ in any other way. Thus, each $M$ is uniquely expressible in this form. $\square$ Now, note that \[1998 = 11111001110_2 \Longrightarrow a_{1998}=11111001110_8 = 1227096648_{10}\]and we are done.

We claim that the sequence $a_i$ contains precisely the nonnegative integers that contain no digits other than 0 and 1 in base 8. Clearly, this sequence works, since for each nonnegative integer, we essentialy express it in base 8, split each digit into 3 bits, and use those to pick either 0 or 1 in that corresponding location in order to find the bit in that place for $i,j,k$. We will then show that there can only be one possible sequence. Note that 0 must be in the sequence, since 0 must be expressible, so $a_0=0$. For $n\geq 0$, let $T_n$ denote the smallest nonnegative integer that cannot be expressed as $a_i+2a_j+4a_k$ for $0\leq i,j,k\leq n$. Claim: $a_{n+1}=T_n$. Suppose otherwise. Then, if $a_{n+1}<T_n$, by definition of $T_n$ there is some way to express $a_{n+1}$ as $a_i+2a_j+4a_k$ for $0\leq i,j,k\leq n.$ However, we can also express $a_{n+1}$ as $a_{n+1}+2a_0+4a_0$, contradicting uniqueness. However, if $a_{n+1}>T_n$, then since it is an increasing sequence, $a_m>T_n$ for all $m\geq n+1.$ However, consider $T_n$. By definition, it cannot be expressed using just $a_0$ through $a_n$. However, if we use any of $a_m$ for $m\geq n+1$, we would already overshoot the goal of $T_n$, so $T_n$ cannot be expressed in any way, contradiction. Therefore, $a_{n+1}=T_n$. Since $T_n$ is uniquely determined by $a_0$ through $a_n$, by induction, there can only be one possible sequence. Since the earlier sequence works, it must be the sequence. Therefore, the answer is $$8^{10}+8^9+8^8+8^7+8^6+8^3+8^2+8.$$

Darn this generating function trick is becoming way too commonly used. Let $f(x) = \sum_{i \geq 0} a_i x^i$. Notice that $f(0) = 0$. Note that the condition is equivalent to $$f(x)f(x^2)f(x^4) = \frac 1{1-x}.$$On the other hand, combining this with $f(x^2)f(x^4)f(x^8) = \frac 1{1-x^2}$, we have $\frac{f(x)}{f(x^8)} = (1+x)$, so thus the infinite product $$\frac{f(x)}{(1+x)(1+x^8)(1+x^{64})\cdots} = f(x^{8^n}) \to f(0) = 1,$$and thus $\{a_n\}$ can be characterized as the sequence of numbers expressible as the sum of powers of $8$. The rest is extraction.

I claim that the only sequence that works is the nonnegative integers that only have $0$s and $1$s in their base $8$ representation. Obviously this works, so we will prove that this is the only possible sequence. First, note that $0$ has to be in the sequence to generate $0$ and $1$ has to be in the sequence to generate $1$. Claim. The next element in the sequence is always the least nonnegative integer that cannot be formed yet. Proof. If the next element is any smaller, it can be formed, then $a_k+2(0)+4(0)=a_k$, bad. If the next element is any larger, than that least nonnegative integer will never be formed, bad. Now we will prove that the next element in the sequence is always the next nonnegative integer with only $0$s and $1$s in its base $8$ representation. Claim. Given the first some amount of terms in the sequence, you are guaranteed to be able to form any number such that if it was written in base $8$ and each nonzero digit was replaced with a $1$, you have it in your sequence. Proof. This is just taking the binary representation of each base $8$ digit. Note that replacing any of the $1$s with a $0$ still keeps you in the part of the sequence you have. Now simply note that any nonnegative integer with only $0$s and $1$s in its base $8$ representation can only be formed by $a_i+2(0)+4(0)$, because the base $8$ addition cannot carry. But this means that the next nonnegative integer with only $0$s and $1$s in its base $8$ representation cannot be formed with the current sequence, and thus must be appended to the sequence. $\blacksquare$ The rest is extraction: $1998_{(10)}=11111001110_{2}$, so the answer is $\boxed{11111001110_{8}}$.

We claim that the sequence is just all numbers whose base $2$ representation contains only $1$s in spots whose place value is a power of $8$, that is, every third digit with the units digit being counted. Thus, the answer would simply be $1998$ written in base $2$ but parsed in base $8$. Clearly, this works, since every digit of any nonnegative integer's base two representation can be split into three classes, the first class being every digit of place value $8^k$, the second being every digit of place value $2\cdot 8^k$ and the third being every digit of place value $4\cdot 8^k$ and the number formed only using digit first class is $a_{i}$, the number formed by the second class is $2a_{j}$ and the third class forms $4a_{k}$. Now, to prove this is the only sequence: note that $0$ must be in the sequence. Suppose we have already constructed some of the sequence in increasing order, then the next term cannot be something already representable as $a_i+2a_j+4a_k$, otherwise the representation isn't unique. If the next term of the sequence is at least two greater than anything already representable, then the number one greater than anything already representation is never going to be representable. Thus, the next term is fixed and thus is the sequence.

We claim that $a_n$ is the $n+1$th smallest base $8$ number made of $1$'s and $0$'s We use induction on the first $2^x$ terms. We claim by induction that the first $2^x$ terms can uniquely express the first $8^x - 1$ integers. Our base case is trivial. Now for the inductive step. Assume the result for $n-1$. Now looking at the last $n-1$ digits of our numbers we can see that each of the $2^{n-1}$ possibilities are expressed $2$ ways: one with a $1$ at the beginning and one without. Since we know that these digits can be combined to form any number from $0$ to $8^{n-1} - 1$ we simply need those $1$'s at the end to form the multiples of $8^{n-1}$ up to $7 \cdot 8^{n-1}$. This is obviously possible. Translating $1998$ we see that $a_{1998} = \boxed{11111001110_8}$. $\blacksquare$ Cute problem

Let $f(x)=\sum_{n=0}^\infty x^{a_n}$. Then, $f(x)f(x^2)f(x^4)=\sum_{n=0}^\infty x^n=\frac1{1-x}$ so $f(x^2)f(x^4)f(x^8)=\frac1{1-x^2}$ so $f(x)=(1+x)f(x^8)$. This implies that if $x^n$ is a term in $f(x)$, then $x^{8n}$ is a term in $f(x^8)$, so $x^{8n}$ and $x^{8n+1}$ must both be terms in $f(x)$. This means that the $a_i$ are the numbers in base $8$ with all digits $0$ or $1$. Since $1998=11111001110_2$, $a_{1998}=11111001110_8=\boxed{1227096648}$.

Notice that the first two terms must be 0 and 1, and each subsequent term is the least integer which cannot be expressed as the desired linear combination of the previous terms. Hence our sequence is unique, so proving that the sequence of integers with only 0s and 1s in base 8 works will suffice. The integers in this sequence have the property that the 1s in its binary representation are spaced out by multiples of 3. The coefficients of 2 and 4 are equivalent to concatenating 0 and 00 to the binary representations of $a_j$ and $a_k$, respectively. Thus the $0 \pmod 3$ bits determine $a_i$, the $1 \pmod 3$ bits determine $a_j$, and the $2 \pmod 3$ bits determine $a_k$, so our representation is attainable and unique. Consequently, since $1998 = 1111101110_2$, we have $a_{1998} = 1111101110_8$. $\blacksquare$

Let $f(x) = x^{a_0} + x^{a_1} + \dots$, the condition easily implies \[f(x)f(x^2)f(x^4) = 1 + x + x^2 + \dots = \dfrac{1}{1 - x} \implies \dfrac{f(x)}{f(x^8)} = \dfrac{f(x)f(x^2)f(x^4)}{f(x^2)f(x^4)f(x^8)} = \dfrac{1 - x^2}{1 - x} = 1 + x.\]Therefore, we have the telescoping series \[f(x) = \dfrac{f(x)}{f(x^8)} \cdot \dfrac{f(x^8)}{f(x^{8^2})} \cdot \dfrac{f(x^{8^2})}{f(x^{8^3})} \cdots = (1 + x)(1 + x^8)(1 + x^{8^2}) \cdots \]So $a_{1998}$ denotes the evaluation of the base-$8$ representation of $1998$ in binary. We have \[1998 = 11111001110_2 \implies a_{1998} = 8^{10} + 8^9 + 8^8 + 8^7 + 8^6 + 8^3 + 8^2 + 8^1\]as wanted.

We claim the solution is $a_{1998}=8^1+8^2+8^3+8^6+8^7+8^8+8^9+8^{10}$ The main claim is: $a_{2^n}=7a_{2^n-1}+1$ and $a_{2^n+k}=a_{2^n}+a_k$ with $(1\leq k<2^n)$. Proof: Clearly $a_0=0$ (if not, we can't get 0), $a_1=1$ (if not we can't get 1). As $1\leq m\leq 7$ can be achieved by using 1 and 0, but not 8, $a_2=8$ and $a_3=9$. We now claim we can get every single number $10\leq m\leq 72$ uniquely. Write $n=8k+r$, with $1\leq k,r\leq 7$ and $k=x_i+2x_j+4x_k$, $r=y_i+2y_j+4y_k$. Now, we perform the following algorithm (which is quite intuitive, so I won't prove it): If $x_n=y_n=1$, choose$a_n=9$ If $x_n=1$, $y_n=0$, choose $a_n=8$ If $x_n=0$, $y_n=1$, choose $a_n=1$ If $x_n=y_n=0$, choose $a_n=0$ Hence, it starts $(0,1,8,9,73,\dots)$. We prove by induction: Suppose it is true until $a_{2^n+k}$ $(k<2^n-1)$. Now clearly we can't get $a_{2^n}+a_{k+1}$, for $a_{2^n}+a_{k+1}=a_{2^n+i}$ (because $7a_{2^n-1}<a_{2^n}\leq a_{2^n+i}$) $+2a_j+4a_k$=$a_{2^n}+a_i+2a_j+4a_k \longleftrightarrow a_{k+1}=a_i+2a_j+4a_k$. Now, for every $a_{2^n+k}+1\leq m\leq a_{2^n}+a_(k+1)-1$, we can get every $a_k+1\leq n\leq a_(k+1)-1$ just using $a_0, a_1, \dots a_k$ by induction hypothesis. Therefore, we select those exact indices for $m$, but choose $a_{2^n+i}$ instead of $a_i$. Finally, we've that it is true for $a_0,a_1, \dots ,a_{2^n+(2^n-1)}$. As we can get $0\leq m\leq 7*a_{2^n-1}$ just using $a_0, a_1, \dots a_{2^n-1}$, we can get all $7*a_{2^n-1}+1\leq n \leq 7*a_{2^n}+7*a_{2^n-1}=7*a_{2^{n+1}-1}$, hence $a_{2^{n+1}}=7a_{2^n}+1$ for $7a_{2^n}+1>7a_{2^n}$. $\square$ It remains to solve the recursion; after some clever algebra we get $a_{2^n}=8^n$ and as $1998=2^1+2^2+2^3+2^6+2^7+2^8+2^9+2^{10}$, we get $a_{1998}=8^1+8^2+8^3+8^6+8^7+8^8+8^9+8^{10}$.