My Math Forum Proof Primes are not "random"
 User Name Remember Me? Password

 Number Theory Number Theory Math Forum

 August 14th, 2017, 01:01 AM #1 Banned Camp   Joined: Dec 2012 Posts: 1,028 Thanks: 24 Proof Primes are not "random" Is there any Official Proof that Primes are not "Random" numbers ?
 August 14th, 2017, 04:46 AM #2 Senior Member   Joined: Aug 2017 From: United Kingdom Posts: 313 Thanks: 112 Math Focus: Number Theory, Algebraic Geometry They are clearly deterministic rather than truly random - as soon as you've defined the ring of integers, the primes and their distribution are completely determined. You probably didn't mean "truly random" when you said "random", but the issue is that what you've asked is incredibly ambiguous. Until you make your statement precise, it's meaningless to ask if there's a proof of it.
August 14th, 2017, 04:56 AM   #3
Senior Member

Joined: Apr 2014
From: Glasgow

Posts: 2,164
Thanks: 736

Math Focus: Physics, mathematical modelling, numerical and computational solutions
Quote:
 Originally Posted by complicatemodulus Is there any Official Proof that Primes are not "Random" numbers ?
I guess you mean something like "Is there any structure to the underlying distribution of prime numbers?"

There's certainly metrics about the distribution and rate of change of primes as you look to higher numbers, but as far as I know there is no deterministic function $\displaystyle f(n)$ that can predict the sequence of primes; current algorithms that determine prime numbers are NP in complexity.

 August 14th, 2017, 05:00 AM #4 Banned Camp   Joined: Dec 2012 Posts: 1,028 Thanks: 24 Is also clear to me that primes follows a fixed pattern, so they are not "ramdomly" placed. So I would like to know if, and where to find it, there is a official proof. I'm playing with my Complicate Numbers and I saw that applying a function to Integers or to Primes will produce a very similar output behavior, so is clear they are not "randomly" placed or the final behavior must be partially or fully different from integer's one. Thanks Ciao Stefano
 August 14th, 2017, 05:19 AM #5 Senior Member   Joined: Dec 2015 From: somewhere Posts: 734 Thanks: 98 A sequence $\displaystyle \; f(n)=PRIME \;$ exists
August 14th, 2017, 09:18 AM   #6
Senior Member

Joined: Apr 2014
From: Glasgow

Posts: 2,164
Thanks: 736

Math Focus: Physics, mathematical modelling, numerical and computational solutions
Quote:
 Originally Posted by idontknow A sequence $\displaystyle \; f(n)=PRIME \;$ exists
Of course the sequence exists. What I said was that there is no function that determines the sequence in a deterministic way. Specifically, all algorithms that exist to compute f(n) are NP algorithms.

Quote:
 Is also clear to me that primes follows a fixed pattern, so they are not "ramdomly" placed.
- What do you mean by "follows a fixed pattern"?

If you mean "has a predictable distribution" then yes, (as far as I'm aware...) there are metrics that characterize the distribution of primes and allow you to make predictions such as what the number of primes are within a certain interval.

However, if you mean "the function to determine the sequence of primes is deterministic" then my question to you is this:

Also...

- Who's saying that they are "randomly placed"? What do you mean by that?

August 14th, 2017, 09:40 AM   #7
Senior Member

Joined: Aug 2017
From: United Kingdom

Posts: 313
Thanks: 112

Math Focus: Number Theory, Algebraic Geometry
Quote:
 Originally Posted by Benit13 Of course the sequence exists. What I said was that there is no function that determines the sequence in a deterministic way. Specifically, all algorithms that exist to compute f(n) are NP algorithms.
I think you're a little confused. Sequences of real numbers (such as $f(n)$ here) are by definition functions from the naturals to the reals. I also don't see the relevance of whether the algorithms are NP: whether something is deterministic is not dependent on how easy it is to determine it in practice...

 August 14th, 2017, 10:13 AM #8 Senior Member   Joined: May 2016 From: USA Posts: 1,310 Thanks: 552 This whole thread seems to have been destined from the start to generate confusion, which is not surprising given that complicatemodulus initiated it. Obviously the function f(n) = the nth prime exists. It relates positive integers to positive integers. (Why involve the reals?) f(1) = 2. f(2) = 3. f(3) = 5. And so on. But so what? The further question of whether that function is "random" or "deterministic" depends on how those words are defined. Moreover, a general formula for the function is not known, which makes it difficult or perhaps impossible to analyze the function in terms of those definitions. If someone defines what unique properties a "random" function has or what unique properties a "deterministic" function has and also specifies the properties of f(n) = the nth prime, then we can have a sensible conversation. Until then, it is a will of the wisp.
August 14th, 2017, 10:16 AM   #9
Senior Member

Joined: Aug 2012

Posts: 2,411
Thanks: 754

Quote:
 Originally Posted by JeffM1 f(1) = 2. f(2) = 3. f(3) = 5. And so on. But so what? The further question of whether that function is "random" or "deterministic" depends on how those words are defined. Moreover, a general formula for the function is not known, which makes it difficult or perhaps impossible to analyze the function in terms of those definitions.
If you give me n, I can deterministically obtain f(n) via the sieve of Eratosthenes. It's deterministic. Someone complained that it's not efficiently computable. That's irrelevant. It's computable. Give me n and I'll give you f(n) via a deterministic algorithm that halts in a finite number of steps.

August 14th, 2017, 10:57 AM   #10
Senior Member

Joined: May 2016
From: USA

Posts: 1,310
Thanks: 552

Quote:
 Originally Posted by Maschke If you give me n, I can deterministically obtain f(n) via the sieve of Eratosthenes. It's deterministic. Someone complained that it's not efficiently computable. That's irrelevant. It's computable. Give me n and I'll give you f(n) via a deterministic algorithm that halts in a finite number of steps.
Is the question whether we can determine primes?

If so, the answer is "of course, we can"

I doubt, however, that is what the intended question is. My point was that without understanding the question, we can spin our wheels forever. I suspect the question is whether there is a simpler pattern to the primes than a list of the primes themselves and whether that pattern can be expressed in a formula.

 Tags primes, proof, random

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Bromster Algebra 0 December 24th, 2015 10:09 PM skynet Probability and Statistics 1 June 18th, 2014 12:26 PM SedaKhold Calculus 0 February 13th, 2012 11:45 AM brunojo Number Theory 70 June 15th, 2009 04:37 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top