Half a croissant, on a plate, with a sign in front of it saying '50c'
h a l f b a k e r y
It's the thought that counts.

idea: add, search, annotate, link, view, overview, recent, by name, random

meta: news, help, about, links, report a problem

account: browse anonymously, or get an account and write.

user:
pass:
register,


             

Please log in.
Before you can vote, you need to register. Please log in or create an account.

Binary pattern heuristic for finding gigantic primes
 
(0) 		  [vote for,
against]

Find large primes with the help of a binary pattern.

Binary numbers: 101, 1101, 11101,111101, 1111111101 ,11111111111111111111111111101 all share two things. They all end in 101 and they are also all prime.

Note that this doesn't always hold. 1111101 is not a prime, but for primes <=509 this holds 85% of the time. That has to be useful as a heuristic.

(As you can tell I'm not, a mathematician)

—ixnaum, Sep 22 2014

Prime Numbers https://www.youtube...watch?v=Yhlv5Aeuo_k
Vi Hart is cool... [RayfordSteele, Sep 22 2014]

[link]






       Primes will always end in 1 in binary. Note that 11 is prime and is 1011, which breaks your pattern.
—RayfordSteele, Sep 22 2014
   

       //for primes <=509 this holds 85% of the time. That has to be useful as a heuristic.//   

       Are you saying that 85% of primes =<509 are of the form [1]n01?   

       This does not mean that 85% of numbers of the form [1]n01 are prime.   

       The numbers you describe are of the form 2^n-3.   

       For the first 10 such numbers (starting with n=3), 6 are prime. For the next 10, only 3 are prime. For the next 10, only 2 are prime. For the next _30_, none is prime.   

       Overall, of the first 60 such numbers (the largest being about 4,600,000,000,000,000,000), only 11 are prime, the highest such prime being only 536,870,909.   

       Nice idea, and neat observation, but it's not likely to be an efficient way of finding large primes, sadly. It might be more efficient than just testing all odd numbers, but it's likely to be much less efficient than testing, say, Mersenne numbers.
—MaxwellBuchanan, Sep 22 2014
   

       //Primes will always end in 1 in binary.//
This is equivalent to saying "Primes never end in 0 in binary", which is the case for every base.
—neutrinos_shadow, Sep 22 2014
   

       I'm not saying all primes follow this pattern. I was claiming that binary numbers with this pattern are likely to be prime.
—ixnaum, Sep 22 2014
   

       This works for base 10 numbers, too! If it ends in 1,3,5,7, or 9, it might be prime.   

       For simplicity, rewrite the number in binary. If it ends in 1, it might be prime.
—sninctown, Sep 22 2014
   
      
[annotate]
   


 

back: main index
business  computer  culture  fashion  food  halfbakery  home  other  product  public  science  sport  vehicle