Are Prime Numbers Truly Random?

In summary: Hurkyl's statement is correct.In summary, there are formulae for the nth prime number, but they are of exponential complexity or worse. This means attempting to calculate very large prime numbers using these formulae would take an incredibly long time. However, there also exist polynomials that can take on all prime numbers and some negative values. Despite the existence of these formulae, researchers still search for large prime numbers using computers.
  • #1
Entropia
1,474
1
http://www.nature.com/nsu/030317/030317-13.html
 
Mathematics news on Phys.org
  • #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 apparently random after all.
 
Last edited by a moderator:
  • #3
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 referring 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
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?
 

1. What are prime numbers?

Prime numbers are positive integers that are divisible only by 1 and themselves. They cannot be formed by multiplying two smaller positive integers together.

2. How are prime numbers different from composite numbers?

Prime numbers have exactly two factors, while composite numbers have more than two factors. For example, 7 is prime because its only factors are 1 and 7, while 8 is composite because its factors are 1, 2, 4, and 8.

3. Why are prime numbers not random?

Prime numbers follow a specific pattern and are not randomly distributed. They become less frequent as the numbers get larger, but there is no definite formula or algorithm for predicting the next prime number.

4. How are prime numbers used in cryptography?

Prime numbers are used in cryptography to generate large, random numbers for encryption. This is because it is difficult to factor a large number into its prime factors, making it harder to decrypt the message without the correct key.

5. Are there any practical applications for prime numbers besides cryptography?

Yes, prime numbers have many real-world applications. They are used in computer science, such as in generating secure keys for communication, and in finding the shortest route between multiple points. They are also used in music theory and in some types of data compression algorithms.

Similar threads

A Is it required to use the Reimann function to solve the problem?
    • General Math
Replies
8
Views
354
MHB -c5.LCM and Prime Factorization of A,B,C
    • General Math
Replies
3
Views
547
A How should I write an account of prime numbers?
    • General Math
Replies
5
Views
1K
B A conjecture on conjectures
    • General Math
Replies
17
Views
534
I What are the unique prime factors of -30?
    • General Math
Replies
22
Views
1K
MHB Apc.1.1.13 what is the prime factorization of 30,030
    • General Math
Replies
3
Views
764
A Prime Number Powers of Integers and Fermat's Last Theorem
    • General Math
Replies
1
Views
750
I Is Riemann's Zeta at 2 Related to Pi through Prime Numbers?
    • General Math
2
Replies
56
Views
5K
I Union of Prime Numbers & Non-Powers of Integers: Usage & Contexts
    • General Math
Replies
1
Views
1K
A I think I discovered a pattern for prime numbers
    • General Math
Replies
1
Views
758

Hot Threads

Recent Insights

Back
Top