- #1
roger
- 318
- 0
Hi,
I just wondered what patterns are known about the prime numbers ?
cheers
roger
I just wondered what patterns are known about the prime numbers ?
cheers
roger
Then what do you mean by "pattern"?There is a pattern. We just don't know what it is yet.
Hurkyl said:Then what do you mean by "pattern"?
We know exactly when primes occur, and we have efficient methods for telling if a given number is a prime. We even have explicit formulas for the n-th prime number.
JasonRox said:There is a pattern. We just don't know what it is yet.
Zurtex said:Patterns are more to do with spotting simple occurrences in real life, not much to do with mathematics.
Helicobacter said:How do we know there is one?
That might not be very meaningful regarding the sequence of primes. For every algorithm there is an equivalent series of mathematical operations, or, if you combine these statements, a mathematical function. Hence, if an algorithm can "spit out" all the primes, then there is a mathematical function that produces that sequence. However this mathematical function can very well be infinite. This is the case with the sequence of primes. There is a very simple algorithm that outputs all the primes. Namely one that iterates through all the positive integers and divides each number by those that come before it (and are bigger than one), outputting a number when it is not divisable.JasonRox said:It was proven that if an algorithm can be made so that a computer can spit out the sequence, then a formula exists. Hence, a pattern.
Well define what a pattern is in mathematics for me then.-Job- said:I don't agree with that statement.
Lots of mathematical functions can be described as being 'infinitely long' take for example all taylor series, this does not make them less useful/-Job- said:. However this mathematical function can very well be infinite.
That's a particularly inefficient way but o.k.-Job- said:This is the case with the sequence of primes. There is a very simple algorithm that outputs all the primes. Namely one that iterates through all the positive integers and divides each number by those that come before it (and are bigger than one), outputting a number when it is not divisable.
That makes no sense, it takes an infinite amount of time to output all natural numbers i.e {1, 2, 3..) on a computer, would you describe the mathematical function f(x) = x as being infinite?-Job- said:In order to output the sequence of all the primes this algorithm would need infinite time, an infinite sequence of operations and thus be equivalent to an infinite mathematical function.
Most of that is so much gibberish I can't really make sense of. Algorithms exist that calculate if a number is a prime or not, much faster than O(n).-Job- said:What pattern exists there then?
If instead we wanted to output the first 100 primes, than the above algorithm would take less than 1000 operations, the equivalent mathematical function have in the order of 1000 operations. Would the sequence have a pattern?
For every sequence there is an algorithm that outputs all the elements in that sequence, it may require infinite memory and infinite time, but it will output all the elements in that sequence, does every sequence have a pattern then?
My definition of a pattern is something that is repeated. Yet, for every sequence of numbers without repetition, such as the primes, the digits of pi, etc, there is an algorithm capable of outputting that sequence.
I would say, if an algorithm can output any n elements of a sequence in O(n) time, with finite memory, then the sequence has a simple pattern. If it requires more then i don't know, but it certainly isn't a simple pattern.
-Job- said:That might not be very meaningful regarding the sequence of primes. For every algorithm there is an equivalent series of mathematical operations, or, if you combine these statements, a mathematical function. Hence, if an algorithm can "spit out" all the primes, then there is a mathematical function that produces that sequence. However this mathematical function can very well be infinite. This is the case with the sequence of primes. There is a very simple algorithm that outputs all the primes. Namely one that iterates through all the positive integers and divides each number by those that come before it (and are bigger than one), outputting a number when it is not divisable.
In order to output the sequence of all the primes this algorithm would need infinite time, an infinite sequence of operations and thus be equivalent to an infinite mathematical function.
What pattern exists there then?
If instead we wanted to output the first 100 primes, than the above algorithm would take less than 1000 operations, the equivalent mathematical function have in the order of 1000 operations. Would the sequence have a pattern?
For every sequence there is an algorithm that outputs all the elements in that sequence, it may require infinite memory and infinite time, but it will output all the elements in that sequence, does every sequence have a pattern then?
My definition of a pattern is something that is repeated. Yet, for every sequence of numbers without repetition, such as the primes, the digits of pi, etc, there is an algorithm capable of outputting that sequence.
I would say, if an algorithm can output any n elements of a sequence in O(n) time, with finite memory, then the sequence has a simple pattern. If it requires more then i don't know, but it certainly isn't a simple pattern.
Okay.-Job- said:I would say, if an algorithm can output any n elements of a sequence in O(n) time, with finite memory, then the sequence has a simple pattern.
That's not true! There are countably many algorithms, and uncountably many sequences. (Even if we only consisder sequences whose terms are either 0 or 1)-Job- said:Yet, for every sequence of numbers without repetition, such as the primes, the digits of pi, etc, there is an algorithm capable of outputting that sequence.
You're misinterpreting me. I said if the algorithm takes a finite amount of memory, meaning if the algorithm can be stored in a finite amount of memory, meaning that if you had an algorithm you'd be able to store it in a hard drive with finite capacity, meaning that the algorithm isn't infinitely large. I didn't mean memory usage at run time. For that i would bound it at about O(n).Also, even if you give a computer the direct formula of a sequence, it requires more and more memory as n gets larger. So, your point is invalid.
Hurkyl said:Okay.
It's odd you would think that the sequence 1, 2, 3, 4, 5, 6, ... of positive integers, in order, doesn't have a simple pattern!
The list consisting of the first N integers has length [itex]\Omega (N \lg N)[/itex], so any algorithm for computing this sequence must take [itex]\Omega(N \lg N)[/itex] time.
That's not true! There are countably many algorithms, and uncountably many sequences. (Even if we only consisder sequences whose terms are either 0 or 1)
Prime numbers are positive integers that are only divisible by 1 and themselves. Examples of prime numbers include 2, 3, 5, 7, and 11.
One way to identify prime numbers is by using the Sieve of Eratosthenes, which is a method of systematically eliminating non-prime numbers to find all prime numbers up to a given limit. Another method is to use trial division, which involves checking if a number is divisible by any numbers other than 1 and itself.
While prime numbers may seem random, there are some patterns and properties that have been identified. For example, prime numbers tend to become less frequent as they get larger, and there are certain patterns in the distribution of prime numbers on the number line.
Prime numbers play a crucial role in many areas of mathematics, from cryptography to number theory. They are also important in various real-world applications, such as in generating secure codes and in data encryption.
No, it is not possible to accurately predict the next prime number. While there are patterns and properties in prime numbers, they do not follow a specific sequence or formula that allows for prediction. Prime numbers are considered to be random and unpredictable.