Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A prime number whose binary representation looks like a giraffe

reddit.com

Post reply on HN
Print view View original

71–80 of 82 posts

Re: A prime number whose binary representation looks like a giraffe

#71

Post by somecontext »

goldenkey wrote: post #29
tromp wrote: post #24

Earlier quoted context omitted.

where log(n) is the natural logarithm of n https://en.wikipedia.org/wiki/Prime_number_theorem

Any log base is just a multiple of the natural log. When you talk about asymptotic growth, those factors are irrelevant.

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).

Re: A prime number whose binary representation looks like a giraffe

#72

Post by qualitytime »

qualitytime wrote: post #66
userbinator wrote: post #42

Great, another great demonstration of the fundamental principles of digital computing - representation and interpretation of data. It's been my experience teaching CS courses that many students, despite being taught bits and bytes and binary and ASCII and so forth, don't really "get it" until they see things like this. This particular one only looks like a giraffe when it's interpreted as a 1bpp big-endian bitmap, bu…

"write a short program that checks if a file is a prime number." What do you mean? I tried googling but failed.

Was that a downvote? For asking a question? Jeez.

Re: A prime number whose binary representation looks like a giraffe

#73

Post by [deleted] »

Jeff_Brown wrote: post #59
llamaz wrote: post #56

Earlier quoted context omitted.

That 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.

This 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]

Re: A prime number whose binary representation looks like a giraffe

#74

Post by llamaz »

Jeff_Brown wrote: post #59
llamaz wrote: post #56

Earlier quoted context omitted.

That 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.

This 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].

I 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.

Re: A prime number whose binary representation looks like a giraffe

#75

Post by chrismorgan »

tzs wrote: post #70
dbdr wrote: post #62

Earlier quoted context omitted.

Looks good with Firefox on Linux too. Given chrismorgan's comment about breaking, it seems that NARROW NO-BREAK SPACE would be a better choice for digit grouping, right?

Yeah, NARROW NO-BREAK SPACE is probably better. As far as the display problem on Firefox and Safari on Mac goes, I've done some experimenting. It looks like it is a font thing. HN has "font-family:Verdana, Geneva, sans-serif;" as part of the style sheet. I made a minimal test page with just the different space examples, and an internal style sheet that just set the font-family for the body, and it shows the problem.…

It’s common for fonts to not include glyphs for all the fancy spaces, which will leave it to a fallback mechanism where a different font is used.

It’s also common for web fonts especially to possess glyphs for some of the fancier spaces, but as duplicates of SPACE, i.e. the wrong size.

Face it: fonts (to a degree the technology, but mostly the actual fonts) are generally pretty bad.

Re: A prime number whose binary representation looks like a giraffe

#76

Post by colejohnson66 »

qualitytime wrote: post #66
userbinator wrote: post #42

Great, another great demonstration of the fundamental principles of digital computing - representation and interpretation of data. It's been my experience teaching CS courses that many students, despite being taught bits and bytes and binary and ASCII and so forth, don't really "get it" until they see things like this. This particular one only looks like a giraffe when it's interpreted as a 1bpp big-endian bitmap, bu…

"write a short program that checks if a file is a prime number." What do you mean? I tried googling but failed.

Hint: Interpret the file’s bits as a single number

Re: A prime number whose binary representation looks like a giraffe

#77

Post by qualitytime »

colejohnson66 wrote: post #76
qualitytime wrote: post #66

Earlier quoted context omitted.

"write a short program that checks if a file is a prime number." What do you mean? I tried googling but failed.

Hint: Interpret the file’s bits as a single number

Thanks for the clarification.

Re: A prime number whose binary representation looks like a giraffe

#78

Post by RiderOfGiraffes »

I guess I should comment here, but I don't have much to add. Most of the questions that arise naturally about how this was done, and about primes in general, have already been asked and answered.

Still, given my username I should add something ...

So if the size was prime x prime then the fact that the number of bits is a semi-prime tells you the size of the image, even if all you have is a stream of digits. Then the "noise" at the end will tell you what the least significant bits are, and hence you get an image without very much ambiguity.

Just thought I'd mention that.

Re: A prime number whose binary representation looks like a giraffe

#79

Post by YomiK »

mkl wrote: post #15
reificator wrote: post #10

I think the more interesting way to do this would be to create a border that's roughly circular to frame the giraffe, and fill that border with noise. Then do the incrementing thing, and your 12 or so bits of noise at the end will blend in better, making it harder for the average person to reverse engineer. I'm imaging something like this, but with a giraffe instead: https://6d4be195623157e28848-7697ece4918e0a73861de…

I had the same sort of idea, and just implemented it in Python using gmpy2 for the primality check. Here's a prime smiley face: 111010101111001000110101111111001001000010000 000000000000000000000000000000000000000000001 000000000000000001110111111100000000000000001 100000000000011110000000000011010000000000001 000000000011100000000000000000011100000000000 100000000100000000000000000000000011000000001 1000000110000000…

Pari/GP's APR-CL took 4 seconds to prove it. Perl's ntheory module took 2.6 seconds to prove with ECPP (including generating and verifying a certificate). That's over 1000x slower than BPSW but still not bad.

Re: A prime number whose binary representation looks like a giraffe

#80

Post by YomiK »

SAI_Peregrinus wrote: post #35
phkahler wrote: post #25

Earlier quoted context omitted.

Sometimes its a good idea to use a faster probable prime test when searching, and then use a slower test to verify the result. As has been done here.

Lenstra and Pomerace's variant of the AKS test is O(log(n)^6), and deterministic. So polynomial, and not a huge exponent. Still not as fast as the probabilistic algorithms, but not as slow as pre-AKS methods.

"not as slow as pre-AKS methods." only in terms of provable asymptotic bounds. It's much slower than APR-CL and ECPP, both of which existed before AKS, and are the methods used daily.
Post reply on HN