4 ms·
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: 1110101011110010001101011111
by mkl 9y ago
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
100000011000000000000000000000000000100000001
100000110000000001000000001000000000011000001
100000100000000001000000001000000000001100000
000001000000000001000000001000000000000100001
100010000000000001000000001000000000000010000
000010000000000001000000001000000000000010001
000010000000000001000000001000000000000010000
000010000000000000000000000000000000000010000
100010000001100000000000000000001100000010001
000001000000110000000000000000011000000100000
000000100000011000000000000000110000001100001
100000110000001111000000000111100000011000000
000000011000000001111111111100000000100000000
100000000100000000000000000000000011000000001
000000000011100000000000000000011100000000000
100000000000011110000000000011010000000000000
100000000000000001110111111100000000000000000
100000000000000000000000000000000000000000001
111011110010001011101100010110111111110011001
As a number, it's
418286130038247526051590581692998429049634527936177232676862400134230223310124567196900044669909574838414882468188159808593146618824409867113710174334769625185535031892647808338085451521099179358299885075661065903947563499117521951858387121272237585876050870984471996640946451287415573046990997289875221396633775785411121263373993999302553.
This took 487 random border attempts to find, which seems pretty small!
Note that efficient primality tests are probabilistic, so there's a small chance this isn't actually prime. I expect it's the same with the giraffe one in the link.
Edit: Here's the code (improved a bit over what made the picture above): https://gitlab.com/snippets/1694391 https://gitlab.com/snippets/1694391
- Smaug123 9y agoIt is provably prime; I got Mathematica to generate a certificate for it in about five minutes using `PrimeQCertificate`.
- phkahler 9y agoSometimes 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.
- SAI_Peregrinus 9y agoLenstra 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.
- YomiK 9y ago"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.
- jdnier 9y agoPlaying with the wrap width (in this case 94), you'll see a small herd of giraffes instead. (This is the prime from the reddit article, rather than your smiley face. Easier to see white on black.) 100000000000000000000000000000000000000000000000000000000000000110000000000000000000000000000000 000000000000000000000000000000111000000000000000000000000000000000000000000000000000000000000111 110000000000000000000000000000000000000000000000000000000000111111000000000000000000000000000000 000000000000000000000000000011111110000000000000000000000000000000000000000000000000000000011111 111000000000000000000000000000000000000000000000000000000001000011110000000000000000000000000000 000000000000000000000000000000000111000000000000000000000000000000000000000000000000000000000000 011110000000000000000000000000000000000000000000000000000000000000111100000000000000000000000000 000000000000000000000000000000000011110000000000000000000000000000000000000000000000000000000000 000111100000000000000000000000000000000000000000000000000000000000011111000000000000000000000000 000000000000000000000000000000000000111110000000000000000000000000000000000000000000000000000000 000011111100000000000000000000000000000000000000000000000000000000000111111100000000000000000000 000000000000000000000000000000000000011111111100000000000000000000000000000000000000000000000000 000000111111111100000000000000000000000000000000000000000000000000000011111111111000000000000000 000000000000000000000000000000000000000111111111111000000000000000000000000000000000000000000000 000000001111111111111100000000000000000000000000000000000000000000000000111111111111111100000000 000000000000000000000000000000000000000011111111111111111000000000000000000000000000000000000000 000000001111111111111111110000000000000000000000000000000000000000000000111111111111111111000000 000000000000000000000000000000000000000011111111111111111110000000000000000000000000000000000000 000000001111111111111111111000000000000000000000000000000000000000000000011111111111111111100000 000000000000000000000000000000000000000001111111111111111110000000000000000000000000000000000000 000000000111100001111111110000000000000000000000000000000000000000000000011110000011111111000000 000000000000000000000000000000000000000001111000000111111100000000000000000000000000000000000000 000000001111100000011111110000000000000000000000000000000000000000000000110110000000110111000000 000000000000000000000000000000000000000011011000000011101110000000000000000000000000000000000000 000000011001100000001110111000000000000000000000000000000000000000000001100110000000111001110000 000000000000000000000000000000000000000110011000000011100110000000000000000000000000000000000000 000000011001100000001100011000000000000000000000000000000000000000000000110010000000100001100000 000000000000000000000000000000000000000001001000000110000110000000000000000000000000000000000000 000000000011100000010000011000000000000000000000000000000000000000000000001110000011000001100000 000000000000000000000000000000000000000000011000011000000110000000000000000000000000000000000000 000000000001100001100000011000000000000000000000000000000000000000000000000111001100000001100000 000000000000000000000000000000000000000000011100110000000110000000000000000000000000000000000000 000000000001010011000000010000000000000000000000000000000000000000000000001100000000000011000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000001000101101001
- YomiK 9y agoPari/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.