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

[QUOTE=Another Primate]
If you add nine to 10 to the nth power (where n is a positive integer), with the result always be a prime number?
[/QUOTE]

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

[QUOTE=Giles]
The full prime factorisation of 100009 is 7 * 13 * 1099.

[/QUOTE]

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

21649 * 513239

[QUOTE=Alive At Both Ends]
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.
[/QUOTE]

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.

[QUOTE=Malacandra]
Or would be if 1099 were prime, instead of being 7 * 157. :stuck_out_tongue:
[/QUOTE]

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)!

[QUOTE=ultrafilter]
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.
[/QUOTE]

Could we get a cite on that?

[QUOTE=Alive At Both Ends]
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.
[/QUOTE]
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.

[QUOTE=SmackFu]
1^n + 2
[/QUOTE]

I meant, apart from obviously trivial formulae like that.

[QUOTE=ultrafilter]
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.
[/QUOTE]

Interesting. What is it?

[QUOTE=Giles]
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)!
[/QUOTE]

rexx is my friend. You want anything less than about 10[sup]15[/sup] factorised, step right up. :smiley:

Not to mention that 10^0 + 9 = 10, which is 2 * 5.

[QUOTE=ultrafilter]
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.
[/QUOTE]

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

[QUOTE=SaintCad]
f(n) = x^(3^n)
Look up Mills’ Constant
[/QUOTE]

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.

[QUOTE=Dervorin]
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?
[/QUOTE]

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.

[QUOTE=Alive At Both Ends]
Interesting. What is it?
[/QUOTE]

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.