Project Euler Problem 25 Pitfalls

Project Euler problem 25 is reasonably straighforward. It asks you to find the first term in the Fibonacci sequence with more than 1000 digits. In ones like these, not reading the question properly is more likely to be your downfall than anything else. So:

  • Give the number of the first term which has 1000 digits, not the 1000-digit number itself
  • Make sure your Fibonacci number generator gives you the sequence correctly: ie F(1)=1 and F(2)=1. If you have F(1)=1 and F(2)=2, you’ll be off by one!
  • Lastly, and this only really applies to my own thickness… If the comment for your Fibonacci number generator says “returns nth Fibonacci number”, make sure it returns the nth Fibonacci number and not a Fibonacci number less than n.
  • If you’re getting a number greater than 5000 you’re off, recheck. Good luck!

Project Euler Problem 11

Just a hint, so you don’t go down the wrong path. You probably won’t, but if you don’t want any hints, stop reading this article!

PS If you don’t know what Project Euler is, I recommend having a look at their website, or just getting an idea from the problems themselves.

What is Project Euler?

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

Now problem / puzzle 11:

In the 2020 grid below, four numbers along a diagonal line have been marked in red.

(snip)

The product of these numbers is 26 63 78 14 = 1788696.

What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 2020 grid?

Just a hint for those of you who spent too long on this like me: it’s essentially a word search. One of these but with numbers.

You see, when I got the wrong answer a couple times I reread the question, and figure “adjacent” just meant anywhere beside each other – eg a square of four numbers, a t-shape. This is not the case! You don’t need to develop a path-finding bot that navigates 4 numbers, looking for the best options! Although, having done that, it’s actually quite fun! In python, at least, it’s quite concise and the code is pretty-looking.

Bonus points (or a packet of chocolate-coated raisins) to the first person who does implement such an algorithm. The answer I’m looking for is the highest product of the resulting 4 numbers, and leave it in the comments.

Bet I won’t get an answer!