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 , let be the smallest prime which does not divide k. Define the integer function to be the product of all primes less than if , and if . Let be the sequence defined by , and for . Find the smallest positive integer such that .
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:
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 , 31 instead of , 1000 instead of , etc. In other words, I wrote the number as where is the - th prime.
Now, I went back to our sequence.
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 .
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 . Let be something ending in 011....1 (there could be 0 1s). Then, when we multiply by , we turn this ending into 111...1. Finally, when we divide by , we turn this into 100...0. But, since this is just how we count up in binary, we conclude that for some k. Since , we see that , and the proof is complete.