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.

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

$</code> ... <code>$</code>...<code>."> Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in $</span> ... <span>$ or $</span> ... <span>$ to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestHi, 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?

Log in to reply

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

Log in to reply