I’ve always had a problem with Goldbach Conjecture in that it puts a strict lower bound on the number of primes less than N (let’s call that p(N)) for any given N. Goldbach Conjecture implies that p(N) >= sqrt(N) for any N. I know there are other strict lower bounds on the frequency of occurence of primes, but this one just seems a little too convinient. Makes me suspicious. Did I mess something up or do I just have to accept that?
groman. I am curious as to how you got from Goldbach’s to the stated lower bound. I am only aware of how the Prime Number Theorem suggests the possibility that GT might be true, which is the other way around of course. Link.
(And at least we can turn this thread into something useful for a bit.)
Suppose N>1. There are N even numbers between 4 and 2(N+1) inclusive; if Goldbach’s Conjecture holds, then each of these corresponds to a sum of two primes between 2 and 2N (and hence to at least one unordered pair chosen from the p(2N) such primes).
The number of distinct unordered pairs of p elements is p(p+1)/2, so we have p(2N)(p(2N)+1)/2 >= N and p(2N) >= sqrt(2N+1/4)-1/2, slightly weaker than groman’s quoted result (giving a bound 1 lower than his for some numbers). I don’t see how to get quite to p(N) >= sqrt(N) but this is close, anyway.
Well, Goldbach’s states that every even integer can be expressed as a sum of two primes. I actually screwed up a little on my lower bound but still. We are not considering any kind of negative prime, so for any given even integer x the two primes p and q such that p+q = x, p < x and q < x.
Now for some positive integer n, consider the set S defined as ** { x in S : x <= n } **, or in other words, the set of all positive integers less than or equal to n. The size of S is obviously n. Now, consider the set E a subset of S that contains only the even elements of S. The size of E is the floor of n/2.
Applying Goldbach, we see that for every e in E there exists a prime (and very improtantly distinct ) pair ** p,q < e ** such that ** p + q = e **. Since ** e <= n ** it follows that ** p in S and q in S **. Now, the total number of such prime pairs in the set S has to be greater than the size of E, otherwise by pigeonhole principle there will be an element of E with no corresponding pair, contradicting Goldbach’s Conjecture.
How many such pairs are there in S? Let’s call the total number of prime numbers in S to be pr(S). The total number of unordered pairs of primes in S is pr(S)** C 2** (that’s my lame attempt at writing down a combination) which is pr(S)(pr(S)** - 1)/2**. So combining with the result above we know that pr(S)(pr(S)** - 1)/2 > | E |, which resolves to pr(S)(pr(S) - 1) > n** and since pr(S) is positive pr(S)(pr(S)** - 1) < pr(S)^2**, so we plug it in above and get pr(S)^2 > n or pr(S)** > sqrt(n)**.
I’m sure I made a mistake somewhere (and checking now I remember Goldbach’s Conjecture allows for using the same prime twice, i.e. 7+7, but that doesn’t seem to affect the actual bound, just the combination calculation above). Anybody know what I’m missing or what I did wrong?
Allowing these pairs affects the bound slightly (see my previous post), but never by more than 1. But I’m not sure why you think this is such an outlandish result; although stronger than the easiest-proved lower bounds on p(N), it is far weaker than the actual behavior p(N)~N/log(N) and so seems fairly plausible.
Now that I think about it, it does seem rather plausible. What’s the maximum strict lower bound do we know for p(N)? It just goes against intuition but when I thought about it I realized that there’s really no other way for it to work out. The reason it seems unintuitive to me is because given two integer numbers n and x, if we describe the probability function t(n,x) that there exists a prime q such that n < q < n+x common sense tells me that there shouldn’t be a simple polynomial function f(n) such that t(n,f(n)) = 1. Apparently my mathematical common sense is wrong in this case, which is good because it will make me more careful in the future.
There are some good lower bounds listed here (and at a similar MathWorld page); the best ones, unsurprisingly, look pretty similar to the form N/log(N) given by the PNT.
Even very weak lower bounds on p(N), like Bertrand’s Postulate–
–satisfy this form. But the result implied by GC is slightly weaker than this. It doesn’t imply, for example, that there is always a prime between n[sup]2[/sup] and (n+1)[sup]2[/sup] (though this is also conjectured to be true), merely that on average there is at least one.
Thanks for the info on my question Omphaloskeptic and groman. (Unfortunately I’ve got a headache, so I have to wait for that to go away in order to digest the answers.)
Just for fun, here’s another piece of prime number trivia: There are intervals of arbitrary length with no primes in them. Every integer in [(n + 1)! + 2, (n + 1)! + n + 1] is composite, and there are n integers in that range.
I apologise,
I was indeed supposed to ask if the <i>sum</i> of any two sequential primes, minus 1, was prime.
Thank you for your answers.
23 + 29 - 1 = 3 * 17, so no.
I thought there are no rules, formulas, etc that can generate prime numbers. There are obvious ones such as all primes except 2 are odd and of those odd primes, none (except 5) will end in a 5, and so on.
There’s a simple algorithm for computing the least prime larger than a given integer N:
int nextPrime( int N )
{
int p = N + 1;
while ( !isPrime( p ) )
{
p = p + 1;
}
return p;
}
The simplest implementation of isPrime is to count the divisors of p, and return true when there are exactly two of them, and false otherwise. Of course, finding a faster technique would make you quite famous.
Given that, it should be quite obvious how to get the entire list of prime numbers less than or equal to a given input.
There are a lot of formulas that generate primes. John Conway has scads of them. Some are really bizarre. Covered one in a 3-part lecture I attended that was eerie (the way the formula worked that is, his lectures are great).
But they are not efficient in a computational sense. A simple sieve would be better.
Section 1.5 of Hardy and Wright’s “An Intro. to the Theory of Numbers” makes some points about this with additional coverage in other sections of the book. (That’s right, I had a copy within arm’s reach and looked it up. Go ahead and laugh.)
ftg
Okay perhaps I should have worded my posting more precisely.
There are no formulas that can generate prime numbers consistently without ever generating a composite number.
For example the trivial formula ((2*n) + 1) yields primes when n=1, 2 and 3 but fails at n=4, and at many other values of n. (You could say this formula generates all prime numbers except 2, but it also generates a heck of a lot of composite numbers too).
Here is an article about prime generating quadratics http://mathforum.org/library/drmath/view/56057.html
but even the best of these holds true for only 44 consecutive values of n.
I believe this is directly related to what Yeppa wanted to know.
The algorithm I gave can be expressed as an equation, but it was simpler to express in C-like syntax. Anyone who’s familiar with recursive function theory should be able to translate it quickly.
I know an formula which will always return a prime, never a composite: For any x, take y = x - x + 2. No matter what value of x you use in this formula, y will always be prime. 
wolf_meister, no. I did answer your intended question. There really are formulas that generate an infinite (or all) primes and only primes. (None of which are going to be polynomials of course.)
Cf. the reference cited.
ftg
Seriously, I would have read more about it but unfortunately, (unlike you), I did not have a copy of Hardy and Wright’s “An Introduction to the Theory of Numbers” within arm’s reach. 
I’m guessing the formulas must be rather complex or else you would have posted one.
Anyway, when I went to school (shortly after Pangaea seperated into distinct continents ), I was told there were no patterns to primes, no formulas, etc. Things must have changed quite a bit. Or maybe my ejukayshun wuz not of the highest kwality. 
I am not math enhanced, but I read the question and it seemed simple to me, perhaps because I did not overthink it. If this were on a test or given in a math class, I might answer differently or seek a formula, but as a baldly stated question makes me suspect the answer is not that involved. (See bellhops tip, words ending in gry, etc.)
Yes, since there are only 3 numbers in the set of sequential numbers that are primes…1,2,3 as noted above. The rest are not sequential, as they are separated by at least one number. (As opposed to the sequential set of prime numbers)
12=3-1=2 Prime
23=6-1=5 Prime
No, based on the above set of numbers.
1+2=3-1=2 Prime
2+3=5-1=4 Not Prime