<< problem 206 - Concealed Square | Divisor Square Sum - problem 211 >> |

# Problem 207: Integer partition equations

(see projecteuler.net/problem=207)

For some positive integers k, there exists an integer partition of the form 4^t = 2^t + k,

where 4^t, 2^t, and k are all positive integers and t is a real number.

The first two such partitions are 4^1 = 2^1 + 2 and 4^{1.5849625}... = 2^{1.5849625}... + 6.

Partitions where t is also an integer are called perfect.

For any m >= 1 let P(m) be the proportion of such partitions that are perfect with k <= m.

Thus P(6) = 1/2.

In the following table are listed some values of P(m)

P(5) = 1/1

P(10) = 1/2

P(15) = 2/3

P(20) = 1/2

P(25) = 1/2

P(30) = 2/5

...

P(180) = 1/4

P(185) = 3/13

Find the smallest m for which P(m) < 1/12345

# My Algorithm

The equation can be written as:

4^t = 2^t + k

(2^t)^2 = 2^t + k

And if I replace x = 2^t:

x^2 = x + k

My program iterates over all integer values of x. Then x^2 must be an integer and k must be an integer, too.

The problem statement already gave away that x=2 is the smallest valid partition and is perfect, too (which means t=1 because 2^1=2).

My variables `total`

, `perfect`

and `x`

are initialized accordingly.

x = 2^t is a *perfect* partition if t is an integer. That means that only one bit of the binary representation of x is set

(left side is the power of two, right side how it is written in binary notation):

2^1 = 10_2

2^2 = 100_2

2^3 = 1000_2

2^4 = 10000_2

2^5 = 100000_2

2^6 = 1000000_2

2^7 = 10000000_2

...

My bit twiddling code from bits.stephan-brumme.com/isPowerOfTwo.html can figure out whether x is a power-of-two in just a few CPU cycles.

As soon as the smallest x is known such that dfrac{perfect}{total} < dfrac{1}{12345}, the formula x^2 = x + k is translated to k = x^2 - x which produces the correct result.

## Note

I added a small live test. You can the numerator and denominator for P(m) = dfrac{numerator}{denominator}, e.g. dfrac{1}{1234} → `1 1234`

.

# My code

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

#include <iostream>
// return true, if x is a power of two

bool isPowerOfTwo(unsigned int x)
{
// see http://bits.stephan-brumme.com/isPowerOfTwo.html
return (x & (x - 1)) == 0;
}
int main()
{
// stop when proportion perfect/total is less than numerator/denominator
unsigned int numerator = 1;
unsigned int denominator = 12345;
std::cin >> numerator >> denominator;
if (numerator > denominator || numerator == 0) // check input: for live test only
return 1;
// count all valid partitions
unsigned long long total = 1;
// count perfect partitions
unsigned long long perfect = 1;
// x=2^t
unsigned long long x = 3;
// perfect/total > numerator/denominator is the same as
// perfect*denominator > total*numerator
while (perfect * denominator > total * numerator)
{
// found another perfect partition ?
if (isPowerOfTwo(x))
perfect++;
// keep going ...
total++;
x++;
}
// find k
unsigned long long k = x * (x - 1);
std::cout << k << std::endl;
return 0;
}

This solution contains 7 empty lines, 11 comments and 1 preprocessor command.

# 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 "3 13" | ./207`

Output:

*Note:* the original problem's input `1 12345`

__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 31, 2017 submitted solution

May 31, 2017 added comments

# Difficulty

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

# Links

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

Code in various languages:

Go: github.com/frrad/project-euler/blob/master/golang/Problem207.go (written by Frederick Robinson)

# 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 206 - Concealed Square | Divisor Square Sum - problem 211 >> |