Large integers in R: Fibonacci number with 1000 digits, Euler Problem 25

The Fibonacci Sequence in nature: The nautilus shell. Euler problem 25

The Fibonacci Sequence occurs in nature: The nautilus shell.

Euler Problem 25 takes us back to the Fibonacci sequence and the problems related to working with very large integers.

The Fibonacci sequence follows a simple mathematical rule but it can create things of great beauty. This pattern occurs quite often in nature, like to nautilus shell shown in the image. The video by Arthur Benjamin at the end of this post illustrates some of the magic of this sequence.

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] 620448401733239409999872

However, finding a number of 1000 digits is a problem with using special functions.

Euler Problem 25 Definition

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 . 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?

Proposed Solutions

The first solution uses the GMP library to manage very large integers. This library also contains a function to generate Fibonacci numbers. This solution cycles through the Fibonacci sequence until it finds a number with 1000 digits.

library(gmp) # GNU Multiple Precision Arithmetic Library
n <- 1
fib <- 1
while (nchar(as.character(fib)) < 1000) {
   fib <- fibnum(n) # Determine next Fibonacci number
   n <- n + 1
}
answer <- n
print(answer)

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.

t <- proc.time()
fib <- 1 # First Fibonaci number
cur <- 1 # Current number in sequence
pre <- 1 # Previous number in sequence
index <- 2
while (nchar(fib) < 1000) {
    fib <- big.add(cur, pre) # Determine next Fibonacci number
    pre <- cur
    cur <- fib
    index <- index + 1
}
answer <- index
print(answer)

This code is much slower than the GMP library but is was fun to develop.

The Magic of the Fibonacci Numbers

Euler Problem 2: Even Fibonacci Numbers

Euler Problem 2 Definition

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \ldots

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Solution

The code generates Fibonacci numbers until it reaches the value of four million. The code then sums the even numbers in the sequence.

fib <- c(1, 2)  #Define first two numbers
while (max(fib) < 4e+06) {
    # Generate Fibonacci numbers until limit is reached
    len <- length(fib)
    fib <- c(fib, fib[len - 1] + fib[len])
}
answer <- sum(fib[fib%%2 == 0])

A range of packages exists that generate Fibonacci numbers. The gmp package for Multiple Precision Arithmetic and the numbers package supplies functions to calculate the nth Fibonacci number. This package is also able to work with very large numbers.

library(gmp)
i <- 1
answer <- 0
fib <- fibnum(1)
while (fibnum(i) <= 4e6) {
    fib <- fibnum(i)
    if (fib%%2==0) answer <- answer + fib
    i <- i + 1
}
print(answer)

Fibonacci Numbers as a magic trick

Fibonacci numbers describe many natural processes and can also be used to create magic tricks. The Missing Square Puzzle is based on this principle.

By Trekky0623 at English Wikipedia (Transferred from en.wikipedia to Commons.) [Public domain], via Wikimedia Commons

By Trekky0623 at English Wikipedia (Transferred from en.wikipedia to Commons.) [Public domain], via Wikimedia Commons