The challenge

Given a positive integer n, calculate the following sum:

1
n + n/2 + n/4 + n/8 + ...

All elements of the sum are the results of integer division.

Example

1
25  =>  25 + 12 + 6 + 3 + 1 = 47

The solution in Python code

Option 1:

1
2
3
4
5
6
7
8
def halving_sum(n): 
    total = [n]
    
    while n>=1:
        n = int(n/2)
        total.append(n)
        
    return sum(total)

Option 2:

1
2
3
4
5
def halving_sum(n): 
    s=0
    while n: 
        s+=n ; n>>=1
    return s

Option 3:

1
2
3
4
5
def halving_sum(n): 
    if n == 1:
        return 1
    else:
        return n + halving_sum(n//2)

Test cases to validate our solution

1
2
3
4
@test.describe('Example Tests')
def example_tests():
    test.assert_equals(halving_sum(25),47)
    test.assert_equals(halving_sum(127),247)