Puppy Linux Discussion Forum Forum Index Puppy Linux Discussion Forum
Puppy HOME page : puppylinux.com
"THE" alternative forum : puppylinux.info
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

The time now is Sat 26 Jul 2014, 03:13
All times are UTC - 4
 Forum index » Off-Topic Area » Programming
Binary representtion of prime numbers
Post new topic   Reply to topic View previous topic :: View next topic
Page 1 of 1 [11 Posts]  
Author Message
mahaju


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

PostPosted: 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
Smile
Back to top
View user's profile Send private message 
Jasper


Joined: 25 Apr 2010
Posts: 1087
Location: England

PostPosted: 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
View user's profile Send private message 
Moose On The Loose


Joined: 24 Feb 2011
Posts: 508

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

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/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
Smile


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
View user's profile Send private message 
Flash
Official Dog Handler


Joined: 04 May 2005
Posts: 10931
Location: Arizona USA

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

Even numbers (ending in 0, 2, 4, 6, Cool cannot be primes, so right there you cut your work in half. Laughing
Back to top
View user's profile Send private message 
mahaju


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

PostPosted: 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
View user's profile Send private message 
Jasper


Joined: 25 Apr 2010
Posts: 1087
Location: England

PostPosted: 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
View user's profile Send private message 
Moose On The Loose


Joined: 24 Feb 2011
Posts: 508

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

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


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
Back to top
View user's profile Send private message 
lwill


Joined: 13 Jun 2008
Posts: 173
Location: City Of Lights

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

2 IS prime
Back to top
View user's profile Send private message Visit poster's website 
Jasper


Joined: 25 Apr 2010
Posts: 1087
Location: England

PostPosted: 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
View user's profile Send private message 
bugman


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

PostPosted: 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
View user's profile Send private message Visit poster's website 
bugman


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

PostPosted: 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
View user's profile Send private message Visit poster's website 
Display posts from previous:   Sort by:   
Page 1 of 1 [11 Posts]  
Post new topic   Reply to topic View previous topic :: View next topic
 Forum index » Off-Topic Area » Programming
Jump to:  

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0664s ][ Queries: 12 (0.0037s) ][ GZIP on ]