1

Imagine each natural number as a point in space along a path on which one can stand and walk. Imagine standing at any one point and looking forward toward the next prime. If we stand at $1$ and look forward, we see that the distance to the next prime is $1$. If we stand at $2$ and look forward, we see that the distance to the next prime is $1$. Let $n$ be any natural number. Let $m$ be the distance from $n$ to the next prime. According to Bertrand's postulate, $m<n$. I have strong reason to believe that $m<2\sqrt n$. We can use the squares of the primes as framework for navigating along the natural number line. I divided the natural number line into sections. I call $1$ and $2$ section $0$ because when $n$ is $1$ or $2$, the number of prime numbers which can affect the distance to the next prime is $0$. At $1$, $m=1$. At $2$, $m=1$.

Is there a mathematical expression for this? I use m because it is the first letter of the word maximum. I say, at $1$, $m=1$. At $2$, $m=1$. Is there already a symbol in use for the maximum distance from any given number n to the next prime? Should this be expressed as a function?

$m(1)=1$ $m$ of one equals one. $m(2)=1$ $m$ of two equals one. $m(3)=2$ $m(4)=2$ From $4$, you have to go no farther than $2$ to get to the next prime. $m(5)=2$ $m(6)=2$ $m(7)=4$

Marc van Leeuwen
  • 115,048
Jeffrey Young
  • 841
  • 1
    If you could express it with a function, you could build a function to compute prime numbers. Don't expect something easy to compute – Sylvain Biehler Sep 25 '14 at 08:13
  • Computing the "next" prime requires knowing all previous prime numbers and thus it is highly unlikely (probably impossible) to find the next prime given only the current number (or even the current prime number)...granted we can compute all previous primes given the current number, but that computation requires "a lot of work". The problem is that the number itself does not tell you the next prime. You really need to know all previous primes as well and computing all previous primes is as hard of a problem as computing the next prime. – Jared Sep 25 '14 at 08:17
  • @Jared No, computing the next prime does not require any knowledge of previous primes. – Erick Wong Sep 25 '14 at 08:32
  • I don't understand why you call it the "maximum distance". How is it different from just "distance"? This is similar to http://en.wikipedia.org/wiki/Prime_gap but parametrized a bit differently. – Erick Wong Sep 25 '14 at 08:35
  • @Erick Wong Good observation! This is something new. I just made this discovery this summer. At 1, m=1. At 2, m=1. At 3, m=2. At 4, m=2. At 5, m=2. At 6, m=2. At 7, m=4. At 8, m=4. At 9, m=4. At 10, m=4. At 11, m=4. At 12, m=4. At 13, m=4. This is maximum distance. It is different from actual distance. Adding m to n will take you slightly beyond the next prime most of the time, but never too far beyond the next prime, and every now and then the distance will be exact. – Jeffrey Young Sep 25 '14 at 13:32
  • @JeffreyYoung Thanks for this clarification. It wasn't obvious from the phrase "maximum distance from here" that you were asking about the maximum (of the prime gap function) over all values up to $m$. – Erick Wong Sep 25 '14 at 15:46
  • @ErickWong I don't see how computing the next prime doesn't require knowledge of previous primes. Let's take a very simple case such as $p = 7$. How do you go about computing that 11 is the next prime? In this particular case, you could argue that 2 and 3 create a period of $2\cdot3 = 6$ where every "1, 5" is prime, therefore above 6, 7 and 11 are the next prime candidates (then it will be 13 and 17, etc...until you get to $5^2 = 25$--which will incorrectly be "guessed" as a prime). But 1), I used knowledge of previous primes and 2) obviously this method breaks down after 7. – Jared Sep 26 '14 at 06:37
  • @Jared Please read the wikipedia article on primality testing http://en.wikipedia.org/wiki/Primality_test. There are exponentially faster ways to find the next prime than computing all previous primes. Sieving on a handful of smaller primes as you describe helps a lot, but those primes would be much, much smaller than the number you are starting from (a far cry from "all previous primes"). – Erick Wong Sep 26 '14 at 09:03
  • @ErickWong To make an analogy, it is like a sidewalk with square sections, each one having a number painted on it. Standing at 1, looking forward, you can see that the next prime is 1 space away. Standing at 2, looking forward, you can see that the next prime is 1 space away. Step forward to 3. Look forward one space and you see the square of 2. On the fourth square of the sidewalk, instead of only a 4 painted there, it says 4=2^2. At 6, it says, 6=2·3. At 8, it says, 8=2^3. So you can see that 2 as a prime factor is at every other point. "Here" refers to the point where are are looking from. – Jeffrey Young Sep 26 '14 at 14:55
  • @JeffreyYoung I think your question needs to be edited and clarified, because I don't see how this analogy adds anything. Your examples in the comments are the most illuminating. As far as I can see, you can't get $m=4$ at $12$ without looking backward at primes $7$ and $11$, as opposed to forward. It's the "maximum" process that you didn't explain (maximum over what?). – Erick Wong Sep 26 '14 at 17:04
  • @ErickWong You are right! I did make a big mistake in only saying to look forward. I did not mean that you cannot look back. I mean that when making a forward move from any natural number, there is a limit for how far you have to go to get to the next prime. To calculate that limit, the first step, I have reason to believe, is to find the square root of the number which you are starting from. – Jeffrey Young Sep 27 '14 at 00:27

1 Answers1

2

Legendre's conjecture says that for every $n$ there is a prime number between $n^2$ and $(n+1)^2$, which is very close to what you surmise (since $(n+1)^2-n^2=2n+1=2\sqrt{n^2}+1$). If true it would imply that the gap after a prime $p$ could be bounded by a constant times$~\sqrt p$; however neither the conjecture nor that consequence have been proved. Given the amount of effort that no doubt has gone into trying to prove this, you can be sure that (1) no counterexamples have been found, but also that (2) there exists no elementary proof that the prime gap after $p$ can be at most $2\sqrt p$. There is more information at the linked article

Marc van Leeuwen
  • 115,048
  • Ok. Now, according to Bertrand, m is related to n. I have found reason to believe that m is related to the section of the natural number line in which n is located. I have been able to define both the beginning point and the end point of each section. Just as 0 is the first whole number, the first section is section 0. Section 0 is 1 and 2. Here, m=1. Section 1 is 3,4,5, and 6. Here, m=2. Pi of the square root of 4 is 1, which is why I call it section 1. Section 2 begins at 7, the last prime before the square of 3, and ends at 22, 1 less than the last prime before the square of 5. – Jeffrey Young Sep 27 '14 at 06:08
  • 1
    The true size of maximum prime gaps is believed to behave as in Cramér's conjecture, which would be (very) roughly like $\log^2 n$. See also http://primes.utm.edu/notes/gaps.html – Erick Wong Sep 27 '14 at 07:16
  • @ErickWong: Thanks for that complement. But I hate the notation $\log^2 n$. Does it mean $(\log n)^2$ (as one would read $\sin^2 n$; it seems like this is the right one) or $\log(\log n)$ (as systematic notation would have it); both are sufficiently frequently occurring expressions to be plausible interpretations. – Marc van Leeuwen Sep 27 '14 at 08:15
  • @MarcvanLeeuwen I agree to some extent; it's just such a common idiom in analytic number theory that I didn't even notice. There one deals with a lot of nested logs and exponentiated logs, but the nested logs tend to be of fixed length, while exponents are often parametric (perhaps this is why the $(\log n)^2$ interpretation seems dominant from my perspective). I tend to draw the line at using "$\log \log^2 n$" which also adds associative ambiguity, but I'll immediately assume it means $(\log(\log n))^2$ if I see it. – Erick Wong Sep 27 '14 at 17:04