Author |
Topic: number Theory problem (Read 1558 times) |
|
LeoYard
Newbie
Posts: 35
|
 |
number Theory problem
« on: Oct 23rd, 2008, 3:48pm » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
Michael Dagg
Senior Riddler
Gender: 
Posts: 500
|
|
Re: number Theory problem
« Reply #1 on: Oct 23rd, 2008, 4:52pm » |
Quote Modify
|
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 .
|
|
IP Logged |
Regards,
Michael Dagg
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
Perhaps this can give us a start: If you enumerate the numbers 0 through 2n-1 in binary, the number of ones is n 2n-1.
This is most easily seen by example. In the image we have the numbers 0 through 15 = 24 - 1 in binary. If you look at each column of the table, exactly half of the entries are ones; hence the result.
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: number Theory problem
« Reply #3 on: Oct 23rd, 2008, 10:58pm » |
Quote Modify
|
on Oct 23rd, 2008, 6:04pm, william wu wrote:Perhaps this can give us a start: If you enumerate the numbers 0 through 2n-1 in binary, the number of ones is n 2n-1.
This is most easily seen by example. In the image we have the numbers 0 through 15 = 24 - 1 in binary. If you look at each column of the table, exactly half of the entries are ones; hence the result.
|
|
Idea is correct, but you mean numbers upto 2n-1 (and n 2n-1) ones.
BTW: I would vote for moving this to easy (at most medium) ... and the thread name is missleading 
|
| « Last Edit: Oct 23rd, 2008, 11:02pm by Hippo » |
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: number Theory problem
« Reply #4 on: Oct 24th, 2008, 11:20am » |
Quote Modify
|
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!
|
| « Last Edit: Oct 24th, 2008, 11:20am by Benny » |
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
warriors837
Guest
|
|
Re: number Theory problem
« Reply #5 on: May 24th, 2009, 7:40pm » |
Quote Modify
 Remove
|
yea...tell me about it, i had it as a bonus in my AP Calc class this year, only 15 minutes to do so
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: number Theory problem
« Reply #6 on: May 25th, 2009, 12:00pm » |
Quote Modify
|
on Oct 24th, 2008, 11:20am, BenVitale wrote: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! |
|
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...
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print