News for hackers. Stuff that matters.

A comment on A prime number whose binary representation looks like a giraffe. Parent comment

Re:A prime number whose binary representation looks like a g... by mkl on Saturday January 20, 2018 @05:50AM (#16192922)
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

[ Parent | on HN ]
Re:A prime number whose binary representation looks like a g... by Smaug123 on Saturday January 20, 2018 @06:01AM (#16192946)
It is provably prime; I got Mathematica to generate a certificate for it in about five minutes using `PrimeQCertificate`.
[ Parent | on HN ]
Re:A prime number whose binary representation looks like a g... by phkahler on Saturday January 20, 2018 @07:38AM (#16193140)
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.
[ Parent | on HN ]
Re:A prime number whose binary representation looks like a g... by SAI_Peregrinus on Saturday January 20, 2018 @10:16AM (#16193604)
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.
[ Parent | on HN ]
Re:A prime number whose binary representation looks like a g... by YomiK on Monday January 22, 2018 @02:20PM (#16207077)
"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.
[ Parent | on HN ]
Re:A prime number whose binary representation looks like a g... by YomiK on Monday January 22, 2018 @02:19PM (#16207066)
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.
[ Parent | on HN ]
Re:A prime number whose binary representation looks like a g... by jdnier on Saturday January 20, 2018 @03:41PM (#16195300)
Playing 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
[ Parent | on HN ]
Re:A prime number whose binary representation looks like a g... by jdnier on Saturday January 20, 2018 @03:50PM (#16195355)
Nice results at 192 (also three giraffes) and at 256 (four giraffes).
[ Parent | on HN ]