h a l f b a k e r y
add, search, annotate, link, view, overview, recent, by name, random
news, help, about, links, report a problem
or get an account
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)
Vi Hart is cool... [RayfordSteele, Sep 22 2014]
Please log in.
If you're not logged in,
you can see what this page
looks like, but you will
not be able to add anything.
Description (displayed with the short name and URL.)
||Primes will always end in 1 in binary. Note that 11 is prime and is 1011, which breaks your pattern.
||//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
||This does not mean that 85% of numbers of the form
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
||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.
||//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.
||I'm not saying all primes follow this pattern. I was
claiming that binary numbers with this pattern are likely
to be prime.
||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.