# 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.

Note by Matthew Lipman
4 years, 3 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

• bulleted
• list

1. numbered
2. list

1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

> This is a quote
This is a quote
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

Hi, I read your notes and the problem sets but I don't quite understand the third problems wording, can you give some more information on that?

- 4 years, 3 months ago

@Matthew Lipman Can you add this to the Brilliant Wiki under a suitable skill in Number Bases? Thanks!

Staff - 3 years, 9 months ago