# Difference between revisions of "Cramer's conjecture"

From Polymath Wiki

Line 1: | Line 1: | ||

'''Cramér's conjecture''' asserts that the largest gap between adjacent primes of size N should be <math>O(\log^2 N)</math>. This is compatible with [[Cramer's random model for the primes]], and specifically with the belief that the number of primes in <math>[n,n+\log n]</math> should resemble a Poisson distribution asymptotically. | '''Cramér's conjecture''' asserts that the largest gap between adjacent primes of size N should be <math>O(\log^2 N)</math>. This is compatible with [[Cramer's random model for the primes]], and specifically with the belief that the number of primes in <math>[n,n+\log n]</math> should resemble a Poisson distribution asymptotically. | ||

− | If this conjecture is true, one has an easy positive answer to the [[finding primes]] project in the strongest form; one simply searches an interval of the form <math>[N, N+O(\log^2 N)]</math> for primes, where N is your favourite k-digit number. | + | If this conjecture is true, one has an [[An efficient algorithm exists if Cramer's conjecture holds|easy positive answer]] to the [[finding primes]] project in the strongest form; one simply searches an interval of the form <math>[N, N+O(\log^2 N)]</math> for primes, where N is your favourite k-digit number. |

− | # [[wikipedia:Cramér's_conjecture|Wikipedia entry on Cramér' | + | # [[wikipedia:Cramér's_conjecture|Wikipedia entry on Cramér's conjecture]] |

## Latest revision as of 01:10, 20 August 2009

**Cramér's conjecture** asserts that the largest gap between adjacent primes of size N should be [math]O(\log^2 N)[/math]. This is compatible with Cramer's random model for the primes, and specifically with the belief that the number of primes in [math][n,n+\log n][/math] should resemble a Poisson distribution asymptotically.

If this conjecture is true, one has an easy positive answer to the finding primes project in the strongest form; one simply searches an interval of the form [math][N, N+O(\log^2 N)][/math] for primes, where N is your favourite k-digit number.