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 Wed 20 Aug 2014, 08:41
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 Posts_count  
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: 1107
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: 513

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: 11012
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: 1107
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: 513

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_website 
Jasper


Joined: 25 Apr 2010
Posts: 1107
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_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_website 
Display_posts:   Sort by:   
Page 1 of 1 Posts_count  
Post_new_topic   Reply_to_topic View_previous_topic :: View_next_topic
 Forum index » Off-Topic Area » Programming
Jump to:  

Rules_post_cannot
Rules_reply_cannot
Rules_edit_cannot
Rules_delete_cannot
Rules_vote_cannot
You cannot attach files in this forum
You can download files in this forum


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0648s ][ Queries: 11 (0.0032s) ][ GZIP on ]