Prime Number Distribution Solved?

  • Thread starter synergy
  • Start date
27
0
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 refering 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

Staff Emeritus
Science Advisor
Gold Member
14,847
14
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, x1, ... xm) that has the property that the solution set of

p(n, x1, ... xm) = 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, x1, ... xm) = n * (1 - p(n, x1, ... xm)^2)

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

NateTG

Science Advisor
Homework Helper
2,450
5
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.
 
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...
 
More...

Try even negative numbers. The negs cancel out.
 

HallsofIvy

Science Advisor
41,625
823
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 nth prime
 
357
0
Originally posted by HallsofIvy
It is lightly that 2n + 32n/3 + 52n/5
+ ... + pn2n/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
 
Last edited:
357
0
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 pa corners once so that it get's as many corners as possible, will it get pb corners?

Best wishes Erik-Olof or Sariaht
 
Last edited:

HallsofIvy

Science Advisor
41,625
823
Why have the last two posts started:

Originally posted by HallsofIvy
and then contained nothing posted by me?
 
27
0
Re: Equation yielding only primes

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.
 
357
0
Originally posted by HallsofIvy
Because i like short threads. Best wishes: Erik-Olof or Sariaht
 

HallsofIvy

Science Advisor
41,625
823
Should I feel flattered?
 
357
0
How am I supposed to feel, corrected?
 

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top