My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree15Thanks
Reply
 
LinkBack Thread Tools Display Modes
August 14th, 2017, 02: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 ?
complicatemodulus is offline  
 
August 14th, 2017, 05:46 AM   #2
Member
 
Joined: Aug 2017
From: United Kingdom

Posts: 97
Thanks: 28

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.
cjem is offline  
August 14th, 2017, 05:56 AM   #3
Senior Member
 
Joined: Apr 2014
From: Glasgow

Posts: 2,074
Thanks: 695

Math Focus: Physics, mathematical modelling, numerical and computational solutions
Quote:
Originally Posted by complicatemodulus View Post
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.
Benit13 is offline  
August 14th, 2017, 06: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
complicatemodulus is offline  
August 14th, 2017, 06:19 AM   #5
Senior Member
 
Joined: Dec 2015
From: Earth

Posts: 177
Thanks: 23

A sequence $\displaystyle \; f(n)=PRIME \; $ exists
idontknow is offline  
August 14th, 2017, 10:18 AM   #6
Senior Member
 
Joined: Apr 2014
From: Glasgow

Posts: 2,074
Thanks: 695

Math Focus: Physics, mathematical modelling, numerical and computational solutions
Quote:
Originally Posted by idontknow View Post
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?
Benit13 is offline  
August 14th, 2017, 10:40 AM   #7
Member
 
Joined: Aug 2017
From: United Kingdom

Posts: 97
Thanks: 28

Quote:
Originally Posted by Benit13 View Post
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...
Thanks from Benit13
cjem is offline  
August 14th, 2017, 11:13 AM   #8
Senior Member
 
Joined: May 2016
From: USA

Posts: 825
Thanks: 335

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.
JeffM1 is offline  
August 14th, 2017, 11:16 AM   #9
Senior Member
 
Joined: Aug 2012

Posts: 1,639
Thanks: 415

Quote:
Originally Posted by JeffM1 View Post
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.
Maschke is online now  
August 14th, 2017, 11:57 AM   #10
Senior Member
 
Joined: May 2016
From: USA

Posts: 825
Thanks: 335

Quote:
Originally Posted by Maschke View Post
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.
JeffM1 is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
primes, proof, random



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Elementary proof of the 1D simple random walk "infinite crossing" theorem Bromster Algebra 0 December 24th, 2015 11:09 PM
how "random" are online "random" spinners? skynet Probability and Statistics 1 June 18th, 2014 01:26 PM
A "simple" application of dirac delta "shift theorem"...help SedaKhold Calculus 0 February 13th, 2012 12:45 PM
"recurrent" mersenne primes brunojo Number Theory 70 June 15th, 2009 05:37 PM





Copyright © 2017 My Math Forum. All rights reserved.