7 ms·
The last line of the picture contains some 'noise': 0000000000000000000000000000000000000000000000000001000101101001 So the idea is that you produce any 63x64
by theaeolist 9y ago
The last line of the picture contains some 'noise':
0000000000000000000000000000000000000000000000000001000101101001
So the idea is that you produce any 63x64 binary image then you find a number up to 2^64 so that added to the number represented by the first image gives a prime. It's not exactly amazing, but clever enough.
- szemet 9y agoOr you can move the image on canvases of different size until you find a position/size where it is prime. Several other methods can work... Primes are not rare at all - average prime gaps are fairly small in that domain...
- krisives 9y agoIsn't the largest gap for any prime sqrt(n) ?
- phkahler 9y agonot even close. the average gap is closer to log(n).
- tromp 9y agowhere 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 agoAny log base is just a multiple of the natural log. When you talk about asymptotic growth, those factors are irrelevant.
- dvanduzer 9y agoIt 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 agoln 2⁶⁴ⁿ > 2⁶⁴ 64n × ln 2 > 2⁶⁴ n > 2⁵⁸ ∕ (ln 2) ≈ 4.2E+17
- chrismorgan 9y agoSuch 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 agoChanged * to × (U+00D7 MULTIPLICATION SIGN) and / to ∕ (U+2215 DIVISION SLASH). I don't like ÷, and I can't be bothered about whitespace. Sorry!
- qmalzp 9y agoThe 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.
- jules 9y agoI don't see why that would work. If the last digit is 0 then the number is not prime. Even if you make the bottom right corner a 1, it is not clear to me that any image will give a prime for sufficiently large canvas. The reason the original method works is that the density of primes around n is roughly 1/log n, so there are lots of primes around. If your image has k pixels the density is approx 1/k, so you'd only have to change the last log k pixels on average.
- tgb 9y agoI'm just disappointed that the noise isn't hidden in the pattern on the giraffe.
- dahart 9y ago> The last line of the picture contains some 'noise' Note that if the picture is prime, then the last line must always contain noise... the last digit must be a 1! I also feel like it's slightly cheating that the first line doesn't contain noise, or a leading 1 digit... the number doesn't naturally fit into 64x64 bits because of all the leading zeroes.
- ThrustVectoring 9y agoIf you "draw" with zeros instead of ones, then you don't have the last-digit-in-foreground problem.
- wakamoleguy 9y agoIt also solves the leading zeros problem. That's potentially a lot of extra computation to handle, though, since the resulting number in the giraffe case would be something like 2^500 times larger. I guess the question of whether that is worth it depends on your individual value for image shaped primes.
- deleted 9y ago[deleted]
- llamaz 9y agoThat may have been how the author came up with a prime number, but any extremely large odd number is probably prime, since the primes get further and further apart as you go further along the number line. So it may have been a lucky guess.
- Jeff_Brown 9y agoThis logic is backward. If you want empirical evidence you can ask WolframAlpha: There are 25 primes in [1, 100]. There are 16 in [1001, 1100]. There are 6 in [1000001, 1000100].
- deleted 9y ago[deleted]
- llamaz 9y agoI agree with your example, and it's what I said. But you're right, I'm wrong. By my own reasoning, any large odd number is likely to be composite. I must have been tired when I wrote my reply.