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

 Whadduzitdo? (Posted on 2005-01-14)
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?

 See The Solution Submitted by e.g. Rating: 3.7143 (7 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Solution | Comment 2 of 9 |
(In reply to An implementation (with results--a Hint--so look only if you want the hint) by Charlie)

Note that when the program is run, powers of two result in S = 1, while large values occur just before the power of two.  This suggests the algorithm is counting the 1 bits in the binary representation of the number N.  This is also suggested by the continual division by 2, although it's not obvious why the algorithm works exactly, by subtracting these quotients from S.

The following program incorporates a conventional conversion of numbers to binary, counting 1 bits as it goes along, as well as implementing the algorithm of the puzzle.  The count of 1 bits always matches the result of the puzzle algorithm, confirming that that is in fact what it does.

DECLARE FUNCTION bi\$ (x!)
DIM SHARED tot
CLS
FOR n = 1 TO 40
s = n: d = n
DO
d = INT(d / 2)
s = s - d
LOOP UNTIL d = 0
PRINT USING "## & ## ## "; n; RIGHT\$("          " + bi\$(n), 10); s; tot
NEXT

FUNCTION bi\$ (x)
b\$ = ""
tot = 0
v = x
DO
q = v \ 2
r = v MOD 2
tot = tot + r
v = q
b\$ = LTRIM\$(STR\$(r) + b\$)
LOOP UNTIL q = 0
bi\$ = b\$
END FUNCTION

Results:

` 1          1  1  1 2         10  1  1 3         11  2  2 4        100  1  1 5        101  2  2 6        110  2  2 7        111  3  3 8       1000  1  1 9       1001  2  210       1010  2  211       1011  3  312       1100  2  213       1101  3  314       1110  3  315       1111  4  416      10000  1  117      10001  2  218      10010  2  219      10011  3  320      10100  2  221      10101  3  322      10110  3  323      10111  4  424      11000  2  225      11001  3  326      11010  3  327      11011  4  428      11100  3  329      11101  4  430      11110  4  431      11111  5  532     100000  1  133     100001  2  234     100010  2  235     100011  3  336     100100  2  237     100101  3  338     100110  3  339     100111  4  440     101000  2  2`

 Posted by Charlie on 2005-01-14 16:44:14

 Search: Search body:
Forums (1)