/sci/ - Science & Math

yes

Poorly phrased question. Define random distribution.

Or let's turn it around, is the distribution of prime numbers not a pattern?

Also unknown.

We dont even know how many there are. We often assume there's infinite, but it hasnt been proven...

>>4255971
> We often assume there's infinite, but it hasnt been proven...
that was proven over 2000 years ago...

>>4255971
>We often assume there's infinite, but it hasnt been proven...
What? Let's assume you have a list of all prime numbers up to a certain value. Take the product of those numbers and add one. You now have an additional prime number, since it's not divisible by any prime, and therefore any other number, below it. Therefore, there is an infinite number of primes.

>>4255971

>>4255971

It's not poorly phrased at all. Does there exist an algorithm by which you can predict every single prime number? If so, the distribution is not random. If not, it is.

>>4256012
Okay that one's better. Youve rephrased it...

Here's an algo: Count off all the integers. Bam you've counted off all the primes.

Easy peasy

>>4256014

That doesn't predict prime numbers. That predicts numbers. Some of them happen to be prime.

Stop talking about this if you don't understand what's going on.

>>4256012
Such an algorithm does not exist. There are special cases that are easy to predict, but not all primes fall into one of these special cases.

Proving a number is prime is, in general, not an easy task either. I think the current best algorithm for testing primality (AKS) runs at <span class="math"> O(\textnormal{log}^6(n)) [/spoiler].

>>4256029
<span class="math">O(log^6(n)) [/spoiler]

Apparently syntax here isn't quite the same as my TeX editor.

>>4256012
It IS poorly phrase. Your new way of phrasing it is even worse. Yes, there is an algorithm. An example of a very poorly performing one is:
1) consider integer i=1
2) is i prime?
2)a) if yes, output i,
2)b) if not, do not output i,
3) increase i by one and go back to step 2).

But it clearly doesn't answer OP's question.

So, to answer OP's question, what we know about prime numbers is that the number of prime numbers between 0 and n is roughly <span class="math">n/ln(n)[/spoiler]. That gives you their density. In average, if you have a prime number p, the next prime number is roughly <span class="math">ln(p)[/spoiler] further. But we also know that there exist pairs <span class="math">(p,p+2)[/spoiler] of primes as high as you want, so that distribution is only in average. You can also look up "probable primes" for algorithms that generate very very high numbers that have a good chance of being prime.

No, it is defined by a set of concrete rules and therefore by definition not random, check out this video:

http://www.youtube.com/watch?v=dux1TBAmndM

>and my dubs

Does encryption still work?

>>4256046
What?

>>4256046

nah, encryption stopped working thanks to quantum computing.

US military exchanges data via UPS now

>>4256046
Look up quantum computers and start using steganography.

>>4256059
> There aren't any practical quantum computers that can handle more than like 8 bits yet
> D-wave is still half-assed

>>4256064
Look up email of previous poster.

Quantum cryptography will keep pace with quantum computers, nothing to worry about.

>>4256064
>implying the government isn't at least a half-decade ahead of the general populace in terms of technology

>>4256102
Indeed. We had some kind of cryptography conference / lecture in which the researcher told us that when, at a cryptography meeting, a colleague first demonstrated the use of entropy based approaches to detect messages in cryptography, a guy from the NSA basically let everybody understand (by asking clever questions) that the NSA already had the hang on that for quite some time...

>>4256012
yes but it works by eliminating all the composite numbers (so its too inefficient)

>>4256035

Your suggested algorithm is just a test for primality. It has no predictive power.

How can it be random?

Like, if you have a prime number, the probability of n+2 also being prime is very high.

I havent taken number theory yet (but I dearly hope to one day!) but a math bro told me once about some theorem that accurately predicts whether or not a number will be prime.

I am under the impression there is reason behind the distribution of primes. That reason is yet discovered.

>>4256344
There is no way to predict which numbers are primes. You've got to go through every number and test it. The only test is to check if its divisible by every other number. There are a few tricks to make this faster. Obviously primes other than 2 can't be even and for every X you don't need to check if a number greater than X/2 can divide it evenly, but it is still an enormously lengthy task that gets longer the larger the number is.

Modern encryption/decryption algorithms rely on this principle to make brute force decryption impossible. To decrypt a message a computer must calculate primes, and since this can't be done quickly it takes an extremely long time, making it effectively impossible to try trillions of passwords until you get the right one.

>>4255987

What you state there is not a proof.

If, for instance, you mulitiply 2 * 3 * 5 * 7 * 11 you get 2310. Adding 1 gives you 2311. Allthough 2311 might be a prime, it is an insufficient proof to claim it is so because it can not be divided divided by 2, 3, 5, 7 or 11. You also have to prove it can not be divided by 13, 17, 19 and so on.

>>4257777
Yeah, people often misunderstand that proof. What he should have said is that it means that there's a prime number strictly above 11. Either it's 2*3*5*7*11+1, or it's something else strictly between 11 and that big number. Repeat. QED.

>>4256326
Tell me what input and what output a "predictive" algorithm must have. I believe it's the same as what my algorithm takes. You can't really criticize the way the work is done, as long as it's done.

>>4257799
>Yeah, people often misunderstand that proof. What he should have said is that it means that there's a prime number strictly above 11.

And you seem to have misunderstood it as well. The number doesn't necessarily have to be above 11 as there are finite sets of primes where the product plus 1 is divisible by a prime smaller than the largest one of the finite set. In any case what he wrote is definitely wrong since 2*3*5*7*11*13=59*509. The correct way to state it (and the way Euclid originally did it) is to say that for any finite set of prime numbers there is, by considering their product plus 1, a prime number which is not one of those. Hence there must be infinitely many prime numbers. No repetition, no contradiction, no induction.

>>4257815
Oops, forgot a +1 at the counter example.

>>4255966
you can't know the distribution until you've counted all the primes
there is formula for finding n-th prime number
so when thing go to infinity the distribution will become undefined

>>4257815
Hmm, I see what you mean. If I take 2*7+1=15, it's divisible by 3 and 5. That works because 2*7 isn't the set of the first 2 primes, and because even if I only take the first primes at some point, if I do an induction, I might add to my set a prime that isn't the next prime.

However, you're right, induction isn't required. And therefore, my argument isn't totally crap if you remove the stupid induction step (which is more of a problem in my proof than the fact that the new prime is above or below the highest prime that you had before, I think).

>>4257850
I'm glad you agree. The essential idea of the proof is there, it's just that too many people restate Euclids original proof as a proof by induction or contradiction which just adds unnecessary complications considering the direct and straightforward nature of the true original statement. It's simply a matter of taste, but I can assure you that every professor likes students who know the tasteful difference.

The distribution of primes in the set of integers shows tantalizing patterns. This suggests there's a generator or algorithm for producing a prime. We've yet to find it. Some suggest that it's a false patterning hence it's really a random process. False patterning is possible, yet the definition of a prime continues to dangle in front of our noses that there *must* be a generator.

It's one of mathematics' great questions. It seems easy to investigate, yet finding the answer is apparently too difficult. Answer it and your name will be historically eternal.

>>4257799
>>4257815

Sweet - with those additions it start to make more sense and to look a lot more like a proof. I had never seen it before, so thanx for the info!

Nope. There is a system of 27 inequalities or something that returns all the primes.

pic not related

>>4257898

>citation needed

>>4257915
>skeleton_will_deliever.jpg

>>4256012
>>4256012

What if the algorithm's feasability is not related to the primes?
That's like saying if something does not glow, that it can't.

Because cities didn't exist and they seem unnatural by the 1 in 100000000000000 chance that humans evolved and created them doesn't mean they don't.

>>4257927
>>4257924
>>4257915
>>4257898

A system of 14 Diophantine equations in 26 variables can be used to obtain a Diophantine representation of the set of all primes. Jones et al. (1976) proved that a given number k + 2 is prime if and only if the following system of 14 Diophantine equations has a solution in the natural numbers:

http://en.wikipedia.org/wiki/Formula_for_primes

>>4257915
he probably means http://en.wikipedia.org/wiki/Formula_for_primes

it seems like the primes have a pseudorandom distribution

If the distribution of any set of primes is predictable, than the set of all the primes cannot be completely random.