# Prime Number Distribution Solved?

Hi everyone, I'm new here. I have an interesting conjecture I have been trying to prove for some time. I've tried it out on a couple of forums, but perhaps some of you can help. Please make whatever comments you can (good or bad) and all input is welcome.

I will give this conjecture in algorithm form, along with an example, and then put it in a general theoretical form.

Take the first (n-1) primes so that p(1)=2, p(2)=3, etc. Now create two numbers, A and B, such that each prime in the above set is a factor of exactly one of them, A or B. It doesn't matter what the exponent on each of them is, as long as it is an integer greater than zero. Notice, for example, that "3 is a factor of A" could mean that 3 to the 56th power is a factor of A.
Good time to introduce the example:
Say p(n-1) is 11. Then A could be 2^4 * 7^3 and B could be 3*5*11^2. Notice each prime <=11 is in A or B, and the exponents are arbitrary. In fact, I usually leave the exponents variable:
A=2^a*7^b, B=3^c*5^d*11^e

Now, check out abs( A +/- B ) = Q* where abs() is absolute value, +/- is plus or minus, and Q* is the set of solutions dependant upon the original exponents.
Now, if q is in Q*, and q < [p(n)]^2 (in the example, 13^2=169), then q MUST be prime (by the distributive principle, q is relatively prime to 2,3,5,7,11 and since it's less than 169, it is prime) or the number 1.

In practice, not all primes less than 169 can be found with the above equation. However, by repartitioning the set into A and B, i.e. make different choices of which primes are factors of A and which are factors of B, all solutions can be gotten this way. In fact, all solutions up to 1369 can be gotten the same way by using the primes up to 31 in A and B.
As I said, every such solution - given the less-than condition - is either prime or 1. The only thing I haven't proven is that EVERY prime can be gotten in this manner.
Notice that, if every prime does follow this pattern, we have a finite set of exponential equations that gets any finite range of primes given as being between p(n-1) and [p(n)]^2.
Does anyone have any ideas on how I could begin to prove that EVERY prime follows this pattern? Thanks for taking the time to read this and in advance for any input.
=================================================================
Theoretical approach:
key:
p(n)# ("read p(n) primorial") = 2*3*5*7*...*p(n)

Given: 2,3,5,...p(n)
If p(n-1+i) does not divide A*B for i an integer > 0 and,
if p(n-1)# divides A*B then,
abs( A +/- B ) = Q*
and if q is an element of Q* and q < [p(n)]^2
then q is prime.
===================================================================
Note: to get a "feel" for this stuff, try the following example, where I leave all of the exponents constant=1 except the exponent on 2:
Abs(105 +/- 2^x)=q where q<121 (note 105=3*5*7)
(note also that abs() takes care of negative primes)
Thanks again,
Aaron

take a look

I find it interesting that nobody has anything to say about this. It really only involves 4th grade math. Is it too boring, or too simple, or what? Would somebody tell me what they think? I've tried using logarithms and modular arithmetic and even straight algebra to prove this, but I can't help thinking I'm overlooking some basic technique that will push the proof through. Basically, the challenge is to show that every exponential equation of the proper form has enough solutions at integer exponents to produce all of the primes in the range from p(n-1) to [p(n)]^2. I'm not sure where to go from there. Are there any ideas out there?[?] I appreciate all input, you never know what will help. Thanks to all of you that looked at this - 'bye for now.
Aaron

Njorl
There are an infinite number of exponent sets that yield A+/-B in the allowed range. You can never be sure your set of primes is exhaustive in the range.

Njorl

True, oh so true...(very good point)
However, in practice it has been my experience that "small" exponents are sufficient, though I don't know if this is true for larger primes. For example, for a particular partition, you might go along for a while getting primes by incrementing the exponent on 2, then you get too large a number so you drop that exponent to a lower value then increment 3's exponent, etc. In other words, you just don't look for the "A containing super-large exponent minus B containing super-large exponent" scenario. When you run out of primes, increment a different exponent. When you've exhausted all choices, repartition. As I said, this technique got all primes less than 1369, though it is possible we might have to use the rest of those infinite number of exponents later, somehow I doubt it. Anyway, even if they are needed, my interest is more theoretical, whether primes are distributed in a way completely controlled by this algorithm, not whether I can get huge ones (although the understanding supplied by this stuff may lead to a new way to find huge primes).
Anyway, THANKS FOR THE COMMENT. Please keep them coming.
Aaron

rolandmath
There is no function gives prime numbers. Problem Show that if f(x)=a0+a_1x+...a_nx^n where the coefficients are integers, then there is an integer y such that f(y) is composite. Here is a hint Assume that f(x)=p is prime and show that p divides f(x+kp) for all integers k. i.e there are no algorithams that find primes except those that do it by brute force(sieve of erasasthones). By the way prime number distributions fall into the realm of solving the riemann hypothesis.

Hurkyl
Staff Emeritus
Gold Member
You might want to do some more reading on the subject. There are functions that give prime numbers; they come in various types, but they include functions such that p(n) is the n-th prime number. (though this latter type of function is very computationally inefficient)

A good bit is known about the distribution of prime numbers. The asymptotic behavior of the prime counting function, &pi;(n), is well-known. Mathematicians can get decent bounds on how big the n-th prime number is. Not to mention useful little theorems like for any n > 1, there is a prime p in the range n < p < 2n. (this is useful for theorem proving)

rolandmath
there is NO function that only gives prime numbers, by the previous theorem. Very easy to prove. As far as giving the nth prime, of course you can do that but through brute force methods like sieves which would in theory alway give the nth prime but since primes are of the infinite sort you can't list them all just the next one. And i have done a lot of research on this area. In fact I am taking analytic number theorey right as we speak.

Hurkyl
Staff Emeritus
Gold Member
What about the function f(n) = 3?

Your proof only shows that no nonconstant single variable polynomial can take prime values for every integral argument... there are lots of other functions one may write. Maybe you'll learn in your class some of the things mentioned at Mathworld:

http://mathworld.wolfram.com/PrimeFormulas.html

rolandmath
yes i have shown that every nonconstnat fucntion does not give primes. therefore we cant discern distributions from such a fucntion. even yours. We can write lost of constant functions that go to only primes

Hurkyl
Staff Emeritus
Gold Member
yes i have shown that every nonconstnat fucntion does not give primes.

No you have not. You've only given reasoning for nonconstant polynomial functions of a single integer variable.

That is a far cry from every nonconstant function.

rolandmath
have you even attempted to prove the theorem. NO function with integer coeficients gives only prime numbers. The theorem says that any function that would do so would also admit composites. Since we cannot factor large numbers were screwed since we would not know what is prime or what is composite.I believe that the theorem is also true for complex numbers, as far multivariable you are welcomed to try to find one. Also the nth prime function you give is useless. Call the largest known prime n, what is n+1.

Hurkyl
Staff Emeritus
Gold Member
have you even attempted to prove the theorem.

I've known it at least since high school.

NO function with integer coeficients gives only prime numbers.

The term "integer coefficients" is not applicable to general functions.

The theorem says that any function that would do so would also admit composites.

Once again, your theorem is only for nonconstant polynomials in a single variable over the integers. Not all functions are polynomials. Not all polynomials are in a single variable over the integers.

For example, the polynomial given at http://functions.wolfram.com/NumberTheoryFunctions/Prime/31/06/ yields every and only prime numbers if we restrict its domain to parameters that give positive values.

Or more trivially, the polynomial x2 + x + 41 gives only prime numbers if you restrict its domain to integers that give prime answers.

Since we cannot factor large numbers were screwed since we would not know what is prime or what is composite.

On the contrary; there exist good tests (both exact and probabilistic) for testing an integer for primality. Primality testing is, as far as we know, a lot easier than factoring.

I say "as far as we know" because factoring is NP-complete, and it is only a conjecture that NP-complete problems are "hard".

Also the nth prime function you give is useless.

Nobody said it was a practical method of giving the n-th prime. The point is that such functions exist. (And someone probably did find them useful for some purpose, otherwise they probably wouldn't be known)

Call the largest known prime n, what is n+1.

n+1 is composite.

Last edited:
HallsofIvy
Homework Helper
NO function with integer coeficients gives only prime numbers.

All this tells us is that you don't know what a function is. Functions in general do not HAVE "coefficients". You appear to be using the word "function" when you mean "polynomial".

Here's a function whose values consist of all primes and only primes: F(n)= the nth prime.

rolandmath
that is not a true function. We know the largest known prime call it p so let f(n)=p for some n
what is f(n+1) ?
you don't know, since p is the largest known prime. Functions should give us values for all elements in the domain. What you've shown is that you DON'T KNOW what a function is. All functions have coefficients. Just multiply by one and you got it

f(n)=1*nth prime
coeffient is 1.

A polynomial is a function
f(x)=a_0+a_1x+...
or like
g(x)=a_0+a_1g_1(x)+a_2g_2(x)+...

whether it be rational, integer, complex or real coefficients.

Staff Emeritus
Gold Member
Dearly Missed
A polynomial is a function, but a function is not necessarily a polynomial, there are functions that cannot be expresed as polynomials, such as sin x and ex, and there are much more general functions than that.

A function is a rule for associating members of one set (the domain) to members of another (the range). The price of shares of Microsoft stock on the NYSE, minute by minute, is a function, it associates he members of one set (minutes) to the members of another set (prices).

Some functions are easier to work with than others, polynomials are just about the easiest. But you need to get beyond thinking all functions are polynomials.

rolandmath
I know that all functions are not polynomials take

f(x)=1 x irrational
f(x)=0 x rational

and infinitley many more examples

but surely e^x can be expressed as a infinitie series poly take

e^x=1+x+x^2/2!+x^3/3!+...

so can cos x sin x tan x ln x. In fact the only way you can take integrals of certain functions is to take power series. A pain in the ass but cool none the less.
Even

1/(1-x)=1+x+x^2+... for -1<x<1

Hurkyl
Staff Emeritus
Gold Member
but surely e^x can be expressed as a infinitie series poly take

No it can't, because there's no such thing as an "infinite series polynomial".

By definition, polynomials have finite degree... so while all polynomials are power series, the reverse is not true.

This distinction is made for good reason; while power series do have a lot in common with polynomials, there is a lot they don't have in common with polynomials as well.

Hey all, I haven't checked out this post lately, it looks like alot's been going on - cool !

Yes, I've noticed the Riemann zeta function has alot to do with the distribution of the primes, but I really don't know alot about that yet (though I have done some research, if anyone has anything interesting to explain about zeta, please feel free - we might even be able to prove the Riemann hypothesis - I'm willing to share the \$1million).

About functions - notice I get around the "there isn't a fcn that produces all primes" idea - even though there is one - because I have SEVERAL functions that are related but different. Each one produces some primes, but it takes several functions to produce them all. As per the example at the beginning of the thread:

abs(3*5*7 +/- 2^x) gives 107,109,113,103,101,97,89,73,41,23 which are not all of the primes less than 121. Only by "mixing it up" within the fcn can we get the rest.

Thanks for all the input, keep it coming!
Aaron

rolandmath
there is a book about it by john derbyshire. It really is simplistic but will get you in the direction of the zeta. I took a class in riemann surfaces a while ago and was taken aback at the amount of knowlegde needed just to comprehend the problem. Good luck. Didn't mean to be such a a**. You have the makings of a good mathematician. Good Luck.

by the way, I read somewhere that there is a function - and I think it's a polynomial - in 26 variables that gives all primes, although it's very inefficient. I won't swear my method is more efficient at large primes, though I'm certain it is for small ones.
Aaron

Hurkyl
Staff Emeritus
Gold Member
Nope.

Originally posted by Hurkyl
Nope.

I cann't accept that without a proof. I didn't see any proof at wolfram's site. could you point me to a proof, if its true I'll be very surprised...

Hurkyl
Staff Emeritus
Gold Member
Unfortunately, I cannot. I have only once seen a proof of this sort of thing in a journal.

While it seems surprising at first, really it shouldn't be. A lot of work has been done showing how logic can be encoded with equations and arithmetic (for instance, see the work of Godel and Tarski), so it's not really all that astonishing that polynomials like this exist.

edit: here's a better link on this polynomial than the one at Wolfram. It has references if you want to go digging:

http://primes.utm.edu/glossary/page.php?sort=MatijasevicPoly

Last edited:
Hurkyl
Staff Emeritus
Gold Member
Oh, touching back on one of the earlier topics in this thread, a deterministic polynomial time algorithm for testing an integer for primality is known... see

http://www.cse.iitk.ac.in/news/primality.html [Broken]

as compared to the problem of factoring which is only known to be NP-complete.

Last edited by a moderator: