# Test System

Most of my development is done on a Intel® Core™ i7-2600K CPU @ 3.40GHz.

My default compiler is G++ with a x86_64 target and its command-line settings are

`g++ -O3 -march=native -fno-exceptions -fno-rtti -std=c++11`

All solutions are single-threaded and run on the CPU only (no GPU etc.).

You'll find below the following Top Ten lists:

In addition a summary of the difficulty is presented.# Execution Time

The majority of my C++ solutions need much longer to compile than to run.

The "slowest" solutions are (user time displayed by `time`

):

problem | seconds |
---|---|

501 - Eight Divisors | 56.33 seconds |

407 - Idempotents | 47.22 seconds |

549 - Divisibility of factorials | 26.77 seconds |

141 - Investigating progressive numbers, n, which are ... | 21.33 seconds |

154 - Exploring Pascal's pyramid | 16.53 seconds |

211 - Divisor Square Sum | 14.64 seconds |

229 - Four Representations using Squares | 10.46 seconds |

571 - Super Pandigital Numbers | 8.88 seconds |

348 - Sum of a square and a cube | 5.59 seconds |

103 - Special subset sums: optimum | 4.27 seconds |

**Note:** 177 out of 270 solutions find the correct result in less than 0.1 seconds.

It's not an "officially enforced" limit but each Project Euler problem should be solvable in less than one minute.

I needed much longer to find the correct solutions for these problems:

problem | seconds | factor |
---|---|---|

291 - Panaitopol Primes | 112 seconds | 1.87x |

# Memory Consumption

The GCC standard library consumes about 2 MByte RAM (basic I/O, etc.).

According to Project Euler, the problems are designed such that a smart solution needs no more than 256 MByte.

problem | peak memory consumption |
---|---|

259 - Reachable Numbers | 138.6 MB |

341 - Golomb's self-describing sequence | 133.3 MB |

425 - Prime connection | 113.6 MB |

155 - Counting Capacitor Circuits | 105.7 MB |

165 - Intersections | 68.9 MB |

309 - Integer Ladders | 59.2 MB |

303 - Multiples with small digits | 46.2 MB |

222 - Sphere Packing | 45.2 MB |

407 - Idempotents | 41.2 MB |

549 - Divisibility of factorials | 41.2 MB |

**Note:** 181 out of 270 solutions allocate less than 2.5 MByte.

Some solutions could be modified to use smaller data types, especially because an `int`

is 8 bytes on my system (64 bit compiler).

The size of the compiled binary is never an issue regarding memory consumption because all are way below 100 kByte (vast majority only about 10 kByte).

# "Expensive" Solutions

These solutions require both lots of CPU time and tons of memory.

(I multiply execution time in seconds by memory consumption in MByte to get my *"factor"*)

problem | factor |
---|---|

407 - Idempotents | 1,947.2 |

549 - Divisibility of factorials | 1,103.2 |

501 - Eight Divisors | 822.4 |

211 - Divisor Square Sum | 262.5 |

291 - Panaitopol Primes | 255.8 |

155 - Counting Capacitor Circuits | 220.9 |

259 - Reachable Numbers | 209.3 |

425 - Prime connection | 188.5 |

222 - Sphere Packing | 101.2 |

154 - Exploring Pascal's pyramid | 99.2 |

# "Lopsided" Solutions

These solutions require lots of CPU time **or** tons of memory - but not both.

Usually there is a trade-off between CPU time and memory consumption and most likely I didn't find a proper balance for these problems.

My standard approach is to prefer faster code and accept higher memory usage - as long as it's below 256 MByte.

I divide execution time in seconds by memory consumption in MByte to get my *"imbalance"*,
if it's smaller than one then I take it's inverse.

problem | imbalance | seconds | peak memory consumption |
---|---|---|---|

291 - Panaitopol Primes | 7,479 | 112 seconds | 2.3 |

341 - Golomb's self-describing sequence | 1,139 | 0.11 seconds | 133.3 |

141 - Investigating progressive numbers, n, which are ... | 928 | 21.33 seconds | 2.3 |

113 - Non-bouncy numbers | 645 | 0.02 seconds | 18.4 |

72 - Counting fractions | 320 | 0.03 seconds | 13.5 |

571 - Super Pandigital Numbers | 287 | 8.88 seconds | 2.3 |

148 - Exploring Pascal's triangle | 236 | 3.53 seconds | 2.3 |

103 - Special subset sums: optimum | 225 | 4.27 seconds | 2.3 |

149 - Searching for a maximum-sum subsequence | 204 | 0.07 seconds | 17.6 |

510 - Tangent Circles | 182 | 4.17 seconds | 2.3 |

**Note:**to compensate for timing inaccuracies I added 0.005 seconds to each execution time when computing the imbalance.

Moreover, the memory overhead of the C++ runtime is estimated to be 2.26 MByte and subtracted from peak memory usage.

# Code Metrics

C++ programs tend to be a bit longer than other popular languages (such as Python).

The metric "lines of code" excludes comments, empty lines and preprocessor commands.

About half of the program in the Top Ten are related to primes numbers. My Miller-Rabin primality test needs about 150 lines.

In general, most of the "bigger" solution contain a substantial amount of code that I just copy from my toolbox.

The actual amount of original code is therefore substantially lower.

problem | lines of code | comments | blank lines |
---|---|---|---|

304 - Primonacci | 236 | 77 | 63 |

80 - Square root digital expansion | 234 | 66 | 42 |

152 - Writing 1/2 as a sum of inverse squares | 209 | 74 | 44 |

60 - Prime pair sets | 206 | 65 | 38 |

146 - Investigating a Prime Pattern | 190 | 60 | 42 |

54 - Poker hands | 188 | 28 | 26 |

126 - Cuboid layers | 187 | 57 | 40 |

280 - Ant and seeds | 179 | 56 | 46 |

313 - Sliding game | 170 | 60 | 33 |

98 - Anagramic squares | 169 | 49 | 42 |

**Note:** 108 out of 270 solutions have less than 50 lines of code.

# Difficulty

Each problem has a "rating" at Project Euler. Very easy have a rating of 5%, while the highest is 100%.

The right column shows how many of my solved problems fall into that category.

rating | solved problems | links | |
---|---|---|---|

5% | 63 | 23.3% | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 (and 48 more) |

10% | 9 | 3.3% | 54, 69, 71, 76, 81, 99, 357, 387, 549 |

15% | 18 | 6.7% | 51, 62, 65, 73, 74, 85, 93, 102, 112, 205, 301, 345, 346, 347, 381 (and 3 more) |

20% | 17 | 6.3% | 60, 61, 64, 70, 72, 80, 82, 87, 89, 145, 187, 315, 323, 407, 429 (and 2 more) |

25% | 21 | 7.8% | 66, 68, 75, 77, 83, 91, 96, 104, 120, 124, 125, 179, 203, 293, 329 (and 6 more) |

30% | 14 | 5.2% | 78, 95, 100, 108, 113, 116, 119, 123, 173, 204, 313, 321, 371, 510 |

35% | 22 | 8.1% | 84, 86, 94, 98, 101, 107, 114, 115, 117, 121, 151, 188, 243, 277, 297 (and 7 more) |

40% | 13 | 4.8% | 88, 90, 110, 122, 131, 174, 207, 214, 231, 235, 265, 287, 501 |

45% | 21 | 7.8% | 103, 105, 109, 111, 118, 129, 130, 132, 134, 135, 136, 138, 142, 162, 164 (and 6 more) |

50% | 21 | 7.8% | 106, 127, 133, 137, 139, 144, 146, 148, 149, 166, 169, 190, 211, 215, 230 (and 6 more) |

55% | 11 | 4.1% | 126, 128, 150, 158, 172, 178, 185, 193, 218, 250, 306 |

60% | 13 | 4.8% | 141, 154, 155, 159, 160, 182, 186, 209, 213, 222, 240, 249, 523 |

65% | 15 | 5.6% | 147, 152, 165, 168, 196, 200, 201, 226, 227, 232, 239, 247, 266, 274, 280 |

70% | 12 | 4.4% | 161, 163, 170, 171, 181, 189, 199, 219, 229, 259, 260, 273 |

75% | - | - | |

80% | - | - | |

85% | - | - | |

90% | - | - | |

95% | - | - | |

100% | - | - | |

270 | 31.3% |

# Heatmap

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

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

yellow | solutions score less than 100% at Hackerrank (but still solve the original problem easily) | |

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

blue | solutions are relevant for Project Euler only: there wasn't a Hackerrank version of it (at the time I solved it) or it differed too much | |

orange | problems are solved but exceed the time limit of one minute or the memory limit of 256 MByte | |

red | problems are not solved yet but I wrote a simulation to approximate the result or verified at least the given example - usually I sketched a few ideas, too |

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 |

551 | 552 | 553 | 554 | 555 | 556 | 557 | 558 | 559 | 560 | 561 | 562 | 563 | 564 | 565 | 566 | 567 | 568 | 569 | 570 | 571 | 572 | 573 | 574 | 575 |

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

My username at Project Euler is

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

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