<p><div><div><div><div data-show-faces="false" data-height="21" data-width="100" data-layout="button_count" data-send="true" data-href="https://www.r-bloggers.com/large-integers-in-r-fibonacci-number-with-1000-digits-euler-problem-25/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="http://r.prevos.net/euler-problem-25/"> The Devil is in the Data</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<div class="wp-caption"><img alt="The Fibonacci Sequence in nature: The nautilus shell. Euler problem 25" src="https://i2.wp.com/2ff8n03drmib1b12373aauek-wpengine.netdna-ssl.com/assets/images/Art/Fibronacci/nautilus%20shell.jpg?resize=257%2C208" data-recalc-dims="1">
<p class="wp-caption-text">The Fibonacci Sequence occurs in nature: The nautilus shell.</p>
</div>
<p>Euler Problem 25 takes us back to the Fibonacci sequence and the problems related to working with very <a rel="nofollow" href="http://r.prevos.net/tag/large-integers/" target="_blank">large integers</a>.</p>
<p>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.</p>
<h2><span>Large Integers in R</span></h2>
<p>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 <em>options</em> function but R struggles with integers with more than 22 digits. This example illustrates this issue.</p>
<pre>
factorial(24)
[1] 6.204484e+23
> options(digits=22)
> factorial(24)
[1] 620448401733239409999872
</pre>
<p>However, finding a number of 1000 digits is a problem with using special functions.</p>
<h2>Euler Problem 25 Definition</h2>
<p>The Fibonacci sequence is defined by the recurrence relation:</p>
<p><img alt="F_n = F_{n-1} + F_{n-2} " title="F_n = F_{n-1} + F_{n-2} " src="http://s0.wp.com/latex.php?latex=F_n+%3D+F_%7Bn-1%7D+%2B+F_%7Bn-2%7D+&bg=ffffff&fg=000&s=0" class="latex">, where <img alt="F_1 = 1 " title="F_1 = 1 " src="http://s0.wp.com/latex.php?latex=F_1+%3D+1+&bg=ffffff&fg=000&s=0" class="latex"> and <img alt="F_2 = 1 " title="F_2 = 1 " src="http://s0.wp.com/latex.php?latex=F_2+%3D+1+&bg=ffffff&fg=000&s=0" class="latex">. The 12<sup>th</sup> term, <img alt="F_{12} " title="F_{12} " src="http://s0.wp.com/latex.php?latex=F_%7B12%7D+&bg=ffffff&fg=000&s=0" class="latex">, is the first term to contain three digits.</p>
<p>What is the index of the <a rel="nofollow" href="https://projecteuler.net/problem=25" target="_blank">first term in the Fibonacci sequence to contain 1000 digits</a>?</p>
<h2>Proposed Solutions</h2>
<p>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.</p>
<pre>
library(gmp) # GNU Multiple Precision Arithmetic Library
n &lt;- 1
fib &lt;- 1
while (nchar(as.character(fib)) &lt; 1000) {
   fib &lt;- fibnum(n) # Determine next Fibonacci number
   n &lt;- n + 1
}
answer &lt;- n
print(answer)
</pre>
<p>This is a very fast solution but my aim is to solve the first 100 Project Euler problems using only base-R code. The <em>big.add</em> function I developed to solve <a rel="nofollow" href="http://r.prevos.net/euler-problem-13/" target="_blank">Euler Problem 13</a>.</p>
<pre>
t &lt;- proc.time()
fib &lt;- 1 # First Fibonaci number
cur &lt;- 1 # Current number in sequence
pre &lt;- 1 # Previous number in sequence
index &lt;- 2
while (nchar(fib) &lt; 1000) {
    fib &lt;- big.add(cur, pre) # Determine next Fibonacci number
    pre &lt;- cur
    cur &lt;- fib
    index &lt;- index + 1
}
answer &lt;- index
print(answer)
</pre>
<p>This code is much slower than the GMP library but is was fun to develop.</p>
<h2>The Magic of the Fibonacci Numbers</h2>
<p><iframe allowfullscreen="true" src="https://www.youtube.com/embed/SjSHVDfXHQ4?version=3&rel=1&fs=1&autohide=2&showsearch=0&showinfo=1&iv_load_policy=1&wmode=transparent" width="450" type="text/html"></iframe></p>
<p>The post <a rel="nofollow" href="http://r.prevos.net/euler-problem-25/" target="_blank">Large integers in R: Fibonacci number with 1000 digits, Euler Problem 25</a> appeared first on <a rel="nofollow" href="http://r.prevos.net/" target="_blank">The Devil is in the Data</a>.</p>
	<p>
<div>
<div>To <strong>leave a comment</strong> for the author, please follow the link and comment on their blog: <strong><a href="http://r.prevos.net/euler-problem-25/"> The Devil is in the Data</a></strong>.</div>
<hr>
<a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers.com</a> offers <strong><a rel="nofollow" href="https://feedburner.google.com/fb/a/mailverify?uri=RBloggers">daily e-mail updates</a></strong> about <a rel="nofollow" href="https://www.r-project.org/" title="The R Project for Statistical Computing">R</a> news and <a rel="nofollow" href="https://www.r-bloggers.com/search/tutorial" title="R tutorials">tutorials</a> on topics such as: <a rel="nofollow" href="https://www.r-bloggers.com/search/data%20science" title="Data science">Data science</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Big%20Data" title="Big Data">Big Data, <a rel="nofollow" href="https://www.r-users.com/" title="R jobs">R jobs</a>, visualization (<a rel="nofollow" href="https://www.r-bloggers.com/search/ggplot2" title="ggplot and ggplot2 tutorials">ggplot2</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/boxplot" title="Boxplots using lattice and ggplot2 tutorials">Boxplots</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/map" title="Maps and gis">maps</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/animation" title="Animation in R">animation</a>), programming (<a rel="nofollow" href="https://www.r-bloggers.com/search/RStudio" title="RStudio IDE for R">RStudio</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/sweave" title="Sweave and literate programming">Sweave</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/LaTeX" title="LaTeX in R">LaTeX</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/SQL" title="SQL and databases">SQL</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/eclipse" title="Eclipse IDE for R">Eclipse</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/git" title="git and github, Version Control System">git</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/hadoop" title="Large data in R using Hadoop">hadoop</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Web+Scraping" title="Web Scraping of google, facebook, yahoo, twitter and more using R">Web Scraping</a>) statistics (<a rel="nofollow" href="https://www.r-bloggers.com/search/regression" title="Regressions and ANOVA analysis tutorials">regression</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/PCA" title="principal component analysis tutorial">PCA</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/time+series" title="Time series">time series</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/trading" title="finance trading">trading</a>) and more...
<img width="1" alt="" src="http://feeds.feedburner.com/~r/RBloggers/~4/W4BpGoc5IZ8" height="1"></a></div>