Project Euler 25: Fibonacci number with 1000 digits
Peter Prevos |
576 words | 3 minutes
Share this content
Project Euler 25 asks us back to the Fibonacci numbers. This famous number sequence describes many natural processes, such as the patterns in this beautiful sunflower. The seeds inside the sunflower grow in a spiral pattern, and the number of spirals tends to be a Fibonacci number. This pattern is the most efficient way to pack the centre with as many seeds as possible.
Famous mathematician and father of computer science Alan Turing was fascinated by this problem until his death. In 2016, the Royal Society published a journal article that builds on his work in the Open Science journal. They collected sunflowers from citizen scientists from around the world and confirmed that for the majority of sunflowers, the number of spirals is a Fibonacci number. They did, however, also discover other patterns. Euler Problem 25 is a bit less poetic as it only asks to generate a huge Fibonacci number.
Project Euler 25 Definition
The Fibonacci sequence is defined by a recurrence relation:
$$F_n = F_{n-1} + F_{n-2} \quad | \quad F_1 = 1, F_2 = 1$$
The 12th term, \(F_{12}=144\), is the first term to contain three digits.
What is the index of the first term in the Fibonacci sequence to contain 1000 digits?
Large Integers in R
By default, numbers with more than 7 digits are shown in scientific notation in R, which reduces the accuracy of the calculation. You can change the precision of large integers with the options() function, but R struggles with integers with more than 22 digits. This example illustrates this issue:
factorial(24)
[1] 6.204484e+23
options(digits = 22)
factorial(24)
[1] 620448401733239409999872Finding a number with 1000 digits is a problem in R with using a special function or package. This article explains how to solve this problem using the GMP package and in base R code.
Project Euler 25 Solution in R
We have already seen various ways to generate Fibonacci numbers in R using a recursive function, a while loop and the GMP library in Euler Problem 2.
Arbitrary-Precision Arithmetic
The first solution uses the GMP package to manage large integers. This package implements the GNU Multiple Precision Arithmetic Library for working with huge numbers. This package also contains a function to generate Fibonacci numbers. This solution cycles through the Fibonacci sequence until it finds a number with 1000 digits.
## Project Euler 25: Fibonacci number with 1000 digits
## GNU Multiple Precision Arithmetic Library
library(gmp)
answer <- 1
fib <- 1
while (nchar(as.character(fib)) <= 1000) {
fib <- fibnum(answer) # Determine next Fibonacci number
answer <- answer + 1
}
print(answer)R-base code
This is a very fast solution but my aim is to solve the first 100 Project Euler problems using only base-R code. The big.add() function I developed to solve Euler Problem 13 uses only basic R to add large numbers. This function multiplies large numbers in the same way you would do on a piece of paper. This code to solve Euler Problem 25 is much slower than the GMP library but it was fun to develop.
## Base-R Solution
fib <- 1 # First Fibonaci number
cur <- 1 # Current number in sequence
pre <- 1 # Previous number in sequence
answer <- 2
while (nchar(fib) < 1000) {
fib <- big.add(cur, pre) # Determine next Fibonacci number
pre <- cur
cur <- fib
answer <- answer + 1
}
print(answer)Share this content
