4 ms·

Isn't the largest gap for any prime sqrt(n) ?

by krisives 9y ago

phkahler 9y ago
not even close. the average gap is closer to log(n).
- tromp 9y ago
  where log(n) is the natural logarithm of n https://en.wikipedia.org/wiki/Prime_number_theorem https://en.wikipedia.org/wiki/Prime_number_theorem
  - goldenkey 9y ago
    Any log base is just a multiple of the natural log. When you talk about asymptotic growth, those factors are irrelevant.
    - dvanduzer 9y ago
      It wasn't clear to me that the problem as framed was about asymptotic growth. I was curious if/when the factors might become relevant, so I started sketching this out... The 63x64 binary canvas is made of integers on the order of 2^4032. (Please forgive my approximation notation.) ln(2^4032) ~= 2795 log_10(2^4032) ~= 1214 So, the difference between natural log (for this canvas size) and log base 10 is only one binary digit (min 11, max 12). The "noise" you need to introduce to the image will definitely keep to the bottom right corner. So, I'm curious how tall the phone-width image needs to be before the required noise exceeds 64 bits (aka a single row). And the answer is... Too tall to be calculated quickly with my brute force method of "try bigger numbers until you get too impatient to wait for your desktop to calculate the natural log". I'm sure if I spent enough time drawing the parameters out, I'd eventually agree that there's no representation of this problem where those factors ever become relevant. BUT. If the problem we were calculating involved log base 1.0001 instead of the natural log, those factors would become relevant at much smaller canvas sizes. I would love to hear an intuitive explanation of logarithms that would convince me to not bother making calculations like this in the future!
      - jwilk 9y ago
        ln 2⁶⁴ⁿ > 2⁶⁴ 64n × ln 2 > 2⁶⁴ n > 2⁵⁸ ∕ (ln 2) ≈ 4.2E+17
        chrismorgan 9y ago
        Such beautiful superscripts and ≈, but then you used * and / instead of × and ÷… I like to also put plenty of THIN SPACE ( ) in to give it space to breathe, e.g. 2 ⁶⁴ ⁿ and 64 n instead of 2⁶⁴ⁿ and 64n. I make my thin spaces with Compose+Space+'.
        jwilk 9y ago
        Changed * to × (U+00D7 MULTIPLICATION SIGN) and / to ∕ (U+2215 DIVISION SLASH). I don't like ÷, and I can't be bothered about whitespace. Sorry!
        chrismorgan 9y ago
        I always forget about DIVISION SLASH and that it’s a thing, distinct from FRACTION SLASH (which I use regularly). I wonder if I should add it to my compose key. Nah, I think ÷ and FRACTION SLASH are enough for me.
        dvanduzer 9y ago
        Thank you for writing out that extremely clear sequence of inequalities. I love a good Unicode style debate, but regardless you absolutely nailed it with conceptual clarity.
        tzs 9y ago
        THIN SPACE (U+2009) is also good to use to group digits, and is in fact the standard way to group digits in the SI system instead of "," or ".". That looks nice and gets rid of the confusion over number like "1,234" and "1.234". In the US, the former is the integer 1234 and the later is the rational number 1234/1000. In Germany or France, these would be the other way around. In SI, "1.234" and "1,234" would both be 1234/1000, and the integer 1234 would be "1 234" with the space there being a thin space. Unfortunately, HN does not support THIN SPACE as far as I can tell. Reddit is a little better. You can enter it in a comment and it will be correctly saved with the comment and it will display correctly in the browser. As long as you don't need to make any edits to your comment afterwards, it is fine. If you edit the comment thin spaces are converted to regular spaces when it loads the editing widget, so unless you go through and put all the thin spaces back you will lose them when you save.
    - somecontext 9y ago
      In computational complexity, one typically ignores multiplicative constants, but in number theory, one often doesn't. The prime number theorem is of this stronger form, and it is in fact only the natural logarithm that makes the usual statement true. It is considerably more difficult to prove this asymptotic result (first proven 1896) than to get "within a multiplicative constant" as in big-O notation (first proven 1848--50).
- qmalzp 9y ago
  The average gap is log(n), but the maximal gap is not well understood. According to https://en.wikipedia.org/wiki/Cram%C3%A9r%27s_conjecture https://en.wikipedia.org/wiki/Cram%C3%A9r%27s_conjecture, current results are Unconditional: n^0.525 Conditional on RH: log(n)*sqrt(n) Conjecturally: log(n)^2
  - chx 9y ago
    > It is still probably true that for every constant {\displaystyle c>2} c>2, there is a constant {\displaystyle d>0} d>0 such that there is a prime between {\displaystyle x} x and {\displaystyle x+d(\log x)^{c}} {\displaystyle x+d(\log x)^{c}} That's quite fascinating.

Isn't the largest gap for any prime sqrt(n) ?

phkahler 9y ago

not even close. the average gap is closer to log(n).

tromp 9y ago
where log(n) is the natural logarithm of n https://en.wikipedia.org/wiki/Prime_number_theorem https://en.wikipedia.org/wiki/Prime_number_theorem
- goldenkey 9y ago
  Any log base is just a multiple of the natural log. When you talk about asymptotic growth, those factors are irrelevant.
  - dvanduzer 9y ago
    It wasn't clear to me that the problem as framed was about asymptotic growth. I was curious if/when the factors might become relevant, so I started sketching this out... The 63x64 binary canvas is made of integers on the order of 2^4032. (Please forgive my approximation notation.) ln(2^4032) ~= 2795 log_10(2^4032) ~= 1214 So, the difference between natural log (for this canvas size) and log base 10 is only one binary digit (min 11, max 12). The "noise" you need to introduce to the image will definitely keep to the bottom right corner. So, I'm curious how tall the phone-width image needs to be before the required noise exceeds 64 bits (aka a single row). And the answer is... Too tall to be calculated quickly with my brute force method of "try bigger numbers until you get too impatient to wait for your desktop to calculate the natural log". I'm sure if I spent enough time drawing the parameters out, I'd eventually agree that there's no representation of this problem where those factors ever become relevant. BUT. If the problem we were calculating involved log base 1.0001 instead of the natural log, those factors would become relevant at much smaller canvas sizes. I would love to hear an intuitive explanation of logarithms that would convince me to not bother making calculations like this in the future!
    - jwilk 9y ago
      ln 2⁶⁴ⁿ > 2⁶⁴ 64n × ln 2 > 2⁶⁴ n > 2⁵⁸ ∕ (ln 2) ≈ 4.2E+17
      - chrismorgan 9y ago
        Such beautiful superscripts and ≈, but then you used * and / instead of × and ÷… I like to also put plenty of THIN SPACE ( ) in to give it space to breathe, e.g. 2 ⁶⁴ ⁿ and 64 n instead of 2⁶⁴ⁿ and 64n. I make my thin spaces with Compose+Space+'.
        jwilk 9y ago
        Changed * to × (U+00D7 MULTIPLICATION SIGN) and / to ∕ (U+2215 DIVISION SLASH). I don't like ÷, and I can't be bothered about whitespace. Sorry!
        chrismorgan 9y ago
        I always forget about DIVISION SLASH and that it’s a thing, distinct from FRACTION SLASH (which I use regularly). I wonder if I should add it to my compose key. Nah, I think ÷ and FRACTION SLASH are enough for me.
        dvanduzer 9y ago
        Thank you for writing out that extremely clear sequence of inequalities. I love a good Unicode style debate, but regardless you absolutely nailed it with conceptual clarity.
        tzs 9y ago
        THIN SPACE (U+2009) is also good to use to group digits, and is in fact the standard way to group digits in the SI system instead of "," or ".". That looks nice and gets rid of the confusion over number like "1,234" and "1.234". In the US, the former is the integer 1234 and the later is the rational number 1234/1000. In Germany or France, these would be the other way around. In SI, "1.234" and "1,234" would both be 1234/1000, and the integer 1234 would be "1 234" with the space there being a thin space. Unfortunately, HN does not support THIN SPACE as far as I can tell. Reddit is a little better. You can enter it in a comment and it will be correctly saved with the comment and it will display correctly in the browser. As long as you don't need to make any edits to your comment afterwards, it is fine. If you edit the comment thin spaces are converted to regular spaces when it loads the editing widget, so unless you go through and put all the thin spaces back you will lose them when you save.
  - somecontext 9y ago
    In computational complexity, one typically ignores multiplicative constants, but in number theory, one often doesn't. The prime number theorem is of this stronger form, and it is in fact only the natural logarithm that makes the usual statement true. It is considerably more difficult to prove this asymptotic result (first proven 1896) than to get "within a multiplicative constant" as in big-O notation (first proven 1848--50).
qmalzp 9y ago
The average gap is log(n), but the maximal gap is not well understood. According to https://en.wikipedia.org/wiki/Cram%C3%A9r%27s_conjecture https://en.wikipedia.org/wiki/Cram%C3%A9r%27s_conjecture, current results are Unconditional: n^0.525 Conditional on RH: log(n)*sqrt(n) Conjecturally: log(n)^2
- chx 9y ago
  > It is still probably true that for every constant {\displaystyle c>2} c>2, there is a constant {\displaystyle d>0} d>0 such that there is a prime between {\displaystyle x} x and {\displaystyle x+d(\log x)^{c}} {\displaystyle x+d(\log x)^{c}} That's quite fascinating.