Has this been proven? ... 10^n + 1
 

Has it been proven that 10^n + 1 is composite for all n > 2 ?
If so, can someone point me to it?

It is composite for n odd, since 11 is a factor. But what about n even?

[QUOTE=monst;111505]Has it been proven that 10^n + 1 is composite for all n > 2 ?
If so, can someone point me to it?

It is composite for n odd, since 11 is a factor. But what about n even?[/QUOTE]
If n has an odd factor m>1, then 10^n + 1 has a non-trivial factor 10^(n/m)+1.
Therefore, the only possibility for 10^n + 1 being prime is n = 2^k (similarly to Fermat primes).

[QUOTE=maxal;111510]If n has an odd factor m>1, then 10^n + 1 has a non-trivial factor 10^(n/m)+1.
Therefore, the only possibility for 10^n + 1 being prime is n = 2^k (similarly to Fermat primes).[/QUOTE]

And as with Fermat primes, we expect that there are only finitely many
primes of the form 10^2^n + 1.

[quote=maxal;111510]If n has an odd factor m>1, then 10^n + 1 has a non-trivial factor 10^(n/m)+1.
Therefore, the only possibility for 10^n + 1 being prime is n = 2^k (similarly to Fermat primes).[/quote]

Thanks for the clarity here. Your response has prompted another question in my mind.

I believe my original post can be genralized a bit to...
For any even base b, b^n + 1 is composite for all n odd, since b + 1 is a factor.

My question is... What generalizations to your response can be made for even bases, b? Do all even bases behave "similar to Fermat primes" as you have proven for b = 10?

Google "Generalized Fermat Numbers" to find more information.

I especially liked the list of factors in Table 1 of Bjorn and Reisel's 1998 paper [URL="http://www.ams.org/mcom/1998-67-221/S0025-5718-98-00891-6/S0025-5718-98-00891-6.pdf"]Factors of Generalized Fermat Numbers[/URL]

[QUOTE=monst;111522]I believe my original post can be genralized a bit to...
For any even base b, b^n + 1 is composite for all n odd, since b + 1 is a factor.[/quote]
This is true for all bases b>1, evenness of b is not required.
[QUOTE=monst;111522]What generalizations to your response can be made for even bases, b?[/QUOTE]
Generalization is straightforward:
If n has an odd factor m>1, then b^n + 1 has a non-trivial factor b^(n/m)+1.
In particular, for odd n we can take m=n and obtain the property you mentioned.

[QUOTE=R.D. Silverman;111518]And as with Fermat primes, we expect that there are only finitely many primes of the form 10^2^n + 1.[/QUOTE]

And since the 10[sup]2[sup]n[/sup][/sup]+1 grow much faster with n than the 2[sup]2[sup]n[/sup][/sup]+1, we heuristically expect fewer primes below any bound n.

By way of example:

2[sup]2[sup]n[/sup][/sup]+1 is prime for n=0,1,2,3,4 and likely for no other known values [and certainly not for n < 33];

10[sup]2[sup]n[/sup][/sup]+1 is prime for n=0,1 and for no other values n < 13. [As high as I tested using PARI just now - there is likely a larger known bound]

[QUOTE=ewmayer;111528]And since the 10[sup]2[sup]n[/sup][/sup]+1 grow much faster with n than the 2[sup]2[sup]n[/sup][/sup]+1, we heuristically expect fewer primes below any bound n.[/QUOTE]

Of course, some numbers scoff at heuristics. 2072005925466[sup]2[sup]n[/sup][/sup]+1 is prime for n = 0,1,2,3,4,5,6. It's the smallest such base and was computed for [url]http://primepuzzles.net/puzzles/puzz_399.htm[/url].

[QUOTE=Jens K Andersen;111547]Of course, some numbers scoff at heuristics.[/QUOTE]

"I am Hassan, the rebellious data point ... I scoff at your means and probability distribution functions. I and my fellow rebel outliers wage jihad against the 95%-confidence-interval infidel crusaders. The streets shall flow with the blood of the 3-SD jackals and their lackeys! All praise be unto Allah, the Unstatistical."

[quote=ewmayer;111580]"I am Hassan, the rebellious data point ... I scoff at your means and probability distribution functions. I and my fellow rebel outliers wage jihad against the 95%-confidence-interval infidel crusaders. [/quote]

on that token, what's the practical use of knowing a sequence is finite if one does not know anything about the last term?
e.g. suppose we know that Fermat primes are finite, but the next and last one is [COLOR=#550055]2072005925466 or larger than [/COLOR][COLOR=#000000]2,365,100,000,000 (cf [URL="http://www.research.att.com/~njas/sequences/A090875"][COLOR=#810081]A090875[/COLOR][/URL]) or 10^10^7 ? and/or, to what extend can heuristics which tell us that a sequence is "most probably" finite, also tell us something about the magnitude of the last term ?[/COLOR]

[QUOTE=m_f_h;111652] and/or, to what extend can heuristics which tell us that a sequence is "most probably" finite, also tell us something about the magnitude of the last term ?[/COLOR][/QUOTE]

Generally speaking, they can't.

Your question strikes at the difference between existence proofs and
constructive proofs. Or, (say) that knowing a diophantine equation
has finitely many solutions, but not knowing a bound on them. Or
knowing that a set is infinite but being unable to exhibit one of its
elements or ....... any of a number of similar situations.

Alan Baker's work on linear forms in logarithms can be useful, but it
isn't always applicable.

A striking example is the Catalan Conjecture. Before Preda Mihailescu :bow:
finished his (very elegant) proof, we knew that there were at most
finitely many solutions. And we had a bound. But the bound was beyond
computer range. Then Preda found a connection to the Wieferich congruence
and this brought the problem to a point where the computation became
possible (but very large). Then he found a proof that avoided the computations. (APPLAUSE!)

Another example: We know that almost all real numbers are Transcendental.
The subset that is algebraic is countable, while the reals are uncountable.
Thus, the algebraic numbers have density 0 in the reals. But knowing that
almost all numbers are transcendental does not help us prove that e.g.
The Euler-Mascheroni constant is.

[QUOTE=R.D. Silverman;111658]
Another example: We know that almost all real numbers are Transcendental.
The subset that is algebraic is countable, while the reals are uncountable.
Thus, the algebraic numbers have density 0 in the reals. But knowing that
almost all numbers are transcendental does not help us prove that e.g.
The Euler-Mascheroni constant is.[/QUOTE]Even worse: almost all numbers are not computable by a Turing machine but, on the C-T hypothesis, we can't give even a single example!

Paul

[QUOTE=xilman;111663]Even worse: almost all numbers are not computable by a Turing machine but, on the C-T hypothesis, we can't give even a single example!

Paul[/QUOTE]

Sure we can. One such example is:

For a given finite state machine, what is the probability that a random input
tape will halt?

[QUOTE=R.D. Silverman;111664]For a given finite state machine, what is the probability that a random input
tape will halt?[/QUOTE]

Your Turing machine still uses a tape drive?!! You should consider upgrading.

[Fry's has specials on TMs nearly every week, you just need to be careful to read the fine print, send any rebate form in promptly, and make sure to save a copy of the latter in case it gets "lost" in the mail, as rebate forms appear to be distressingly prone to doing, similarly to insurance claim forms.]

[QUOTE=R.D. Silverman;111664]Sure we can. One such example is:

For a given finite state machine, what is the probability that a random input
tape will halt?[/QUOTE]Fair enough --- my statement was too sloppily phrased and should not have used "give". A more accurate verb would be "compute".

Even this statement needs tightening up a little. For instance, e is transcendental but we can compute it to an arbitrary but fixed precision and do so efficiently. Non-computable numbers are, by definition, non-computable.

Paul

[QUOTE=ewmayer;111672]Your Turing machine still uses a tape drive?!! You should consider upgrading.

[Fry's has specials on TMs nearly every week, you just need to be careful to read the fine print, send any rebate form in promptly, and make sure to save a copy of the latter in case it gets "lost" in the mail, as rebate forms appear to be distressingly prone to doing, similarly to insurance claim forms.][/QUOTE]

This is terrific! What is the price on a standard NDTM??? I'd like to buy one.

[QUOTE=xilman;111663]Even worse: almost all numbers are not computable by a Turing machine but, on the C-T hypothesis, we can't give even a single example!

Paul[/QUOTE]

Even weirder is the fact that if we work outside of the system, there can be an 'equal' number of non-computable numbers as there are computable ones. In other words, there is a countable model for the (standard) reals. And, of course, one could just work with the "computable" reals in the first place depending on which model one favors. :smile: