wu :: forums - Print Page


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

        riddles >> hard >> number Theory problem
        
(Message started by: LeoYard on Oct 23^rd, 2008, 3:48pm)

Title: number Theory problem
Post by LeoYard on Oct 23^rd, 2008, 3:48pm

When we write the integers from 1 through 10 (1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010) in base 2, we have to write the number "one" 17 times. How many "ones" are needed to list, in binary notation, the integers from 1 through 2001?

N.B. Notice that the powers of two -- 2, 4, 8, 16, etc. -- are represented in base two by 10, 100, 1000, 10000, and so on -- just as the powers of ten are in base ten notation.

Title: Re: number Theory problem
Post by Michael Dagg on Oct 23^rd, 2008, 4:52pm

Might seem hard but it really isn't. You asked for a
count of 1's for 1...2001 ; shortly someone will post
some code for this calculation that answers your
question.

It gets more interesting if you ask for a formula
for 1 to any N .

Title: Re: number Theory problem
Post by william wu on Oct 23^rd, 2008, 6:04pm

Perhaps this can give us a start: If you enumerate the numbers 0 through 2^n-1 in binary, the number of ones is n 2^n-1.

This is most easily seen by example. In the image we have the numbers 0 through 15 = 2⁴ - 1 in binary. If you look at each column of the table, exactly half of the entries are ones; hence the result.

Title: Re: number Theory problem
Post by Hippo on Oct 23^rd, 2008, 10:58pm

on 10/23/08 at 18:04:56, william wu wrote:

Idea is correct, but you mean numbers upto 2ⁿ-1 (and nhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gif2^n-1) ones.

BTW: I would vote for moving this to easy (at most medium) ... and the thread name is missleading :(

Title: Re: number Theory problem
Post by BenVitale on Oct 24^th, 2008, 11:20am

Well, if you go upto 2047 (11111111111) that is 11 binary digits, the number of "ones" is 11 * 2^(11-1) or 11 * 2^10 = 11,264 "ones"

Then, you could subtract the number of 1's from 2002 through 2047... but it would take some time and it's not very elegant. Imagine you have this problem on a test -- you would have only 15 minutes to solve this problem...you wouldn't be able to finish it on time!

Title: Re: number Theory problem
Post by warriors837 on May 24^th, 2009, 7:40pm

yea...tell me about it, i had it as a bonus in my AP Calc class this year, only 15 minutes to do so

Title: Re: number Theory problem
Post by rmsgrey on May 25^th, 2009, 12:00pm

on 10/24/08 at 11:20:13, BenVitale wrote:

Keep up with the same approach?

2002 is 111 1101 1100

so the 35 remaining numbers to get to 2047 are 111 11xx xxxx for 5*35=175 1s
the last 32 (2006-2047) have 1 in the 32s bit (another 32 1s)
Of those last 32, each of the remaining 5 bits is 1 16 times. (another 5*16=80 1s)
So you're only needing to count the last 5 bits of 2003, 2004 and 2005 - 11101, 11110 and 11111 respectively for a final 13 1s

175+32+80+13 = 290

11264-290 = 10974 1s total...