Applications of Bases: Part II - 2014 AIME II #15

First, before I begin, I'd like to say WOW, was I surprised by the reaction. I haven't been posting anything new (part II) because I've been looking/drained of good problems to add. I was totally in for a surprise on this year's AIME II.

First, the problem.

For any integer $k\ge 1$, let $p(k)$ be the smallest prime which does not divide k. Define the integer function $X(k)$ to be the product of all primes less than $p(k)$ if $p(k)>2$, and $X(k)=1$ if $p(k)=2$. Let $\{x_n\}$ be the sequence defined by $x_0=1$, and $x_{n+1}X(x_n)=x_n p(x_n)$ for $n\ge 0$. Find the smallest positive integer $t$ such that $x_t=2090$.

So, let's go through my thinking process seeing this on the test. At first, I did not see the trick, but it seemed like the kind of problem with a trick. So, what better than compute a few values. Around 10 minutes later (and with a good deal of errors having been made), I had finally obtained the following:

$x_0=1,~ x_1=2, ~ x_2=3, ~ x_3=6, ~ x_4=5$

Just looking at that, I wasn't totally sure I saw any pattern. But I did see that there was one, just not an immediately obvious one.

So, I started factorizing. I knew that this was a question about prime factorization simply because we were multiplying and dividing by products of primes constantly.

Here's the important part, though, which saved me quite a bit of time and is why I am posting this to Applications of Bases. I was kind of lazy. I wrote 1 instead of $2^1$, 31 instead of $3^3\cdot 2^1$, 1000 instead of $7^1$, etc. In other words, I wrote the number $n=(p_k^{e_k})\cdot \ldots \cdot (p_1^{e_1})$ as $e_k e_{k-1}\ldots e_1$ where $p_k$ is the $k$ - th prime.

Now, I went back to our sequence.

$x_0=0, ~ x_1=1, ~ x_2=10, ~x_3=11, ~ x_4=100$

By that point, I needed little confirmation that this was a strange kind of binary, so I rushed off, found that 2090 was 10010101, and converted to get $\boxed{t=149}$.

Yup, 149 was right. But let's prove it, shall we? (I actually did prove it in my head on the test. It wasn't too hard to see.)

First, we get $x_{n+1}=\frac{x_n p(x_n)}{X(x_n)}$. Let $x_n$ be something ending in 011....1 (there could be 0 1s). Then, when we multiply by $p(x_n)$, we turn this ending into 111...1. Finally, when we divide by $X(x_n)$, we turn this into 100...0. But, since this is just how we count up in binary, we conclude that $x_n=n+k$ for some k. Since $x_0=0$, we see that $k=0$, and the proof is complete.