# Codefights: sumOdious

An *odious* number is a non-negative integer that has an odd number of `1`

s in its binary representation. The first few odious numbers are therefore `1 ("1")`

, `2 ("10")`

, `4 ("100")`

, `7 ("111")`

, `8 ("1000")`

, `11 ("1011")`

, and so on.

Given an integer `k`

, find and return the sum of the first `k`

*odious* numbers, modulo `10`

.^{6} + 7

**Example**

For

`k = 4`

, the output should be`sumOdious(4) = 14`

.The sum of the first

`4`

*odious*numbers is`1 + 2 + 4 + 7 = 14`

.For

`k = 10`

, the output should be`sumOdious(10) = 95`

.

**Input/Output**

**[time limit] 4000ms (js)**

**[input] integer k***Guaranteed Constraints:*`1 ≤ k ≤ 10`

.^{9}**[output] integer**The sum of the first

`k`

*odious*numbers, modulo`10`

.^{6}+ 7

## Solution

This problem can be tackled by observing the pattern the series generates. For that, we implement the actual problem statement naively.

function count(n) { var s = 0; while (n) s+= n & 1, n>>= 1; return s; } function sumOdious(n) { var s = 0; var c = 0; for (var i = 1; c < n; i++) if (count(i) & 1) { s+= i; c++; } return s % (1e6 + 7); } for (var i=0; i <= 10; i++) { console.log(i, sumOdious(i)) }

After executing the code, we see the following series:

\[\{1, 3, 7, 14, 22, 33, 46, 60, ...\}\]

Looking up the pattern reveals the known series A173209 with the following closed form solution:

\[a(n) = n^2 - (n + 1) \backslash 2 + \min(n \bmod 2, \text{hammingWeight}(n) \bmod 2)\]

We need the parity of the hamming weight here, which can be calculated recursively quite easily under the module two:

h = x => x ? 1 + h(x >> 1) & 1: 0

Given \(h\), the minimum of the parity of the hamming weight and \(n \bmod 2\) is simply

\[\min(n \bmod 2, \text{hammingWeight}(n) \bmod 2) := n \& 1 \& h(n) \]

Since we calculate everything under mod 2 already, we can remove the mod two from the \(h\) function:

h = x => x ? 1 + h(x >> 1) : 0

Finally, we can implement the whole solution:

m = 1e6 + 7 sumOdious = n => (n % m * n + (n & 1 & h(n)) - (++n >> 1)) % m

There is one little optimization possible: We can move the definition of the \(h\)-function into sumOdious.

m = 1e6 + 7 sumOdious = n => (n % m * n + (h = x => x ? n & 1 ^ h(x >> 1) : 0)(n) - (++n >> 1)) % m