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 n-1, 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 n-1 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: 778
|
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: 12813 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: 778
|
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: 173 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^51-1 = 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^51-1 = 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
|
|
 |
|