As this year comes to a close, people around the world will be counting down the last few seconds of 2012. But, how come we never count up the first few seconds of the new year? What is it about the last few seconds of the year that makes them so special? Maybe it has to do with surviving a Mayan apocalypse, but that was just this year. I guess it always comes down to letting go of the good and of the difficult moments in our past. The champagne helps. Still, I would like to take a moment to pay tribute to the first few seconds of 2013 (the future) with a simple problem and a twist…
The question is simple enough:
What is the longest sequence of consecutive numbers, such that each element of the sequence is a power of a prime number?
You will arrive at the answer soon after asking yourself the question: How often is a number divisible by both 2 and 3? The answer is every 6 numbers (since the number in question has to be divisible by 
Now, here comes the twist…
Challenge: Is there a sequence of 10 consecutive numbers such that none of them is a power of a prime number?
To get the ball rolling, here are the first such sequences with one, two and three elements, respectively: [6], [14,15], [20,21,22].
Super Challenge: Can you find a sequence of 2013 consecutive numbers, such that none of them is a power of a prime number?
Impossible Challenge: Can you solve the first challenge, giving the sequence containing the smallest numbers satisfying the conditions of the problem?
Good luck and enjoy the rest of 2012! Who knows, maybe some genius will solve the above challenges before 2013 rolls around…
Quantum Frontiers 
Dear Spiros, fun challenges! Do you seriously believe that one may sensibly solve the 2013-flavored challenge without any computer help?
The smallest sequence of 10 consecutive non-powers-of-prime is the set {200, 201, … 209}. Is this the solution to the normal challenge or even the “impossible challenge”? Maybe I didn’t understand the latter.
There are 71 consecutive numbers like that whose last, largest one is 31,468. But better sequences suddenly become very rare afterwords! 😉 I doubt it will be easy to find a sequence with 2013 consecutive numbers.
Happy New Year! Lubos
There’s a sequence of 85 consecutive non-prime-powers ending with 156,006. At that point, I decided to quit the super brute force haha.
The brute force – or almost brute force – is arguably needed to find the sequences with the smallest numbers obeying the conditions. But I became sure it must be easy to generate *some* sequences that are arbitrarily long and satisfy the conditions.
Starting from controllable numbers such as products of distinct primes, I think I can get far and solve the super challenge.
Realize that 2011 and 2017 are primes – adjacent primes. It’s helpful to remember all the primes around this year. 😉 Now, take the product P(2011) of all the smallest 305 primes between 2 and 2011. Right above this “crippled factorial”, there should be numbers that can’t be just powers of primes.
I actually believe that if one takes the numbers starting from 1165610607189929661467197053813727272138867498848228171825425578681765988267456263591251622683312123339226959927971229475024708471164178973682667805938657827377535691145389708153775590103527590364540310297825429922630039644734717198493298456278297428526488267653537411305294904255537238309128044845864531400147266775998840666765040996655886390674582930177844589621064347713041268806542978134868688312124681952138462814259377928818310880565544326519825618844764342683851135558625589643111063770244047641743284447037999848902989454060846394621425556201502163102389466926704188574672448170830851112572065402584331948077025927066794804441094109048015299500620814270624280767494274431778770295277102065728247697438963321026800450278685138635987181028574882935128888440883095502623850543524610955833829368882791390305094552385184384050569748361928392864112 and going up to this plus 2014, one obtains a sequence of 2015 numbers that aren’t powers of primes, thus solving the super challenge.
I hope that I multiplied the prime integers correctly, and added two. 😉
It seems to me that you answered your own comment (previous) Lubos. With a great answer indeed. Can you generalize your reasoning to prove that there are arbitrarily long such sequences? Then, the “Supergod” challenge becomes finding the smallest such sequence for each fixed length. I have no idea how to do that…
Thanks, yup, and nope, Spiros. 😉 Arbitrarily long sequences exist because for any prime p, the numbers of the form 2*3*5*…*p + K for K between 2 and q-1 (that generalizes your multiples of 2*3=6) may be nicely factorized (where q is the next prime after p). Either K is a prime, in which case
2*3*5*…*p + K
may be written via the distributive law as K*(something+1) where something+1 is obviously not a power of K equal to K^M because K^M mod P would be equal to 1 for all the primes P between 2,3,5…,p except for K. However, all such numbers (with the specified values of number mod P = 1) have the form 1+2*3*5*…*p (except K) * M for some integer M and already M=1 gives numbers well above my interval’s upper bound. It’s because even the smallest product 2*3*5*…*o where o is the prime before p is greater than the largest prime in the original product, p, and that’s the best case. (In particular, even 2*3 is greater than 5.)
Or, more trivially, K is not a prime in which case
2*3*5*…*p + K
may be written as K*(something) and K already contains at least 2 primes in the prime decomposition, so it’s not a power of a prime. Because arbitrarily large primes p (and especially q) exist, I can make the sequence above arbitrarily long.
I don’t know how to find the sequence of a given length with the minimum size elements and I suspect that no algorithm exists.
Lubos, your answer is close but not quite there yet. For example, 2*3*5+2=32. There is a simple trick to make your answer work. What is it?
Oops, that’s quite a bug! 😉 Thanks for catching it.
I suppose it’s possible to move the whole sequence to somewhat higher numbers, and/or to prove that the number of exceptions (numbers that are powers of prime, at the end) can’t be too high so one may still use some sequences I sketched and/or their parts to get arbitrarily long ones. 🙂
Can’t I just mutate the method in a nearly arbitrary way? For example, take the basic benchmark to be (2*3*5*…*p)^2 instead of just the first power I used before. Then if you add a composite number containing at least two primes in the decomposition, these two primes will still be included in the sum, assuming that they’re smaller than p (or some other function of p or q that still goes to infinity if p goes to infinity). If we add a prime K to it, this prime may be factorized, and the remaining factor can’t be (?? please check again, there was a mistake here before ??) a power of this prime K because it is equal to 1 modulo K, isn’t it? 😉
If the fix above works, I would guess that there are many other fixes as well and the problem is rather easy and the solutions are highly ambiguous.
Bingo. Squaring the product of primes works and is the most elegant solution I have seen so far. Nicely done! And yes, it is quite arbitrary since any higher power of the product will also work [you want every prime at least twice in order to get the +1 remainder in the other factor; p(p*k+1)]. Ambiguity appears in the form of a challenge: What is the formula that allows you to produce the smallest numbers in these sequences? Is there even a closed form?
Cool, Spiros. Concerning the closed form, unless you invent special functions that just produce the right answers ;-), I am willing to bet thousands of dollars that a closed form for the minimal numbers of the sequences doesn’t exist. This looks like a very complex task combining several levels of number theory and even the formula for n-th prime doesn’t exist, does it?
What I am not so sure about is whether there exists a proof that such a closed form of the function doesn’t exist and whether this proof may actually be found by real-world people soon (or is it already known?). 🙂