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=gnu++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
, single core only):
problem | seconds |
---|---|
501 - Eight Divisors | 56.33 seconds |
407 - Idempotents | 46.52 seconds |
549 - Divisibility of factorials | 26.77 seconds |
141 - Investigating progressive numbers, n, which are ... | 21.33 seconds |
473 - Phigital number base | 19.34 seconds |
154 - Exploring Pascal's pyramid | 16.53 seconds |
211 - Divisor Square Sum | 14.64 seconds |
229 - Four Representations using Squares | 10.46 seconds |
358 - Cyclic numbers | 9.56 seconds |
386 - Maximum length of an antichain | 8.92 seconds |
Note: 185 out of 299 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 60 seconds.
I needed much longer to find the correct solutions for a few problems.
Some of them can be heavily parallelized, but the timings below still refer to the slower single-core version:
problem | seconds | OpenMP support |
---|---|---|
611 - Hallway of square steps | 5692 seconds | yes |
216 - Investigating the primality of numbers of the form ... | 1960 seconds | yes |
343 - Fractional Sequences | 147 seconds | yes |
291 - Panaitopol Primes | 121 seconds | yes |
411 - Uphill paths | 92 seconds | yes |
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 |
---|---|
411 - Uphill paths | 234.6 MByte |
259 - Reachable Numbers | 138.6 MByte |
341 - Golomb's self-describing sequence | 133.3 MByte |
425 - Prime connection | 113.6 MByte |
155 - Counting Capacitor Circuits | 105.7 MByte |
165 - Intersections | 68.9 MByte |
581 - 47-smooth triangular numbers | 67.9 MByte |
309 - Integer Ladders | 59.2 MByte |
358 - Cyclic numbers | 47.7 MByte |
303 - Multiples with small digits | 46.2 MByte |
Note: 192 out of 299 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).
It's not an "officially enforced" limit but each Project Euler problem should be solvable with less than 256 MByte memory.
I needed much more to find the correct solution to these problems:
problem | peak memory consumption | factor |
---|---|---|
461 - Almost Pi | 634 MByte | 2.47x |
"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".
Solutions with a colored background exceed either the CPU or memory limit (or both) and obviously dominate this list.
problem | factor |
---|---|
611 - Hallway of square steps | 83257.5 |
411 - Uphill paths | 21567.7 |
216 - Investigating the primality of numbers of the form ... | 17364.0 |
461 - Almost Pi | 4257.2 |
407 - Idempotents | 1916.1 |
549 - Divisibility of factorials | 1103.2 |
501 - Eight Divisors | 822.4 |
343 - Fractional Sequences | 480.5 |
358 - Cyclic numbers | 456.1 |
291 - Panaitopol Primes | 277.9 |
"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 | 3,452 | 120.81 seconds | 2.3 MByte |
341 - Golomb's self-describing sequence | 1,139 | 0.11 seconds | 133.3 MByte |
141 - Investigating progressive numbers, n, which are ... | 928 | 21.33 seconds | 2.3 MByte |
208 - Numbers for which Euler's totient function equals ... | 844 | 0.03 seconds | 31.8 MByte |
113 - Non-bouncy numbers | 645 | 0.02 seconds | 18.4 MByte |
611 - Hallway of square steps | 460 | 5691.65 seconds | 14.6 MByte |
72 - Counting fractions | 320 | 0.03 seconds | 13.5 MByte |
216 - Investigating the primality of numbers of the form ... | 297 | 1959.82 seconds | 8.9 MByte |
571 - Super Pandigital Numbers | 287 | 8.88 seconds | 2.3 MByte |
148 - Exploring Pascal's triangle | 236 | 3.53 seconds | 2.3 MByte |
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 |
---|---|---|---|
343 - Fractional Sequences | 240 | 86 | 59 |
284 - Steady Squares | 240 | 56 | 56 |
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 |
Note: 112 out of 299 solutions have less than 50 lines of code.
Difficulty
Each problem has a "rating" at Project Euler. Very easy ones 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 | 21.1% | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 (and 48 more) |
10% | 9 | 3.0% | 54, 69, 71, 76, 81, 99, 357, 387, 549 |
15% | 18 | 6.0% | 51, 62, 65, 73, 74, 85, 93, 102, 112, 205, 301, 345, 346, 347, 381, 493, 500, 504 |
20% | 20 | 6.7% | 60, 61, 64, 70, 72, 80, 82, 87, 89, 145, 187, 315, 323, 407, 429 (and 5 more) |
25% | 24 | 8.0% | 66, 68, 75, 77, 83, 91, 96, 104, 120, 124, 125, 179, 203, 293, 329 (and 9 more) |
30% | 15 | 5.0% | 78, 95, 100, 108, 113, 116, 119, 123, 173, 204, 313, 321, 371, 461, 510 |
35% | 25 | 8.4% | 84, 86, 94, 98, 101, 107, 114, 115, 117, 121, 151, 188, 243, 277, 288 (and 10 more) |
40% | 17 | 5.7% | 88, 90, 110, 122, 131, 174, 207, 214, 231, 235, 265, 287, 327, 386, 418, 455, 501 |
45% | 24 | 8.0% | 103, 105, 109, 111, 118, 129, 130, 132, 134, 135, 136, 138, 142, 162, 164 (and 9 more) |
50% | 23 | 7.7% | 106, 127, 133, 137, 139, 144, 146, 148, 149, 166, 169, 190, 211, 215, 230 (and 8 more) |
55% | 12 | 4.0% | 126, 128, 150, 158, 172, 178, 185, 193, 218, 250, 284, 306 |
60% | 13 | 4.3% | 141, 154, 155, 159, 160, 182, 186, 209, 213, 222, 240, 249, 523 |
65% | 15 | 5.0% | 147, 152, 165, 168, 196, 200, 201, 226, 227, 232, 239, 247, 266, 274, 280 |
70% | 18 | 6.0% | 156, 161, 163, 170, 171, 181, 189, 199, 208, 219, 229, 237, 244, 248, 259, 260, 268, 273 |
75% | - | - | |
80% | - | - | |
85% | - | - | |
90% | - | - | |
95% | - | - | |
100% | - | - | |
(unknown) | 3 | 1.0% | 607, 610, 611 |
299 | 32.4% |
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 | |
black | problems are solved but access to the solution is blocked for a few days until the next problem is published | |
the flashing problem is the one I solved most recently |
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 |
576 | 577 | 578 | 579 | 580 | 581 | 582 | 583 | 584 | 585 | 586 | 587 | 588 | 589 | 590 | 591 | 592 | 593 | 594 | 595 | 596 | 597 | 598 | 599 | 600 |
601 | 602 | 603 | 604 | 605 | 606 | 607 | 608 | 609 | 610 | 611 | 612 | 613 | 614 |
I scored 13526 points (out of 15700 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.