Posted on Jun 11, 2020

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!

Top comments (16)

Anna • Jun 12 '20 • 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 ADD WS-NUMBER TO WS-SUM DIVIDE WS-NUMBER BY 2 GIVING WS-NUMBER END-PERFORM DISPLAY WS-SUM. STOP RUN.

Mike Talbot ⭐ • Jun 11 '20

const half = n => n > 0 ? n + half(n>>1) : n

Mihail Malo • Jun 13 '20

const half = n => n && half(n>>1) + n

Mihail Malo • Jun 13 '20 • Edited

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 • Jun 12 '20 • 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.@

Mihail Malo • Jun 13 '20 • Edited

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 • Jun 12 '20

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 • Jun 18 '20

Here is the simple solution with Python:

def halving_sum(n): # your code here  exp = 0 currentNumber = 0 answer = 0 while n >= int(pow(2, exp)): currentNumber = int(n / pow(2, exp)) answer += currentNumber exp += 1 return answer

Swarup Das • Jun 11 '20

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

Vidit Sarkar • Jun 12 '20

Here is a Python solution,

 halvingSum = lambda n : n and (n + halvingSum(n >> 1)) print(halvingSum(25)) # output -> 47 print(halvingSum(127)) # output -> 247

AmirabbasJ • Jun 13 '20

Javascript

function halvingSum(num){ if(num === 1){ return 1 } return num+halvingSum(Math.floor(num/2)) }

View full discussion (16 comments)