# Daily Challenge #257 - Halving Sum

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! Anna • Edited

## COBOL

Run it at jdoodle.com/a/280D

``````IDENTIFICATION DIVISION.
PROGRAM-ID. HALVING-SUM.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 WS-NUMBER PIC 9(4).
01 WS-SUM PIC 9(5) VALUE 0.
PROCEDURE DIVISION.
DISPLAY 'Enter number from 1 to 9999:'
ACCEPT WS-NUMBER FROM CONSOLE
PERFORM UNTIL WS-NUMBER < 1
DIVIDE WS-NUMBER BY 2 GIVING WS-NUMBER
END-PERFORM
DISPLAY WS-SUM.
STOP RUN.
`````` Does "until you reach a decimal" mean "until the result of integer division is below 1"?
Because `25/2` is immediately `12.5`, but the example doesn't stop there.
(I do see "integer division", but then there are no decimals) Sam Ferree • Edited

Befunge-93

``````&>:02pv
>2/:0`!#v_:02g+02p
>02g.@
``````

Edit:
Here is a version with comments

``````&>:02pv Read a value t from the user, store it at (0,2)
divide t by 2, if t > 0 store (0,2)+t at (0,2) repeat
>2/:0`!#v_:02g+02p
if t <= 0 print (0,2) as integer, end program
>02g.@
`````` I like the word problem in the question, where decimals are mentioned, but not the example.
So the examples would be:

• 25 => 25 + 12.5 = 25
• 28 => 28 + 14 + 7 + 3.5 = 49
``````const half = n => n % 2 ? n : n + half(n / 2) // ew, not even tail recursion
``````

1) However, we know that the infinite series `n + n/2 + n/4 + n/8 + ...` converges to `2n`.
(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:

``````0b1100 / 2 = 0b110
0b110 / 2 = 0b11
0b11 / 2 = 'loss.jpg'
``````

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 to `2n``/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

``````fn half(x: u64) -> u64 {
let highest = x.trailing_zeros();
2 * x - (x >> highest)
}
``````

which results in just this assembly

``````example::half:
test    rdi, rdi
je      .LBB0_1
bsf     rcx, rdi
jmp     .LBB0_3
.LBB0_1:
mov     ecx, 64
.LBB0_3:
mov     rdx, rdi
shr     rdx, cl
lea     rax, [rdi + rdi]
sub     rax, rdx
ret
``````

Is that good, one might ask? No idea, IDK how to computers. David Leger

### Looping

``````const halvingSum = (n: number): number => {
let sum = 0;

while (n !== 0) {
sum += n;
n = Math.floor(n / 2);
}

return sum;
}
``````

### Recursion

``````const halvingSum = (n: number): number => {
if (n === 0) {
return n;
}

return n + halvingSum(Math.floor(n / 2))
}
``````

### Tail Recursion

``````const halvingSum = (n: number, sum: number = 0): number => {
if (n === 0) {
return sum;
}

return halvingSum(Math.floor(n / 2), sum + n);
}
`````` peter279k

Here is the simple solution with Python:

``````def halving_sum(n):
exp = 0
currentNumber = 0
while n >= int(pow(2, exp)):
currentNumber = int(n / pow(2, exp))
exp += 1

`````` Swarup Das
``````/**
*
* @param {Number} number
*/
function halvingSum(number) {
let total = 0;
while (number > 0) {
total += number;
number = Math.floor(number / 2);
}
}

`````` Vidit Sarkar

Here is a Python solution,

``````
halvingSum = lambda n : n and (n + halvingSum(n >> 1))

print(halvingSum(25)) # output -> 47
print(halvingSum(127)) # output -> 247
`````` Amin

``````halvingSum :: Int -> Int
halvingSum 0 = 0
halvingSum x = (+) x \$ halvingSum \$ div x 2
`````` Blake Johnson

# C

``````int halving_sum(int n) {
if (n / 2 <= 1) return n + 1;
return n + halving_sum(n / 2);
}
`````` Austin Nieset

Learning Typescript

``````function halvingSum(num: number): number {
if (num <= 1) {
return 0;
} else {
return num + Math.floor(halvingSum(num/2));
}
}
``````