# Prime Number Question: 10^n plus 9

**URL:** <https://boards.straightdope.com/t/prime-number-question-10-n-plus-9/362342>\
**Category:** Factual Questions\
**Created:** [June 27, 2006, 1:24pm UTC](https://boards.straightdope.com/t/prime-number-question-10-n-plus-9/362342 "2006-06-27T13:24:43Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![Another\_Primate](https://avatars.discourse-cdn.com/v4/letter/a/f19dbf/32.png) [@Another\_Primate](https://boards.straightdope.com/u/Another_Primate)\
**Post date:** [June 27, 2006, 1:24pm UTC](https://boards.straightdope.com/t/prime-number-question-10-n-plus-9/362342/1 "2006-06-27T13:24:43Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Crimmsy](https://avatars.discourse-cdn.com/v4/letter/c/c89c15/32.png) [@Crimmsy](https://boards.straightdope.com/u/Crimmsy)\
**Post date:** [June 27, 2006, 1:41pm UTC](https://boards.straightdope.com/t/prime-number-question-10-n-plus-9/362342/2 "2006-06-27T13:41:10Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Giles](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/giles/32/60_2.png) [@Giles](https://boards.straightdope.com/u/Giles)\
**Post date:** [June 27, 2006, 1:41pm UTC](https://boards.straightdope.com/t/prime-number-question-10-n-plus-9/362342/3 "2006-06-27T13:41:34Z")

</div>

No: 100009 = 14287 \* 7

---

<div class="post-metadata">

**Author:** ![Dervorin](https://avatars.discourse-cdn.com/v4/letter/d/eb8c5e/32.png) [@Dervorin](https://boards.straightdope.com/u/Dervorin)\
**Post date:** [June 27, 2006, 1:45pm UTC](https://boards.straightdope.com/t/prime-number-question-10-n-plus-9/362342/4 "2006-06-27T13:45:10Z")

</div>

[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?

---

<div class="post-metadata">

**Author:** ![Giles](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/giles/32/60_2.png) [@Giles](https://boards.straightdope.com/u/Giles)\
**Post date:** [June 27, 2006, 1:47pm UTC](https://boards.straightdope.com/t/prime-number-question-10-n-plus-9/362342/5 "2006-06-27T13:47:13Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Alive\_At\_Both\_Ends](https://avatars.discourse-cdn.com/v4/letter/a/73ab20/32.png) [@Alive\_At\_Both\_Ends](https://boards.straightdope.com/u/Alive_At_Both_Ends)\
**Post date:** [June 27, 2006, 2:13pm UTC](https://boards.straightdope.com/t/prime-number-question-10-n-plus-9/362342/6 "2006-06-27T14:13:17Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![SmackFu](https://avatars.discourse-cdn.com/v4/letter/s/53a042/32.png) [@SmackFu](https://boards.straightdope.com/u/SmackFu)\
**Post date:** [June 27, 2006, 2:35pm UTC](https://boards.straightdope.com/t/prime-number-question-10-n-plus-9/362342/7 "2006-06-27T14:35:50Z")

</div>

1^n + 2

---

<div class="post-metadata">

**Author:** ![Malacandra](https://avatars.discourse-cdn.com/v4/letter/m/45deac/32.png) [@Malacandra](https://boards.straightdope.com/u/Malacandra)\
**Post date:** [June 27, 2006, 2:39pm UTC](https://boards.straightdope.com/t/prime-number-question-10-n-plus-9/362342/8 "2006-06-27T14:39:43Z")

</div>

[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. 😛  
Next up: 11,111,111,111.

21649 \* 513239

---

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [June 27, 2006, 2:48pm UTC](https://boards.straightdope.com/t/prime-number-question-10-n-plus-9/362342/9 "2006-06-27T14:48:00Z")

</div>

[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.

---

<div class="post-metadata">

**Author:** ![Giles](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/giles/32/60_2.png) [@Giles](https://boards.straightdope.com/u/Giles)\
**Post date:** [June 27, 2006, 2:50pm UTC](https://boards.straightdope.com/t/prime-number-question-10-n-plus-9/362342/10 "2006-06-27T14:50:05Z")

</div>

[QUOTE=Malacandra]  
Or would be if 1099 were prime, instead of being 7 \* 157. 😛  
[/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)!

---

<div class="post-metadata">

**Author:** ![Mayo\_Speaks](https://avatars.discourse-cdn.com/v4/letter/m/c57346/32.png) [@Mayo\_Speaks](https://boards.straightdope.com/u/Mayo_Speaks)\
**Post date:** [June 27, 2006, 2:52pm UTC](https://boards.straightdope.com/t/prime-number-question-10-n-plus-9/362342/11 "2006-06-27T14:52:34Z")

</div>

[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?

---

<div class="post-metadata">

**Author:** ![MikeS](https://avatars.discourse-cdn.com/v4/letter/m/919ad9/32.png) [@MikeS](https://boards.straightdope.com/u/MikeS)\
**Post date:** [June 27, 2006, 3:16pm UTC](https://boards.straightdope.com/t/prime-number-question-10-n-plus-9/362342/12 "2006-06-27T15:16:46Z")

</div>

[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](http://en.wikipedia.org/wiki/Formula_for_primes) for the first such formula discovered.

---

<div class="post-metadata">

**Author:** ![Alive\_At\_Both\_Ends](https://avatars.discourse-cdn.com/v4/letter/a/73ab20/32.png) [@Alive\_At\_Both\_Ends](https://boards.straightdope.com/u/Alive_At_Both_Ends)\
**Post date:** [June 27, 2006, 3:23pm UTC](https://boards.straightdope.com/t/prime-number-question-10-n-plus-9/362342/13 "2006-06-27T15:23:38Z")

</div>

[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?

---

<div class="post-metadata">

**Author:** ![Malacandra](https://avatars.discourse-cdn.com/v4/letter/m/45deac/32.png) [@Malacandra](https://boards.straightdope.com/u/Malacandra)\
**Post date:** [June 27, 2006, 3:29pm UTC](https://boards.straightdope.com/t/prime-number-question-10-n-plus-9/362342/14 "2006-06-27T15:29:57Z")

</div>

[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. 😃

---

<div class="post-metadata">

**Author:** ![cmkeller](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/cmkeller/32/118_2.png) [@cmkeller](https://boards.straightdope.com/u/cmkeller)\
**Post date:** [June 27, 2006, 4:05pm UTC](https://boards.straightdope.com/t/prime-number-question-10-n-plus-9/362342/15 "2006-06-27T16:05:01Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Saint\_Cad](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/saint_cad/32/18907_2.png) [@Saint\_Cad](https://boards.straightdope.com/u/Saint_Cad)\
**Post date:** [June 27, 2006, 5:09pm UTC](https://boards.straightdope.com/t/prime-number-question-10-n-plus-9/362342/16 "2006-06-27T17:09:14Z")

</div>

[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

---

<div class="post-metadata">

**Author:** ![Mayo\_Speaks](https://avatars.discourse-cdn.com/v4/letter/m/c57346/32.png) [@Mayo\_Speaks](https://boards.straightdope.com/u/Mayo_Speaks)\
**Post date:** [June 27, 2006, 5:34pm UTC](https://boards.straightdope.com/t/prime-number-question-10-n-plus-9/362342/17 "2006-06-27T17:34:37Z")

</div>

[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.

---

<div class="post-metadata">

**Author:** ![Another\_Primate](https://avatars.discourse-cdn.com/v4/letter/a/f19dbf/32.png) [@Another\_Primate](https://boards.straightdope.com/u/Another_Primate)\
**Post date:** [June 27, 2006, 8:31pm UTC](https://boards.straightdope.com/t/prime-number-question-10-n-plus-9/362342/18 "2006-06-27T20:31:05Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![JSexton](https://avatars.discourse-cdn.com/v4/letter/j/96bed5/32.png) [@JSexton](https://boards.straightdope.com/u/JSexton)\
**Post date:** [June 27, 2006, 8:35pm UTC](https://boards.straightdope.com/t/prime-number-question-10-n-plus-9/362342/19 "2006-06-27T20:35:33Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [June 28, 2006, 3:12am UTC](https://boards.straightdope.com/t/prime-number-question-10-n-plus-9/362342/20 "2006-06-28T03:12:31Z")

</div>

[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.

[Next page](https://boards.straightdope.com/t/prime-number-question-10-n-plus-9/362342.md?page=2)
