Author |
Topic: count numbers that have prime # of bits set (Read 481 times) |
|
inexorable
Full Member
Posts: 211
|
 |
count numbers that have prime # of bits set
« on: Oct 24th, 2007, 4:32pm » |
 Quote  Modify
|
consider a function P(x) where:
P(x) returns:
true if the number of 1 bits set in the
binary representation of x is prime,
false otherwise.
For example, P(239) returns true, while P(51) returns false.
Next, consider the following function prime_bits:
uint64_t prime_bits(uint64_t a, uint64_t b);
A call to prime_bits(a, b) returns the number of values between a and b inclusive for which P(x) is true. For example, prime_bits(4, 10) returns 5, while prime_bits(137, 31415926535897) returns 7753256197126.
How do you implement prime_bits(a,b) such that its running time is faster than O(n) where n=b-a ?
|
| « Last Edit: Oct 24th, 2007, 5:12pm by inexorable » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: count numbers that have prime # of bits
« Reply #1 on: Oct 25th, 2007, 2:29am » |
Quote Modify
|
I'd look up the previous thread on the subject before implementing it..
In any case, you'd use combinatorics.
|
| « Last Edit: Oct 25th, 2007, 2:35am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print