<< problem 24 - Lexicographic permutations | Reciprocal cycles - problem 26 >> |

# Problem 25: 1000-digit Fibonacci number

(see projecteuler.net/problem=25)

The Fibonacci sequence is defined by the recurrence relation:

F_n = F_{n-1} + F_{n-2}, where F_1 = 1 and F_2 = 1.

Hence the first 12 terms will be:

F_1 = 1

F_2 = 1

F_3 = 2

F_4 = 3

F_5 = 5

F_6 = 8

F_7 = 13

F_8 = 21

F_9 = 34

F_{10} = 55

F_{11} = 89

F_{12} = 144

The 12th term, F_{12}, is the first term to contain three digits.

What is the index of the first term in the Fibonacci sequence to contain 1000 digits?

# My Algorithm

I precompute all Fibonacci number with up to 5000 digits (a design decision influenced by Hackerrank's modified problem) and keep those results in `cache`

.

Unfortunately, there is a small problem with C++ ...

F_{47}=2971215073 is the largest Fibonacci number that fits in a 32-bit integer and

F_{94}=19740274219868223167 is too big for a 64-bit integer.

My program stores such large number as a `std::vector`

where index 0 contains the least significant digit ("in reverse order").

E.g. F_{23}=28657 is represented as `{ 7, 5, 6, 8, 2 }`

The function `add`

returns the sum of two large numbers `a`

and `b`

where `b>=a`

.

The algorithm behind this function is exactly the same you were taught in primary school.

## Alternative Approaches

The main problem was adding two very large numbers. When programming in Python, Java, etc. you get these things for free.

## Modifications by HackerRank

The large amount of test cases was the main cause for dividing my solution into two parts;

1. precompute all relevant Fibonacci numbers (done once - "expensive")

2. look up the result (performed many, many times - "cheap")

# My code

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

#include <vector>
#include <iostream>
// store single digits because numbers get too big for C++

typedef std::vector<unsigned int> Digits;
// Hackerrank's upper limit

const unsigned int MaxDigits = 5000;
// add two long number where b >= a

Digits add(const Digits& a, const Digits& b)
{
Digits result = b;
unsigned int carry = 0;
for (unsigned int i = 0; i < result.size(); i++)
{
// "a" might have less digits than "b"
if (i < a.size())
result[i] += a[i];
// don't forget about the carry ...
result[i] += carry;
// handle overflow
if (result[i] >= 10)
{
carry = 1;
result[i] -= 10;
}
else
carry = 0;
}
// largest digit not overflowing ?
if (carry != 0)
result.push_back(carry);
return result;
}
int main()
{
// precompute number of steps we needed for each number of digits
// [number of digits] => [index of smallest Fibonacci number]
std::vector<unsigned int> cache = { 0, 1 }; // F_0 is undefined
cache.reserve(MaxDigits);
// f(1) = 1
Digits a = { 1 };
// f(2) = 1
Digits b = { 1 };
// we have predefined F_1 and F_2
unsigned int fiboIndex = 2;
while (cache.size() <= MaxDigits)
{
// next Fibonacci number
fiboIndex++;
auto next = add(a, b);
a = std::move(b);
b = std::move(next);
// digits of current Fibonacci number
auto numDigits = b.size();
// digits of the previously largest Fibonacci number
auto largestKnown = cache.size() - 1; // don't count the 0th element
// one more digit than before ?
if (largestKnown < numDigits)
cache.push_back(fiboIndex);
}
// simply look up the result
unsigned int tests;
std::cin >> tests;
while (tests--)
{
unsigned int numDigits;
std::cin >> numDigits;
std::cout << cache[numDigits] << std::endl;
}
return 0;
}

This solution contains 15 empty lines, 17 comments and 2 preprocessor commands.

# 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 "1 3" | ./25`

Output:

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

__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.4 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 24, 2017 submitted solution

April 4, 2017 added comments

# Hackerrank

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

My code solves **4** out of **4** 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.

# Links

projecteuler.net/thread=25 - **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-25-fibonacci-sequence-1000-digits/ (written by Kristian Edlund)

Haskell: github.com/nayuki/Project-Euler-solutions/blob/master/haskell/p025.hs (written by Nayuki)

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

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

C: github.com/eagletmt/project-euler-c/blob/master/20-29/problem25.c (written by eagletmt)

Javascript: github.com/dsernst/ProjectEuler/blob/master/25 1000-digit Fibonacci number.js (written by David Ernst)

Scala: github.com/samskivert/euler-scala/blob/master/Euler025.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 24 - Lexicographic permutations | Reciprocal cycles - problem 26 >> |