Binary representtion of prime numbers

For discussions about programming, programming questions/advice, and projects that don't really have anything to do with Puppy.
Post Reply
Message
Author
User avatar
mahaju
Posts: 487
Joined: Mon 11 Oct 2010, 07:11
Location: between the keyboard and the chair

Binary representtion of prime numbers

#1 Post by mahaju »

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/SimilarQuest ... 0101+prime

http://anjackson.net/2007/07/19/visuali ... _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
:)

Jasper

#2 Post by Jasper »

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).

User avatar
Moose On The Loose
Posts: 965
Joined: Thu 24 Feb 2011, 14:54

Re: Binary representtion of prime numbers

#3 Post by Moose On The Loose »

mahaju wrote: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/SimilarQuest ... 0101+prime

http://anjackson.net/2007/07/19/visuali ... _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
:)
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.

User avatar
Flash
Official Dog Handler
Posts: 13071
Joined: Wed 04 May 2005, 16:04
Location: Arizona USA

#4 Post by Flash »

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

User avatar
mahaju
Posts: 487
Joined: Mon 11 Oct 2010, 07:11
Location: between the keyboard and the chair

#5 Post by mahaju »

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

Jasper

#6 Post by Jasper »

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

User avatar
Moose On The Loose
Posts: 965
Joined: Thu 24 Feb 2011, 14:54

#7 Post by Moose On The Loose »

Flash wrote:Even numbers (ending in 0, 2, 4, 6, 8) cannot be primes, so right there you cut your work in half. :lol:
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

:idea:

User avatar
lwill
Posts: 171
Joined: Fri 13 Jun 2008, 04:00
Location: City Of Lights
Contact:

#8 Post by lwill »

2 IS prime

Jasper

#9 Post by Jasper »

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

bugman

#10 Post by bugman »

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

bugman

#11 Post by bugman »

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

Post Reply