Has the Prime Number Distribution Puzzle Been Cracked?

[synergy]

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

 

[synergy]

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

 

[synergy]

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]

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]

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 function does not give primes. therefore we can't discern distributions from such a function. even yours. We can write lost of constant functions that go to only primes

 

[Hurkyl]

yes i have shown that every nonconstnat function 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.

Have you read the page I linked?

 

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

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 x² + 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.

 

[HallsofIvy]

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

your half ass funciton
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.

 

[selfAdjoint]

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 e^x, 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]

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.

 

[synergy]

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 a lot to do with the distribution of the primes, but I really don't know a lot 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.

 

[synergy]

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

 

[ogb p]

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.

This is a joke?... right?

 

[Hurkyl]

Nope.

 

[ogb p]

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]

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

 

[Hurkyl]

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


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

 

[ogb p]

thanks for the link! it was very informative

I see now, the equation results in a finite amount of positive values, all of which are prime... very impressive... I mistakenly thought you were referring to a polynomial which produces an infinite number of prime values. As the site says, "so many have asked if it is possible to have a polynomial which produces only prime values. Sadly, it is easy to show that this is not the case (unless the polynomial is constant)"

 

[Hurkyl]

It does provide all primes. (Though I agree that the wording on the page isn't the most clear)

(And as noted before, anything it produces that isn't a prime is a negative number)


I've found some lecture notes at http://www.risc.uni-linz.ac.at/courses/ss99/logic2/ that have the relevant theorems (in addition to a number of interesting topics). In these notes, in the last section:

Theorem 35 - An n-ary predicate P is semidecidable iff there exists a register machine with n input registers which stops if the input has the property P.

Theorem 36 - Any semi-decidable predicate is diophantine.


Given theorem 35, it's easy enough to see that primality is semidecidable. Given an input p, loop through all positive integers n and stop if n divides p.

Thus, by theorem 36, there is a diophantine equation in n and other variables which has solutions only when n is prime.

That is, there is a polynomial p(n, x₁, ... x_m) that has the property that the solution set of

p(n, x₁, ... x_m) = 0

consists only of solutions where n is prime, and for every prime number q there is a solution where n = q.


Finally, the polynomial

f(n, x₁, ... x_m) = n * (1 - p(n, x₁, ... x_m)^2)

Can take on any prime value, and any value which is not prime must be negative.

 

[NateTG]

Regarding the seminal post of this thread:

Let's say that we're starting with n primes. Then the number of partitions we're looking at is 2^n. Now, let's also limit ourselves to 1,2, or 3 as the exponents, that makes the total number of options that need to be explored 6^n. Since the n th prime is approximately e^n, checking all the numbers up to e^2n is probably faster.

So, even if your algorithm works, it isn't computationally useful.

 

[StargateX1]

Equation yielding only primes

What about 41+n(n+1)? Any n you plug into that equation will yield a prime number.

Try it with n=1, n=2, n=3, n=5, n=10, n=15, n=28, n=33, n=39, etc...

 

[StargateX1]

More...

Try even negative numbers. The negs cancel out.

 

[HallsofIvy]

Rolandmath: you seem to be consistently missing Hurkyl's point.

You have repeatedly said that your proof shows that no function with integer coefficients can give all prime numbers and only prime numbers. Hurkyl has repeatedly pointed out that you should be saying polynomial. Functions don't even have to have coefficients.

Here's a perfectly good function that gives all prime numbers and has only prime values:

p(n) is defined as the n^th prime

 

[Sariaht]

Originally posted by HallsofIvy

It is lightly that 2ⁿ + 3^2n/3 + 5^2n/5
+ ... + p_n^2n/p, were 2n/p is replaced by a nearby number n, like 0, 1 etc., is a prime.



1 2 3 4 5 6 7 8 9

Add two of these speaches...

6+9 gains the value 15, which is not a prime.

but to get 6 you have to add 3 to 3, or 2 to 2 to 2 etc.
if you follow the serie 2 + 3 + 2 + 3 + ... you notice that the primes are getting more and more rare the longer you get

thats because 2 is a more common speach than 3, and that 5 is more common than 2*3. It's better to follow the equation above.

Best wishes Sariaht

 

[Sariaht]

Originally posted by HallsofIvy

bend a triangel once so that it get's as many corners as possible.

It gets 7.

My question is:

If you bend a polygone with p_a corners once so that it get's as many corners as possible, will it get p_b corners?

Best wishes Erik-Olof or Sariaht

 

[HallsofIvy]

Why have the last two posts started:

Originally posted by HallsofIvy

and then contained nothing posted by me?

 

[ogb p]

Originally posted by StargateX1
What about 41+n(n+1)? Any n you plug into that equation will yield a prime number.

Try it with n=1, n=2, n=3, n=5, n=10, n=15, n=28, n=33, n=39, etc...

n=41 is divisible by 1, 41, 43, and 1763. Therefore it is not prime. the same goes for 41x where x is any positive integer.