All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

Given positive, integer N, what does this algorithm produce?
```let S and D = N
repeat
let D = ⌊D/2⌋
subtract D from S
until D=0
produce S as the result```
Note: ⌊x⌋ represents the integer part of x.

For non-programmers: start with a positive, integer number (say, 19). Divide it by 2, discarding remainders, until you get to 0. (In this case, you'd get 9, 4, 2, and 1.) Sum all the quotients. (9+4+2+1=16.) Subtract the sum from the original number. (19-16=3.) What's the result?

 Submitted by e.g. Rating: 3.7143 (7 votes) Solution: (Hide) This algorithm calculates the number of ones in the binary representation of N.It's easy to see that if we start with 2N, we get the same result as starting with N, while if we start with 2N+1, the result is 1 more than if we start with N. Since starting with N=1 produces 1, the result follows.Check http://math.ucsd.edu/~mathclub/games/brainteaser-archive/counting.html for another proof.

 Subject Author Date Solution Praneeth 2007-07-31 12:59:13 very good, love the algorithmic view. chris 2005-02-26 06:53:51 additionally sjh182 2005-01-20 06:53:59 Solution Larry 2005-01-14 23:42:34 Independent Solution Tristan 2005-01-14 23:00:39 My thoughts on why the algorihm works Hugo 2005-01-14 18:27:09 Recursive solution Federico Kereki 2005-01-14 17:33:10 Solution Charlie 2005-01-14 16:44:14 An implementation (with results--a Hint--so look only if you want the hint) Charlie 2005-01-14 15:16:49

 Search: Search body:
Forums (0)