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. Co...
For further actions, you may consider blocking this person and/or reporting abuse
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
Haskell
C
Learning Typescript
Verbose C# solutions 😄
This is a simple python code.