<< problem 168 - Number Rotations | Find the largest 0 to 9 pandigital that can ... - problem 170 >> |

# Problem 169: Exploring the number of different ways a number can be expressed as a sum of powers of 2

(see projecteuler.net/problem=169)

Define f(0)=1 and f(n) to be the number of different ways n can be expressed as a sum of integer powers of 2 using each power no more than twice.

For example, f(10)=5 since there are five different ways to express 10:

1 + 1 + 8

1 + 1 + 4 + 4

1 + 1 + 2 + 2 + 4

2 + 4 + 4

2 + 8

What is f(10^25)?

# My Algorithm

It's easy to write a recursive function to solve the problem for small input, such as 10.

Unfortunately it becomes very slow when analyzing number larger than 10^6. Memoization helps a bit but can't find the solution for 10^25, though.

I created a small list of `solve(1..50)`

and noticed a certain pattern:

`solve(2^y) = y + 1`

, e.g. `solve(16) = solve(2^4) = 5`

`solve(2^y - 1) = 1`

, e.g. `solve(31) = solve(2^5 - 1) = 1`

If the binary representation consists of 1s only, then the result is always `1`

.

If the binary representation consists of a single 1 followed by `y`

zeros, then the result is always `y+1`

.

The whole thing got even more interesting:

appending 1s doesn't change the result, too: `solve(9) = solve(9 >> 1) = solve(4) = 3`

And after fiddling around with the binary representations, I found that the number of consecutive zeros plays a major role.

I came up with an iterative formula:

f_i(x) = f_{i-1}(x) + zeros_i(x) * sum_{k=1..i}{f_k(x)}

where zeros_i(x) stands for the number of zeros between two 1s, beginning from the left side of the binary representation of x.

`countZeros`

returns a vector of those lengths of zero bits, e.g. 100000_10 = 11000011010100000_2 → `{ 0, 4, 0, 1, 1, 5 }`

If x is odd, then the right-most 1s have to be removed until x becomes even.

## Note

After finishing my program, I discovered that this is called the Diatomic Series - a term haven't heard of before.

This program doesn't compile with Visual C++ because I had to use the GCC extension `__int128`

since 10^25 > 2^64.

# My code

… was written in C++11 and can be compiled with G++, Clang++. You can download it, too.

#include <iostream>
#include <vector>
#include <string>
// GCC-specific 128 bit integer

typedef unsigned __int128 BigNum;
// brute-force solver, not used anymore

unsigned int solve(unsigned int x, unsigned int minAdd = 1)
{
if (x == 0)
return 1;
unsigned long long result = 0;
auto current = minAdd;
while (current <= x)
{
// try to remove current 2^k once
result += solve(x - current, current*2);
// and twice
if (x >= 2*current)
result += solve(x - 2*current, current*2);
// process 2^(k+1)
current *= 2;
}
return result;
}
// count consecutive zeros in binary representation

std::vector<unsigned int> countZeros(BigNum x)
{
std::vector<unsigned int> result;
// right-most 1s don't affect the result, remove them
while ((x & 1) == 1)
x >>= 1;
auto consecutive = 0;
while (x > 0)
{
// look at right-most bit
if ((x & 1) == 0)
{
// once more zero
consecutive++;
}
else
{
// runs of consecutive zeros interrupted by a 1
result.insert(result.begin(), consecutive);
consecutive = 0;
// note: consecutive can be zero, too !
}
x >>= 1;
}
return result;
}
int main()
{
// can't read anything >= 2^64, must do it via string parsing
std::string large;
std::cin >> large;
BigNum x = 0;
// digit by digit ...
for (auto c : large)
x = x*10 + (c - '0');
// count consecutive zeros in binary representation
auto zeros = countZeros(x);
// compute number of distinct representations
unsigned long long result = 1;
unsigned long long sum = 1;
for (unsigned int i = 0; i < zeros.size(); i++)
{
result += zeros[i] * sum;
sum += result;
}
std::cout << result << std::endl;
return 0;
}

This solution contains 13 empty lines, 15 comments and 3 preprocessor commands.

# Interactive test

You can submit your own input to my program and it will be instantly processed at my server:

This is equivalent to`echo 10 | ./169`

Output:

*Note:* the original problem's input `10000000000000000000000000`

__cannot__ be entered

because just copying results is a soft skill reserved for idiots.

*(this interactive test is still under development, computations will be aborted after one second)*

# Benchmark

The correct solution to the original Project Euler problem was found in less than 0.01 seconds on a Intel® Core™ i7-2600K CPU @ 3.40GHz.

(compiled for x86_64 / Linux, GCC flags: `-O3 -march=native -fno-exceptions -fno-rtti -std=c++11 -DORIGINAL`

)

See here for a comparison of all solutions.

**Note:** interactive tests run on a weaker (=slower) computer. Some interactive tests are compiled without `-DORIGINAL`

.

# Changelog

May 30, 2017 submitted solution

May 30, 2017 added comments

# Hackerrank

see https://www.hackerrank.com/contests/projecteuler/challenges/euler169

My code solves **11** out of **11** test cases (score: **100%**)

# Difficulty

Project Euler ranks this problem at **50%** (out of 100%).

Hackerrank describes this problem as **easy**.

*Note:*

Hackerrank has strict execution time limits (typically 2 seconds for C++ code) and often a much wider input range than the original problem.

In my opinion, Hackerrank's modified problems are usually a lot harder to solve. As a rule thumb: brute-force is rarely an option.

# Links

projecteuler.net/thread=169 - **the** best forum on the subject (*note:* you have to submit the correct solution first)

Code in various languages:

Java: github.com/nayuki/Project-Euler-solutions/blob/master/java/p169.java (written by Nayuki)

# Heatmap

green problems solve the original Project Euler problem and have a perfect score of 100% at Hackerrank, too.

yellow problems score less than 100% at Hackerrank (but still solve the original problem).

gray problems are already solved but I haven't published my solution yet.

blue problems are solved and there wasn't a Hackerrank version of it at the time I solved it or I didn't care about it because it differed too much.

red problems are solved but exceed the time limit of one minute or the memory limit of 256 MByte.

*Please click on a problem's number to open my solution to that problem:*

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |

26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |

51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 |

76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |

101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 |

126 | 127 | 128 | 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 |

151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 | 171 | 172 | 173 | 174 | 175 |

176 | 177 | 178 | 179 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 | 191 | 192 | 193 | 194 | 195 | 196 | 197 | 198 | 199 | 200 |

201 | 202 | 203 | 204 | 205 | 206 | 207 | 208 | 209 | 210 | 211 | 212 | 213 | 214 | 215 | 216 | 217 | 218 | 219 | 220 | 221 | 222 | 223 | 224 | 225 |

226 | 227 | 228 | 229 | 230 | 231 | 232 | 233 | 234 | 235 | 236 | 237 | 238 | 239 | 240 | 241 | 242 | 243 | 244 | 245 | 246 | 247 | 248 | 249 | 250 |

251 | 252 | 253 | 254 | 255 | 256 | 257 | 258 | 259 | 260 | 261 | 262 | 263 | 264 | 265 | 266 | 267 | 268 | 269 | 270 | 271 | 272 | 273 | 274 | 275 |

276 | 277 | 278 | 279 | 280 | 281 | 282 | 283 | 284 | 285 | 286 | 287 | 288 | 289 | 290 | 291 | 292 | 293 | 294 | 295 | 296 | 297 | 298 | 299 | 300 |

301 | 302 | 303 | 304 | 305 | 306 | 307 | 308 | 309 | 310 | 311 | 312 | 313 | 314 | 315 | 316 | 317 | 318 | 319 | 320 | 321 | 322 | 323 | 324 | 325 |

326 | 327 | 328 | 329 | 330 | 331 | 332 | 333 | 334 | 335 | 336 | 337 | 338 | 339 | 340 | 341 | 342 | 343 | 344 | 345 | 346 | 347 | 348 | 349 | 350 |

351 | 352 | 353 | 354 | 355 | 356 | 357 | 358 | 359 | 360 | 361 | 362 | 363 | 364 | 365 | 366 | 367 | 368 | 369 | 370 | 371 | 372 | 373 | 374 | 375 |

376 | 377 | 378 | 379 | 380 | 381 | 382 | 383 | 384 | 385 | 386 | 387 | 388 | 389 | 390 | 391 | 392 | 393 | 394 | 395 | 396 | 397 | 398 | 399 | 400 |

401 | 402 | 403 | 404 | 405 | 406 | 407 | 408 | 409 | 410 | 411 | 412 | 413 | 414 | 415 | 416 | 417 | 418 | 419 | 420 | 421 | 422 | 423 | 424 | 425 |

426 | 427 | 428 | 429 | 430 | 431 | 432 | 433 | 434 | 435 | 436 | 437 | 438 | 439 | 440 | 441 | 442 | 443 | 444 | 445 | 446 | 447 | 448 | 449 | 450 |

451 | 452 | 453 | 454 | 455 | 456 | 457 | 458 | 459 | 460 | 461 | 462 | 463 | 464 | 465 | 466 | 467 | 468 | 469 | 470 | 471 | 472 | 473 | 474 | 475 |

476 | 477 | 478 | 479 | 480 | 481 | 482 | 483 | 484 | 485 | 486 | 487 | 488 | 489 | 490 | 491 | 492 | 493 | 494 | 495 | 496 | 497 | 498 | 499 | 500 |

501 | 502 | 503 | 504 | 505 | 506 | 507 | 508 | 509 | 510 | 511 | 512 | 513 | 514 | 515 | 516 | 517 | 518 | 519 | 520 | 521 | 522 | 523 | 524 | 525 |

526 | 527 | 528 | 529 | 530 | 531 | 532 | 533 | 534 | 535 | 536 | 537 | 538 | 539 | 540 | 541 | 542 | 543 | 544 | 545 | 546 | 547 | 548 | 549 | 550 |

I scored 13,183 points (out of 15300 possible points, top rank was 17 out of ≈60000 in August 2017) at Hackerrank's Project Euler+.

Look at my progress and performance pages to get more details.

My username at Project Euler is

**stephanbrumme**while it's stbrumme at Hackerrank.

# Copyright

I hope you enjoy my code and learn something - or give me feedback how I can improve my solutions.

All of my solutions can be used for any purpose and I am in no way liable for any damages caused.

You can even remove my name and claim it's yours. But then you shall burn in hell.

The problems and most of the problems' images were created by Project Euler.

Thanks for all their endless effort.

<< problem 168 - Number Rotations | Find the largest 0 to 9 pandigital that can ... - problem 170 >> |