 # Prime Number Question: 10^n plus 9

If you add nine to 10 to the nth power (where n is a positive integer), with the result always be a prime number?

No: 10^5 + 9 is divisible by 7.

No: 100009 = 14287 * 7

Nope; 100009 isn’t prime, sadly, although 109 and 1009 both are. Often patterns in prime numbers don’t last - a famous one was 2^(2^n) + 1, which was thought to be prime for all n, and it’s true for 1, 2, 3 and 4, but not for 5 (4294967297 is composite).

Did you have any reasons for thinking that 10^n + 9 would always be prime?

The full prime factorisation of 100009 is 7 * 13 * 1099.

And every number of the form 10^(5+6n) + 9 is going to be divisible by 7 and 13, so there is an infinite number of counter-examples.

In fact, there is no known formula that yields only primes, and I think most mathematicians believe none will ever be found. I don’t know if it’s been proved impossible, though.

1^n + 2

Or would be if 1099 were prime, instead of being 7 * 157. Next up: 11,111,111,111.

21649 * 513239

There’s a very short formula that gives the next prime not smaller than a given n, but it’s not a polynomial like most conjectured prime formulas are.

Thanks! I really should remember to check prime factors a second time, especially when the test is not an easy one (as it is for 2, 3 and 5)!

Could we get a cite on that?

Well, there are polynomial formulas whose positive outputs are all prime. You have to ignore the negative ones, though. See the Wikipedia page for the first such formula discovered.

I meant, apart from obviously trivial formulae like that.

Interesting. What is it?

rexx is my friend. You want anything less than about 10[sup]15[/sup] factorised, step right up. Not to mention that 10^0 + 9 = 10, which is 2 * 5.

f(n) = x^(3^n)
Look up Mills’ Constant

That should say “f(n) = floor(x^(3^n))” where x is a constant.
But Mills’ Constant can (so far, at least) only be calculated by finding prime numbers, so is no use in discovering new ones. It’s still damn interesting, but not really useful.

I didn’t think it was, but a very smart relative of mine said that it was, and was asking me “why is that”… so it kind of convinced me that it was! And I knew that I was definitely not capable of explaining Why it Was, if it, in fact, was… and wish I’d spent some more time just coming up with examples of Why it Wasn’t, before I posted this. Hmm. But the replies are so interesting that I am happy with the error. Thanks!

That idea sounds familiar to me. I think it may have appeared in a Robert J. Sawyer book…possibly Factoring Humanity.

Basically, it comes down to the fact that every Turing machine can be expressed as a function. What you do is you take the Turing machine that computes the next prime after an integer, and write it as a function. The actual formula is basically “the smallest integer greater than x with only two divisors”, only in symbols.