<< problem 222 - Sphere Packing | Four Representations using Squares - problem 229 >> |

# Problem 225: Tribonacci non-divisors

(see projecteuler.net/problem=225)

The sequence 1, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193, 355, 653, 1201 ...

is defined by T_1 = T_2 = T_3 = 1 and T_n = T_{n-1} + T_{n-2} + T_{n-3}.

It can be shown that 27 does not divide any terms of this sequence.

In fact, 27 is the first odd number with this property.

Find the 124th odd number that does not divide any terms of the above sequence.

# My Algorithm

Computing a new element of the Tribonacci sequence requires the last three elements.

They are called `tri1`

, `tri2`

and `tri3`

in my code, the next element is `triNext`

:

`unsigned int triNext = tri1 + tri2 + tri3;`

My divisibility check computes a number's modulo and aborts if it becomes zero (`current`

is the current divisor, e.g. 27):

`triNext %= current;`

`if (triNext == 0)`

` break;`

Unfortunately, Tribonacci numbers get massive after just a few steps. Luckily:

(x + y) mod m = (x mod m + y mod m) mod m

Hence my variables `tri1`

, `tri2`

, `tri3`

and `triNext`

don't have to store true Tribonacci numbers but only the remainder modulo the current divisor.

To find out for sure that a number is a non-divisor you have to find a cycle, that means that the remainders repeat themselves.

There are a few smart ways to do that in a 100% safe way - but I decided to have a fixed number of steps and assume a number is a non-divisor if it passed all tests.

The only optimization in my code is to detect whether `tri1 == tri2 == tri3 == 1`

because then it returned to the starting point and there is a loop.

(side note: that simple optimization is sufficient to reliably find the 124th number, though, and I'm not entirely sure why).

My prototype found that 1577 is the divisor where my program needed 22710 steps to prove that it divides a Tribonacci number.

That's why `maxSteps = 22710`

.

## Note

It seems divisor^2 is a hard limit for `MaxSteps`

. My empirically found value is much smaller for most Tribonacci numbers and therefore faster.

The modulo operation `triNext %= current;`

can be slow.

`tri1`

, `tri2`

and `tri3`

are each smaller than `current`

, therefore their sum `triNext`

must be smaller than `3*current`

, too.

The following code is about twice as fast as the modulo operation (which I kept in my solution):

`while (triNext >= current)`

` triNext -= current;`

I thought that a fully unrolled loop could be even faster, but it isn't:

`if (triNext >= current)`

`{`

` triNext -= current;`

` if (triNext >= current)`

` triNext -= current;`

`}`

# My code

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

#include <iostream>
int main()
{
// look for 124th number
unsigned int index = 124;
std::cin >> index;
// 22710 steps until 1577 is a divisor (worst number I observed until the result is found)
const unsigned int MaxSteps = 22710;
// current divisor
unsigned int current = 1; // yes, I could start at 29, too
// found non-divisors
unsigned int numFound = 0;
while (numFound < index)
{
// check next divisor
current += 2;
// first three numbers of the sequence
unsigned int tri1 = 1;
unsigned int tri2 = 1;
unsigned int tri3 = 1;
bool isDivisor = false;
for (unsigned int step = 0; step <= MaxSteps; step++)
{
// next element in sequence
unsigned int triNext = tri1 + tri2 + tri3;
// I need only its remainder
triNext %= current;
// no remainder ? => divisor
if (triNext == 0)
{
isDivisor = true;
break;
}
// update last three elements of the sequence
tri1 = tri2;
tri2 = tri3;
tri3 = triNext;
// returned to original state ? must be a loop
if (tri1 == 1 && tri2 == 1 && tri3 == 1)
break;
}
// found a new non-divisor
if (!isDivisor)
numFound++;
}
// display last non-divisor
std::cout << current << std::endl;
return 0;
}

This solution contains 11 empty lines, 13 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 10 | ./225`

Output:

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

__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 0.02 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

June 23, 2017 submitted solution

June 23, 2017 added comments

# Difficulty

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

# Links

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

# 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 222 - Sphere Packing | Four Representations using Squares - problem 229 >> |