wu :: forums - Print Page


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

        riddles >> putnam exam (pure math) >> binary
        
(Message started by: mad on Jul 31^st, 2007, 1:42pm)

Title: binary
Post by mad on Jul 31^st, 2007, 1:42pm

Let f(k) = y where k is the y-th number in the increasing sequence of non-negative integers with the same number of ones in its binary representation as y, e.g. f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 1, f(4) = 3, f(5) = 2, f(6) = 3 and so on. Given k >= 0, compute f(k).

Title: Re: binary
Post by towr on Jul 31^st, 2007, 2:26pm

I can't entirely understand the way you've phrased that..
Is f(k) an inverse function, because it seems k depends on y rather than vice versa.

Title: Re: binary
Post by Eigenray on Jul 31^st, 2007, 2:55pm

It's basically the "[link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1177951862]prime bits[/link]" problem. Except not necessarily prime.

(Inverse problem [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1144397342]here[/link] and [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1182493760]here[/link].)

Title: Re: binary
Post by towr on Jul 31^st, 2007, 3:03pm

Ah, f(k) is the count of nonnegative numbers http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gifk with the same number of bits set to one as k.
Now I understand it.

Title: Re: binary
Post by mad on Jul 31^st, 2007, 3:31pm

Eg.

1010
will come after
0011
0101
0110
1001
1010

So, it is the 5th number here.