Author |
Topic: Another How Many Integers Riddle... (Read 340 times) |
|
Dudidu
Full Member
Posts: 227
|
 |
Another How Many Integers Riddle...
« on: Nov 20th, 2003, 9:57am » |
 Quote  Modify
|
How many integers [in] {1,2,..., 5000} have a binary representation such that the number of 1's is a multiple of 3 ?
P.S. If your using a computer to exhaustively check all the binary representations you will only get half of the points  .
|
| « Last Edit: Nov 20th, 2003, 9:59am by Dudidu » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Another How Many Integers Riddle...
« Reply #1 on: Nov 20th, 2003, 11:33am » |
Quote Modify
|
If it the range went to some power of two it'd be a lot easier..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Another How Many Integers Riddle...
« Reply #2 on: Nov 20th, 2003, 9:33pm » |
Quote Modify
|
::
lets first look at interval (0,4095)
it takes 12 bit representation
so number of required integers,
C(12,0)+C(12,3)+C(12,6)+C(12,9)+C(12,12)
for the interval (4096,5000)
it takes 13 bit representation
things to note :
1>the 13th bit is already set (13 is MSB for me)
2>and for 5000 whose binary representation is
1001110001000, we note that the second highest bit set is 10th bit.
So the number of required integers in this interval,
C(10,2)+C(10,5)+C( 10,8 )
So the total is the sum of the above two,
which comes to
1708
but i have actually calculated for the interval (0,5119)
there are some extras, this is were i have to go manual and find the ones i need to remove from my count.
manual count gave me 39 extras.
so the actual required number of integers,
1708 - 39
=1669
::
|
| « Last Edit: Nov 20th, 2003, 9:34pm by TenaliRaman » |
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Another How Many Integers Riddle...
« Reply #3 on: Nov 21st, 2003, 1:03am » |
Quote Modify
|
I did it fairly similar, but I got a different (hopefully correct) answer
::5000 = 4096+512+256+128+8
so the number of ones would be
C(12,3)+C(12,6)+C(12,9)+C(12,12)+ // # up to 4096
C(9,2)+C(9,5)+C(9,8)+ // one 1 from 4096, so we need 2,5 or 8 more
C(8,1)+C(8,4)+C(8,7)+ // 2 1's from 4096+512, 1,4 or 7 extra needed
C(7,0)+C(7,3)+C(7,6)+ // 3 1's from 4096+512+256, so 0,3 or 6 more needed
C(3,2) = 1668
::
|
| « Last Edit: Nov 21st, 2003, 1:31am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Another How Many Integers Riddle...
« Reply #4 on: Nov 21st, 2003, 3:46am » |
Quote Modify
|
you are right towr.
i did not see that 0 wasn't in the given set .. i had considered 0 earlier hence i got 1 more than your answer.
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Another How Many Integers Riddle...
« Reply #5 on: Nov 23rd, 2003, 4:47am » |
Quote Modify
|
TenaliRaman and towr,
Your solution (1668) is correct, well done  !
(and ,of course, you get all of the points ).
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print