Paul Michael Kielstra

I’m teaching Math 1A, single-variable calculus, right now. The following problem and solution are for those of my students who found the Intermediate Value Theorem interesting. The problem I got from an entrance test for a university I applied to, which I’m keeping secret in case they still use this question; the solution is my own.

Problem: Recall that \(x!\) is \((x)(x-1)(x-2)\cdots(2)(1)\). Prove that none of \(1000!+2, \dots, 1000!+1000\) are prime. Prove that there exist 999 consecutive numbers (that is to say, a list of numbers of the form \(a, a+1, \dots, a+998\) for some \(a\)) of which exactly ten are prime.

Solution: For the first part, consider a general \(1000!+x\) for \(2 \leq x \leq 1000\). Then \(1000!\) is divisible by \(x\) (can you see why?) so \(1000!+x\) must be divisible by \(x\) as well. But, since \(x>1\) , \(1000!+x\) can’t be prime.

This gives us a list of 999 consecutive numbers that doesn’t have any primes at all. Note now that we aren’t asked to find an exact list of 999 consecutive numbers that have ten primes among them; we’re just asked to prove that such a list exists. The Intermediate Value Theorem has shown itself to be a powerful tool in proving things of this sort, so let’s see if we can apply something a little bit like it here.

Define the function \(f(x)\) to be the number of primes between \(x+2\) and \(x+1000\), inclusive. We’ve just proved that \(f(1000!)=0\). Furthermore, we know that \(f(0)\) is pretty large. There are loads of primes between \(2\) and \(1000\). There are, in fact, \(168\), but that’s not particularly important. We can fairly quickly find ten primes in that interval, so we know that \(f(0)>10\).

We do have a problem, in that \(f(0)\) isn’t exactly continuous in any standard sense of the word. In fact, its domain really only includes integers. (You could extend it to real numbers, but then it would have jumps in it, and then we couldn’t apply IVT.) So let’s instead try to come up with a definition of “continuity” that works for functions that are just defined on integers. We’ll say that a function \(f\) is integer-continuous if \(|f(x)-f(x+1)|\leq 1\). That is to say, whenever \(x\) changes by at most \(1\), \(f(x)\) also changes by at most \(1\).

Important note: “Integer-continuous” is terminology that I just made up. Don’t use it in tests.

Is our prime-counting function \(f(x)\) integr-continuous? As it happens, yes. Let’s see what happens when we go from counting primes in \([x+2, x+1000]\) to counting primes in \([x+3, x+1001]\). Most of the numbers in that interval remain the same, and are counted the same way. However, we lose one number at the start and we gain one number at the end. There are four possibilities:

• Lose a prime, gain a prime: \(f(x)=f(x+1)\)

• Lose a prime, gain a non-prime: \(f(x)=f(x+1)+1\)

• Lose a non-prime, gain a prime: \(f(x)=f(x+1)-1\)

• Lose a non-prime, gain a non-prime: \(f(x)=f(x+1)\)

In all these cases, the difference beween \(f(x)\) and \(f(x+1)\) is at most \(1\), so \(f\) must be integer-continuous.

We just need one more piece of the puzzle. Recall that the Intermediate Value Theorem states that, for a continuous function \(g\), for any value \(q\) between \(g(a)\) and \(g(b)\), there exists some \(c\) between \(a\) and \(b\) such that \(g(c)=q\). We can get a similar theorem for integer-continuous functions. Let’s say that \(g\) is integer-continuous. Then, because at every step the value of \(g(x)\) can change by at most \(1\), we must hit every integer value between \(g(a)\) and \(g(b)\) on our way from \(x=a\) to \(x=b\).

To return to our prime-counting function \(f\), we know that \(f(0) > 10\) and \(f(1000!) = 0\). Therefore, on the way from \(0\) to \(1000!\), we must reach some \(x\) such that \(f(x)\) is exactly \(10\). That’s the proof!

The moral of the story: pay attention to the methods and ways of thinking you meet in math class just as much as to the theorems and results themselves. The former are useful in far more ways than the latter, and the same patterns show up in lots of different areas.

If you’re interested, I ran a computer search to try to find some actual values of \(x\) such that \(f(x)=10\). They’re pretty large. Between \(1\) and \(10000\), \(f(x)\) is always bigger than \(101\). So, I resorted to plugging in random big numbers and hoping to get lucky, and in the end I found that \(x = 9 \times 10^{32}+10038\) gives exactly \(f(x)=10\). It’s probably not the smallest number that works, but I honestly don’t particularly care. \(9 \times 10^{32} + 10038\) is a perfectly good number, it’s far smaller than \(1000!\) (which is approximately \(4 \times 10^{2567}\)), and I don’t think that there are many numbers much smaller than it that will do the job, so as far as answers go I’m happy with this one.