Tag Archives: large numbers

Generating Primes with Formulas

Algebra, Number Theory, Proofs, , , ,

Prime numbers—namely, positive integers with no divisors other than 1 and themselves—have long fascinated mathematicians. As a result, there have been many attempts at formulas to generate prime numbers. For example, the polynomial \(x^2-x+41\) spits out a prime number for \(x = 0, 1, 2, …, 40\). But for \(x = 41\), the value is \(41^2\), which is not prime. Can we find some nonconstant polynomial \(f(x)\) with integer coefficients that only spits out prime values? (The constant polynomial \(f(x) = 2\) always returns a prime, but this is not very interesting.) In a word: No. There is no such polynomial. To prove this, assume \(f\) is such a polynomial. Then \(f(0) = p\) for some prime \(p\), and all of the numbers \(\{f(p), f(2p), f(3p), \ldots \}\) are divisible by \(p\). This sequence grows toward infinity, so one of them is greater than \(p\). Since this number has a factor of \(p\), it is not prime.

What if we switch from polynomials to exponents? Maybe the function \(2^m + 1\) will give us lots of primes. It can be shown that if \(2^m + 1\) is prime then \(m\) itself has to be a power of 2. (Indeed, if a prime \(p > 2\) divides \(m\), check that \(2^{m/p} + 1\) divides \(2^m + 1\).) So the only possibilities are the numbers \(F_n = 2^{2^n} + 1\), which are called Fermat numbers. The first few are $$\begin{align*}
F_0 &= 3,\\
F_1 &= 5,\\
F_2 &= 17,\\
F_3 &= 257,\\
F_4 &= 65537.
\end{align*}$$ It was long believed that all Fermat numbers were prime (Fermat himself conjectured this!), but in fact the very next one, \(F_5 = 4294967297 = 641 \cdot 6700417\), is composite. (In Fermat’s defense, this is a large number to factor by hand!) Are there at least infinitely many Fermat primes? We currently don’t know. In fact, the Fermat primes shown above are the only known Fermat primes!

Similarly, numbers of the form \(2^n-1\) are called Mersenne numbers. In order for this to be prime, it is necessary for \(n\) itself to be prime. (Indeed, if \(a\) divides \(n\) then \(2^a-1\) divides \(2^n-1\).) So is \(2^p-1\) prime for every prime \(p\)? Unfortunately, no: \(2^{11}-1\) is not prime. But there seem to be many Mersenne primes. Thanks to the “Great Internet Mersenne Prime Search,” a.k.a. GIMPS, there are 47 Mersenne primes known, the largest of which is \(2^{43112609}-1\), which has 12978189 digits (in base 10).

OK, so the above “prime-generating” functions don’t work very well. Here’s one that does work. It can be shown that there is some polynomial \(Z(a, b, c, d, e, f, g, h, i, j)\) with 10 variables and integer coefficients such that any positive output from \(Z\) (when given integer inputs) is prime, and furthermore, every prime is obtained in this way. (Note: \(Z\) spits out many non-positive values as well.) Unfortunately, this polynomial \(Z\) is not very practical. For one thing, its degree is about \(38!\). (Yes, I mean 38 factorial.)

“Read Backwards” Month

Games/Experiments, Number Theory, , , ,

There are quite a few beautifully symmetric dates that present themselves this month, including 11/1/11, 11/02/2011, 11/05/2011 (use a mirror!), 11/11/11, and 11/22/11. In honor of this phenomenon, I want to say a few words about palindromes, which are simply things that read the same backwards as forwards. A few famous examples include “racecar,” “Never odd or even,” “I prefer pi”, “Dr. Awkward”, “Aibohphobia” (which means fear of palindromes [I didn’t make this up!]), “Go hang a salami; I’m a lasagna hog!”, or if you read by word instead of by letter, “Blessed are they that believe that they are blessed.”

If we consider digits instead of letters or words, then numbers such as 676, 100020001, and 12345678987654321 are palindromes. These are in fact quite special palindromes, as they are all squares of integers: \(26^2 = 676\), \(111111111^2 = 12345678987654321\), and \(10001^2 = 100020001\). Are there infinitely many palindromic squares? Yes: the last example above hints that \(10\ldots01^2 = 10\ldots020\ldots01\) for however many 0s you put in the middle. By contrast, if we ask for \(n^5\) to be palindromic (or any higher power), then no solutions are currently known!

You might ask for other types of palindromic numbers, such as palindromic primes. A few examples include 7 (this is a palindrome!), 101, 19391, and 1000000008000000001. Are there infinitely many? We don’t know. But the largest palindromic prime currently known is \(10^{200000} + 47960506974 \cdot 10^{99995} + 1\), according to Wikipedia.

For one more game, here’s a way to make palindromes out of non-palindromes. Start with a non-palindrome, like 86, and keep adding it to its reversal until you get a palindrome: e.g., 86+68 = 154, 154+451 = 605, and 605+506 = 1111, which is a palindrome. How quickly will this terminate? Well, try starting with 89 and see how long it takes! (Answer: it finally stops at a 13-digit palindrome.) But surely it always terminates eventually, right? Surprisingly, the answer to this question is currently unknown. In fact, it is unknown if the sequence starting at 196 ever finds a palindrome!

Finally, if you still want more to think about, try repeating this entire discussion in another base, e.g. base 2. Good luck!