Given a positive integer n, calculate the following sum:
n + n/2 + n/4 + n/8 + ...
All elements of the sum are the results of integer division. Continue dividing the number until you reach a decimal (no decimals allowed in final answer).
Example
25 => 25 + 12 + 6 + 3 + 1 = 47
Tests
halvingSum(25)
halvingSum(127)
This challenge comes from Belia on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!
Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!
Top comments (16)
COBOL
Run it at jdoodle.com/a/280D
:v
Does "until you reach a decimal" mean "until the result of integer division is below 1"?
Because
25/2
is immediately12.5
, but the example doesn't stop there.(I do see "integer division", but then there are no decimals)
Befunge-93
Edit:
Here is a version with comments
I like the word problem in the question, where decimals are mentioned, but not the example.
So the examples would be:
12.5= 253.5= 491) However, we know that the infinite series
n + n/2 + n/4 + n/8 + ...
converges to2n
.(because it is
2n * (1/2 + 1/4 + 1/8 + 1/16 + ⋯)
link)2) And we know that the highest power of 2 we can cleanly divide a number is the number of trailing zeros it has:
3) And we also know that the sum of the infinitely many items we don't get to add looks like, for example
n/8 + n/16 + n/32 + ...
, which is equivalent to2n
/8
* (1/2 + 1/4 + 1/8 + 1/16 + ⋯)
(and converges to(2n/8)
).4) So the sum without that tail is
2n - 2n/8
, where 8 is 2 to the power of number of trailing zeros of n.5) Well, turns out there is an intrinsic for trailing zeros.
Rust
which results in just this assembly
Is that good, one might ask? No idea, IDK how to computers.
Looping
Recursion
Tail Recursion
Here is the simple solution with Python:
Here is a Python solution,
Javascript