# 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
6 years, 11 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. 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 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> 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?

- 6 years, 11 months ago

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

Staff - 6 years, 4 months ago