<< problem 44 - Pentagon numbers | Goldbach's other conjecture - problem 46 >> |

# Problem 45: Triangular, pentagonal, and hexagonal

(see projecteuler.net/problem=45)

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

Triangle T_n=n(n+1)/2

→ 1, 3, 6, 10, 15, ...

Pentagonal P_n=n(3n-1)/2

→ 1, 5, 12, 22, 35, ...

Hexagonal H_n=n(2n-1)

→ 1, 6, 15, 28, 45, ...

It can be verified that T_285 = P_165 = H_143 = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

# My Algorithm

In Problem 42 and Problem 44 I already had to check a number whether it is a triangular or a pentagonal number.

My code generates all hexagonal numbers (starting with H_144). And stop as soon as I find a hexagonal number that is triangular and pentagonal, too.

By the way: every hexagonal number is triangular, too:

H_n=T_{2n-1}

## Modifications by HackerRank

The problem was heavily modified by Hackerrank:

the program has to find all numbers, up to an input value, that are

- triangular and pentagonal or

- pentagonal and hexagonal

# My code

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

The code contains `#ifdef`

s to switch between the original problem and the Hackerrank version.

Enable `#ifdef ORIGINAL`

to produce the result for the original problem (default setting for most problems).

#include <iostream>
#include <cmath>
// note: isTriangular and isPentagonal based on Euler problems 42 and 44

bool isTriangular(unsigned long long x)
{
unsigned long long n = sqrt(2*x);
// if n is actually the right answer then t(n) = x
unsigned long long check = n * (n + 1) / 2;
return (x == check);
}
bool isPentagonal(unsigned long long x)
{
unsigned long long n = (1 + sqrt(24*x + 1)) / 6;
// if x was indeed a pentagonal number then our assumption P(n) = x must be true
auto p_n = n * (3 * n - 1) / 2;
return p_n == x;
}
int main()
{
//#define ORIGINAL

#ifdef ORIGINAL
// 143 is the first number which is triangular, pentagonal and hexagonal
for (unsigned int i = 144; ; i++)
{
unsigned int hexagonal = i * (2*i - 1);
if (isPentagonal(hexagonal))
{
// found it !
std::cout << hexagonal << std::endl;
return 0;
}
}
#else
// hexagonal numbers grow the fastest, triangular the slowest
unsigned long long limit;
unsigned int a, b;
std::cin >> limit >> a >> b;
// triangular and pentagonal at the same time
if (a == 3 && b == 5)
{
// let's generate the sequence of all pentagonal numbers, check if triangular, too
for (unsigned long long i = 1; ; i++)
{
auto pentagonal = i * (3*i - 1) / 2;
if (pentagonal >= limit)
break;
if (isTriangular(pentagonal))
std::cout << pentagonal << std::endl;
}
}
// same idea for pentagonal and hexagonal numbers
if (a == 5 && b == 6)
{
// let's generate the sequence of all hexagonal numbers, check if pentagonal, too
for (unsigned long long i = 1; ; i++)
{
auto hexagonal = i * (2*i - 1);
if (hexagonal >= limit)
break;
if (isPentagonal(hexagonal))
std::cout << hexagonal << std::endl;
}
}
#endif
return 0;
}

This solution contains 12 empty lines, 11 comments and 5 preprocessor commands.

# Interactive test

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

This live test is based on the Hackerrank problem.

This is equivalent to`echo "100000 5 6" | ./45`

Output:

*(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

February 27, 2017 submitted solution

April 19, 2017 added comments

# Hackerrank

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

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

# Difficulty

Project Euler ranks this problem at **5%** (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.

# Similar problems at Project Euler

Problem 42: Coded triangle numbers

Problem 44: Pentagon numbers

*Note:* I'm not even close to solving all problems at Project Euler. Chances are that similar problems do exist and I just haven't looked at them.

# Links

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

Code in various languages:

Python: www.mathblog.dk/project-euler-45-next-triangle-pentagonal-hexagonal-number/ (written by Kristian Edlund)

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

Mathematica: github.com/nayuki/Project-Euler-solutions/blob/master/mathematica/p045.mathematica (written by Nayuki)

C: github.com/eagletmt/project-euler-c/blob/master/40-49/problem45.c (written by eagletmt)

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

Javascript: github.com/dsernst/ProjectEuler/blob/master/45 Triangular, pentagonal, and hexagonal.js (written by David Ernst)

Scala: github.com/samskivert/euler-scala/blob/master/Euler045.scala (written by Michael Bayne)

# 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 44 - Pentagon numbers | Goldbach's other conjecture - problem 46 >> |