 # Daily Challenge #257 - Halving Sum From DEV.to

I saw this and I thought it would be fun to see how people come up with solutions! Share them down below!!

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!

2 Likes

Fun one.

This works...
``````def halving_sum(n):
return 1 if n <= 1 else n + halving_sum(n//2)
``````
3 Likes

Cool problem.

This works but looks a bit clunky…

halving_sum
``````>>> def halving_sum(n):
return sum([int(n * 2**(-x)) for x in range(0, n + 1) if int(n * 2**(-x)) > 0])

>>> halving_sum(25)
47
>>> halving_sum(127)
247
>>>
``````
3 Likes

That was an enjoyable challenge.
My answer ain’t as pretty looking, but at least I got it done.

A Solution
``````def halving_sum(n):
result = float(n)
work = float(n) / 2

while work >= 1:

if work.is_integer():
result += work
else:
result += int(work)

work /= 2
return result

print(halving_sum(25)) #should equal 47
print(halving_sum(127)) #should equal 247
``````
3 Likes

Another kick at the comprehension.

halving_sum with log
``````>>> from math import log, ceil
>>> def halving_sum(n):
return [int(n * 2**(-x)) for x in range(0, ceil(log(2*n) / log(2)))]

>>> halving_sum(25)
[25, 12, 6, 3, 1, 0]
>>> halving_sum(127)
[127, 63, 31, 15, 7, 3, 1, 0]
>>> halving_sum(527)
[527, 263, 131, 65, 32, 16, 8, 4, 2, 1, 0]
>>> halving_sum(1527)
[1527, 763, 381, 190, 95, 47, 23, 11, 5, 2, 1, 0]
>>>
``````

The sums

``````>>> def halving_sum(n):
return sum([int(n * 2**(-x)) for x in range(0, ceil(log(2*n) / log(2)))])

>>> halving_sum(25)
47
>>> halving_sum(127)
247
>>> halving_sum(527)
1049
>>> halving_sum(1527)
3045
>>>
``````

Okay, one more crack, this time with `floor` instead of `ceil`.

halving_sum with floor
``````>>> from math import log, floor
>>> def halving_sum(n):
return [int(n * 2**(-x)) for x in range(0, floor(log(2*n) / log(2)))]

>>> halving_sum(25)
[25, 12, 6, 3, 1]
>>> halving_sum(127)
[127, 63, 31, 15, 7, 3, 1]
>>> halving_sum(527)
[527, 263, 131, 65, 32, 16, 8, 4, 2, 1]
>>> halving_sum(1527)
[1527, 763, 381, 190, 95, 47, 23, 11, 5, 2, 1]
>>>
``````

The sums

``````>>> def halving_sum(n):
return sum([int(n * 2**(-x)) for x in range(0, floor(log(2*n) / log(2)))])

>>> halving_sum(25)
47
>>> halving_sum(127)
247
>>> halving_sum(527)
1049
>>> halving_sum(1527)
3045
>>>
``````
1 Like

Using comprehension and log2…

halving_sum
``````>>> def halving_sum(n):
return [int(n * 2**(-x)) for x in range(0, floor(log2(2*n)))]

>>> halving_sum(25)
[25, 12, 6, 3, 1]
>>> halving_sum(127)
[127, 63, 31, 15, 7, 3, 1]
>>> halving_sum(527)
[527, 263, 131, 65, 32, 16, 8, 4, 2, 1]
>>> halving_sum(1527)
[1527, 763, 381, 190, 95, 47, 23, 11, 5, 2, 1]
>>>
``````
``````>>> def halving_sum(n):
return sum([int(n * 2**(-x)) for x in range(0, floor(log2(2*n)))])

>>> halving_sum(25)
47
>>> halving_sum(127)
247
>>> halving_sum(527)
1049
>>> halving_sum(1527)
3045
>>>
``````

`const half = n => n && half(n>>1) + n`
Bit shifting! This is one juicy tasty solution

2 Likes

Rather obvious once we remove our blinders.

I was fixated on the series converging on `2 * n`.

half.py
``````>>> def half(n):
return n and half(n >> 1) + n

>>> half(25)
47
>>> half(127)
247
>>>
``````
2 Likes
I did something quite useless.

The value is repeatedly bitshifted, losing one digit and lowering the value of all the remaining digits

The lowest bit is used one time as 1 (total 1)
The second is used twice, as 2 and 1 (total 3)
The third is used three times, as 4 2 1 (total 7)
The fourth is used four times, as 8 4 2 1 (total 15)
… and so on
that sum (1 3 7 15 31 …) is a power of 2 minus 1

``````bitvalue n = 2 ^ (n + 1) - 1
``````

where n=0 is the first bit
…except, may as well do it with bit shifting

``````bitvalue n = 2 `shiftL` n - 1
``````

I can then create a list for how much each bit is worth

``````bitvalues = map bitvalue [0 ..]
``````

which gets me this:

``````> take 15 bitvalues
[1,3,7,15,31,63,127,255,511,1023,2047,4095,8191,16383,32767]
``````

If i then have the bits of some number

``````bits n = fromEnum <\$> unfoldr next n
where next x = if x == 0 then Nothing else Just (testBit x 0, shiftR x 1)
``````
``````> bits 4
[0,0,1]
> bits 1234897
[1,0,0,0,1,0,1,1,1,1,1,0,1,0,1,1,0,1,0,0,1]
``````

I can zip that with how much they’re worth

``````> zip (bits 1234897) bitvalues
[(1,1),(0,3),(0,7),(0,15),(1,31),(0,63),(1,127),(1,255),(1,511),(1,1023),(1,2047),(0,4095),(1,8191),(0,16383),(1,32767),(1,65535),(0,131071),(1,262143),(0,524287),(0,1048575),(1,2097151)]
``````

multiply each pair (1 -> keep, 0 -> drop)

``````> zipWith (*) (bits 1234897) bitvalues
[1,0,0,0,31,0,127,255,511,1023,2047,0,8191,0,32767,65535,0,262143,0,0,2097151]
``````

and sum them

``````halvingSum n = sum \$ zipWith (*) (bits n) bitvalues
``````

…refactor a bit

``````halvingSum = sum . zipWith (*) bitvalues . bits
``````

And all that is useless because it’s one iteration per bit which is the same number of iterations as one would get by repeatedly halving the value.
For manual computation I imagine this would be faster, but computers happen to be good at summing and halving large numbers and rather bad at looking at individual bits.

https://repl.it/repls/CylindricalUtilizedBlocks

Oh yeah...

I can do this

``````2 ^ (n + 1) - 1
``````

for all bits simultaneously by multiplying the number by 2 and subtracting 1 for each active bit

``````halvingSum n = 2 * n - popCount n
``````

or, as python:

``````def halvingSum(n):
return (n << 1) - f'{n:b}'.count('1')
``````

bitshifting can eat it.

3 Likes