wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> count  numbers that have prime # of bits set
        
(Message started by: inexorable on Oct 24^th, 2007, 4:32pm)

Title: count numbers that have prime # of bits set
Post by inexorable on Oct 24^th, 2007, 4:32pm

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 ?

Title: Re: count numbers that have prime # of bits
Post by towr on Oct 25^th, 2007, 2:29am

I'd look up the previous thread on the subject before implementing it..
In any case, you'd use combinatorics.