Author 
Message 
mahaju
Joined: 11 Oct 2010 Posts: 491 Location: between the keyboard and the chair

Posted: Thu 03 Mar 2011, 22:31 Post subject:
Binary representtion of prime numbers 

Is there any way to check whether a number is prime from it's binary representation? And I do not mean the classical method of dividing the number n by numbers from 2 to n1, but actually determining if it is a prime from it's patterns of 0's and 1's.
Here are some of the related things I have found
http://askville.amazon.com/SimilarQuestions.do?req=binary+numbers+form+101+10101+1010101+prime
http://anjackson.net/2007/07/19/visualising_prime_numbers_in_binary
If there is any such method I would like to write a program in C or C++ to determine if a number is prime by using it's binary representation
Thanks in advance

Back to top



Jasper
Joined: 25 Apr 2010 Posts: 1350 Location: England

Posted: Thu 03 Mar 2011, 22:44 Post subject:


Hi,
Categorically not.
Type:
factor x
into your console/terminal where x can be any positive integer (though I don't know how large) to factorize x.
The largest known prime has almost 13,000,000 decimal digits. Note that the number 13,000,000 has only 8 decimal digits.
The natural log of that number is almost 30,000,000 which means that is the average distance between the primes.
My regards
PS It is only necessary to test to the square root of n (not n1 and since 2 is the only even prime number it is only necessary to test odd integers).

Back to top



Moose On The Loose
Joined: 24 Feb 2011 Posts: 643

Posted: Fri 04 Mar 2011, 00:13 Post subject:
Re: Binary representtion of prime numbers 

For speed you need a quantum computer.
Finding out whether or not a number is prime can be done a lot faster than the trial and error divide method but the amount it is faster by is a nearly constant factor so for really big values it only takes twice the life of the universe instead of 3 times.
If you are limited to a 32 bit value, life gets a lot easier. You only need to remember the primes from 1 to 65536 and try them against your number under test. This can be quick.

Back to top



Flash
Official Dog Handler
Joined: 04 May 2005 Posts: 12015 Location: Arizona USA

Posted: Fri 04 Mar 2011, 00:57 Post subject:


Even numbers (ending in 0, 2, 4, 6, cannot be primes, so right there you cut your work in half.

Back to top



mahaju
Joined: 11 Oct 2010 Posts: 491 Location: between the keyboard and the chair

Posted: Fri 04 Mar 2011, 02:48 Post subject:


I agree that even numbers cannot be prime, but this doesn't actually cut my work in half
because it only tells me about the LSB
If my number is, say, 10 bits long then I don't think it much reduces my work

Back to top



Jasper
Joined: 25 Apr 2010 Posts: 1350 Location: England

Posted: Fri 04 Mar 2011, 08:21 Post subject:


Hi again,
There are types of primes with special characteristics e.g. Fermat primes of which only 5 are known and Mersenne primes of which only some 50 are known.
There are classic theorems e.g, The Prime Number Theorem and Proth's Theorem and The Proof of the Infinity of the Primes attributed to Euclid which is brilliant but simple.
For an exercise in computer programming the Sieve of Eratosthenes would take very few lines of code. 22 short lines from memory when I wrote a program in GWBasic some 30 years ago  the principle is simple.
My regards

Back to top



Moose On The Loose
Joined: 24 Feb 2011 Posts: 643

Posted: Fri 04 Mar 2011, 11:04 Post subject:


Flash wrote:  Even numbers (ending in 0, 2, 4, 6, cannot be primes, so right there you cut your work in half. 
I think you will also find that if the sum of the bytes in the number can be divided by 51, the number can be divided by 51. Someone who has already had their morning coffee should check this

Back to top



lwill
Joined: 13 Jun 2008 Posts: 174 Location: City Of Lights

Posted: Fri 04 Mar 2011, 15:01 Post subject:


2 IS prime

Back to top



Jasper
Joined: 25 Apr 2010 Posts: 1350 Location: England

Posted: Fri 04 Mar 2011, 15:08 Post subject:


Hi,
Re: the "51" conjecture above
Type into a console:
factor 2251799813685247
and you will see its prime factors are:
7 103 2143 11119 and 131071
The 51 digit binary number consisting entirely of 1's = 2^511 = 2,251,799,813,685,247
My regards

Back to top



bugman
Joined: 20 Dec 2005 Posts: 2131 Location: buffalo commons

Posted: Sat 05 Mar 2011, 09:50 Post subject:


Moose On The Loose wrote:  I think you will also find that if the sum of the bytes in the number can be divided by 51, the number can be divided by 51. Someone who has already had their morning coffee should check this 
it's 3 you're thinking of
the set of which includes 51, natch
_________________ . . . the machines are clean
and the machines are not corrupted
 lee "scratch" perry

Back to top



bugman
Joined: 20 Dec 2005 Posts: 2131 Location: buffalo commons

Posted: Sat 05 Mar 2011, 09:51 Post subject:


Jasper wrote:  The 51 digit binary number consisting entirely of 1's = 2^511 = 2,251,799,813,685,247 
this you know if you do rgb coding
ffcc99
etc
god bless 17 and all who sail on her
_________________ . . . the machines are clean
and the machines are not corrupted
 lee "scratch" perry

Back to top



