Prime Numbers Not Random?

  • Thread starter Entropia
  • Start date
  • #1
Entropia
140
1
http://www.nature.com/nsu/030317/030317-13.html
 

Answers and Replies

  • #2
The sequence of primes is entirely deterministic. There are even nth prime formulae; however, the formulae are of exponential complexity...or worse.

Addendum: Oh, there's a link. The site explains how the sucession of primes is not so apparantly random after all.
 
Last edited by a moderator:
  • #3
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,967
19
It gets better than that.

There exist polynomials p(n) (n integer) that only take on prime or negative values. Even bettern there exist polynomials p(n) that can be every prime number and some negative values, but nothing else!

There even exists a formula for the n-th prime number! (I've only heard this referenced though, I have never actually seen it)

Hurkyl
 
  • #4
Originally posted by Hurkyl
There even exists a formula for the n-th prime number! (I've only heard this referenced though, I have never actually seen it)

Hurkyl

What if this is true, why are they still searching for big prime numbers with computers and stuff. Why don't they just plug 100,000,000,000,000,000,000,000,000,000,001 in for the n and get a massive prime number. I really have to doubt about this part.

What are the functions you were refering to that take on all prime numbers and some negative numbers. Those sound kind of interesting.
 
  • #5
Why don't they just plug 100,000,000,000,000,000,000,000,000,000,001 in for the n and get a massive prime number?

Exponential Complexity:

If T(f; n) is the time it takes to calculate f(n), the T(f; n + 1) is approximately T(f; n) times some constant k > 1. Attempting to calulate the 100,000,000,000,000,000,000,000,000,000,001st prime would probably require more eons than there are Angstroms in a lightyear.
 
  • #7
Loren Booda
3,119
4
Hurkyl
There even exists a formula for the n-th prime number! (I've only heard this referenced though, I have never actually seen it)
Urban Legend?
 

Suggested for: Prime Numbers Not Random?

  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
20
Views
9K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
12
Views
4K
  • Last Post
Replies
1
Views
896
  • Last Post
Replies
6
Views
2K
Replies
10
Views
19K
Replies
3
Views
3K
  • Last Post
Replies
10
Views
2K
  • Last Post
Replies
14
Views
5K
Top