Let $a_{1}, a_{2}, a_{3}, \cdots$ be an increasing sequence of nonnegative integers such that every nonnegative integer can be expressed uniquely in the form $a_{i}+2a_{j}+4a_{k}$, where $i, j, $ and $k$ are not necessarily distinct. Determine $a_{1998}$.
Problem
Source:
Tags: Additive Number Theory
21.10.2007 13:04
Peter wrote: Let $ a_{1}, a_{2}, a_{3}, \cdots$ be an increasing sequence of nonnegative integers such that every nonnegative integer can be expressed uniquely in the form $ a_{i} + 2a_{j} + 4a_{k}$, where $ i, j,$ and $ k$ are not necessarily distinct. Determine $ a_{1998}$. http://www.kalva.demon.co.uk/short/soln/sh98n8.html
20.11.2014 00:57
Looks like the link doesn't work anymore. Here is link to solutions: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=124444&sid=53ca20003f1933fab8dd8d504d27aeee#p124444
22.02.2023 17:25
Since neither of the above links work anymore, here is a quick explanation of the solution: $a_i$ is the $i$-th smallest non-negative integer that can be written as a (possibly empty) sum of distinct powers of $8$. By writing a non-negative $n$ integer in base $8$, you can figure out what $a_i, a_j, a_k$ need to be in order for $a_i + 2a_j + 4a_k$ to be equal to $n$. For example, if a certain digit of $n$ in base $8$ is $5$, then you need both $a_i$ and $a_k$ to have that power of $8$ in their sum. You should be able to convince yourself that this shows both existence and uniqueness. To actually figure out what $a_m$ is for $m \ge 1$, one can write $m-1$ in binary as, say, $m-1 = \sum_{i \in S} 2^i$, for a certain set of integers $S$. Then $a_m = \sum_{i \in S} 8^{i}$. As $1998 = 2^1 + 2^2 + 2^3 + 2^6 + 2^7 + 2^8 + 2^9 + 2^{10}$, we get $a_m = 8^1 + 8^2 + 8^3 + 8^6 + 8^7 + 8^8 + 8^9 + 8^{10}= 1227096648$.