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
>>> 

I saw this answer in the comments of the original post:

Another answer

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.

4 Likes