<p><div><div><div><div data-width="100" data-show-faces="false" data-send="true" data-layout="button_count" data-height="21" data-href="https://www.r-bloggers.com/euler-problem-20-large-integer-factorials/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="http://r.prevos.net/euler-problem-20/"> 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>
<p><a target="_blank" rel="nofollow" href="http://sixo.deviantart.com/art/Shuffle-Animated-GIF-156993131"><img alt="Euler Problem 20" src="https://i1.wp.com/orig00.deviantart.net/8ced/f/2010/074/1/a/shuffle___animated_gif_by_sixo.gif?resize=327%2C220" data-recalc-dims="1"></a>Euler Problem 20 is the third problem that requires special consideration for working with very <a target="_blank" rel="nofollow" href="http://r.prevos.net/tag/large-integers/">large integers</a>. In this problem, we look at <a target="_blank" rel="nofollow" href="https://en.wikipedia.org/wiki/Factorial">factorials</a>. These numbers are useful in combinatorics if, for example, you like to know in how many ways you can arrange a deck of cards.</p>
<p>The problem with computing factorials is that they are mostly very large numbers, beyond the generic capabilities of computers to process. This problem can be solved using a specialised R package and using only base-R code.</p>
<h2>Euler Problem 20 Definition</h2>
<p><img title="n! = n times (n - 1) times (n-2) times ldots times 3 times 2 times 1 " alt="n! = n times (n - 1) times (n-2) times ldots times 3 times 2 times 1 " class="latex" src="http://s0.wp.com/latex.php?latex=n%21+%3D%C2%A0n+%5Ctimes+%28n+-%C2%A01%29+%5Ctimes+%28n-2%29+%5Ctimes+%5Cldots+%5Ctimes+3+%5Ctimes+2+%5Ctimes+1+&bg=ffffff&%23038;fg=000&%23038;s=0">.</p>
<p>For example: <img title=" 10! = 10 times 9 times ldots times 3 times 2 times 1 = 3628800 " alt=" 10! = 10 times 9 times ldots times 3 times 2 times 1 = 3628800 " class="latex" src="http://s0.wp.com/latex.php?latex=%C2%A010%21+%3D+10+%5Ctimes+9+%5Ctimes+%5Cldots+%5Ctimes+3+%5Ctimes+2+%5Ctimes+1+%3D+3628800+&bg=ffffff&%23038;fg=000&%23038;s=0">.</p>
<p>The sum of the digits in the number <img title="10! " alt="10! " class="latex" src="http://s0.wp.com/latex.php?latex=10%21+&bg=ffffff&%23038;fg=000&%23038;s=0"> is <img title="3 + 6 + 2 + 8 + 8 + 0 + 0 = 27 " alt="3 + 6 + 2 + 8 + 8 + 0 + 0 = 27 " class="latex" src="http://s0.wp.com/latex.php?latex=3+%2B+6+%2B+2+%2B+8+%2B+8+%2B+0+%2B+0%C2%A0%3D+27+&bg=ffffff&%23038;fg=000&%23038;s=0">.</p>
<p><a target="_blank" rel="nofollow" href="https://projecteuler.net/problem=20">Find the sum of the digits in the number 100!</a></p>
<h2>Euler Problem 20 Solution</h2>
<p>The factorial of the number 100 contains 158 digits, which is a lot more digits than a 64-bit operating system can accurately produce. Using the standard function: factorial(100) = 9.332622e+157. Without using a specialised algorithm, we cannot determine the sum of all digits. We need to deploy <a target="_blank" rel="nofollow" href="https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic">arbitrary-precision arithmetic</a> to solve this problem.</p>
<p>Many computer languages, including R, have special libraries to deal with such large numbers. The <a target="_blank" rel="nofollow" href="https://cran.r-project.org/web/packages/gmp/index.html">GMP Multiple Precision Arithmetic</a> package renders this problem almost trivial.</p>
<pre>
library(gmp)
digits &lt;- factorialZ(100)
digits &lt;- as.character(digits)
answer &lt;- sum(as.numeric(unlist(strsplit(digits, &quot;&quot;))))
</pre>
<h2>Base-R Code</h2>
<p>The problem becomes more interesting when only using basic R code. I developed the big.add function to solve <a target="_blank" rel="nofollow" href="http://r.prevos.net/euler-problem-13/">Euler Problem 13</a> through the addition of very large integers. We can extend this function to also calculate factorials. A factorial can be replaced by a series of additions, for example:</p>
<p><img title="3! = 1 times 2 times 3 = (((1+1) + (1+1)) + (1+1)) " alt="3! = 1 times 2 times 3 = (((1+1) + (1+1)) + (1+1)) " class="latex" src="http://s0.wp.com/latex.php?latex=3%21+%3D+1+%5Ctimes+2+%5Ctimes+3+%3D+%28%28%281%2B1%29+%2B+%281%2B1%29%29+%2B+%281%2B1%29%29+&bg=ffffff&%23038;fg=000&%23038;s=0"></p>
<p>This can be mimicked in R using the <a target="_blank" rel="nofollow" href="http://adv-r.had.co.nz/Functionals.html#functionals-fp">Reduce function</a>. This function reduces a vector to a single value by recursively calling a function. Reduce(“+”, rep(4, 5)) is the same as:</p>
<p><img title="4 times 5 = ((((4 + 4) + 4) + 4) + 4) = 20 " alt="4 times 5 = ((((4 + 4) + 4) + 4) + 4) = 20 " class="latex" src="http://s0.wp.com/latex.php?latex=4+%5Ctimes+5+%3D+%28%28%28%284+%2B+4%29+%2B+4%29+%2B+4%29+%2B+4%29+%3D+20+&bg=ffffff&%23038;fg=000&%23038;s=0"></p>
<p>Using a loop, we can use the Reduce function to calculate a factorial, using only additions:</p>
<pre>
fact &lt;- 1
x &lt;- 100
for (i in 2:x) {
    fact &lt;- Reduce(&quot;+&quot;, rep(fact, i))
}
print(fact)
</pre>
<p>The <em>big.factorial</em> function below implements this idea by combining the <em>big.add</em> and <em>Reduce</em> functions to calculate large integer factorials. The function returns a value of 1 when the factorial of 0 or 1 is requested. This function does not calculate the <a target="_blank" rel="nofollow" href="https://en.wikipedia.org/wiki/Gamma_function">Gamma-function</a> for fractions. For all other values, it goes through a loop from 2 to the requested factorial. The temporary values are stored in the <em>bf</em> variable. The code loops through the factorials by using the result of the previous <em>Reduce</em> call into the current one.</p>
<pre>
big.factorial &lt;- function(x) {
    x &lt;- floor(x)
    bf &lt;- 1 if (x > 1) {
        for (i in 2:x) {
            bf &lt;- Reduce(big.add, rep(bf,i))
        }
    }
    return (bf)
}

digits &lt;- big.factorial(100)
answer &lt;- sum(as.numeric(unlist(strsplit(as.character(digits), &quot;&quot;))))
print(answer)
</pre>
<p>This function is most certainly not as fast as the GMP package but it was fun to write and to learn about the mechanics behind arbitrary precision arithmetic at work.</p>
<p>If you like to know how factorials can be used to determine the number of ways a deck can be shuffled the watch this video.</p>
<p><iframe width="450" allowfullscreen="true" src="https://www.youtube.com/embed/uNS1QvDzCVw?version=3&rel=1&%23038;fs=1&%23038;autohide=2&%23038;showsearch=0&%23038;showinfo=1&%23038;iv_load_policy=1&%23038;wmode=transparent" type="text/html"></iframe></p>
<p>The post <a target="_blank" rel="nofollow" href="http://r.prevos.net/euler-problem-20/">Euler Problem 20: Large Integer Factorials</a> appeared first on <a target="_blank" rel="nofollow" href="http://r.prevos.net/">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-20/"> 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 title="The R Project for Statistical Computing" rel="nofollow" href="https://www.r-project.org/">R</a> news and <a title="R tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/tutorial">tutorials</a> on topics such as: <a title="Data science" rel="nofollow" href="https://www.r-bloggers.com/search/data%20science">Data science</a>, <a title="Big Data" rel="nofollow" href="https://www.r-bloggers.com/search/Big%20Data">Big Data, <a title="R jobs" rel="nofollow" href="https://www.r-users.com/">R jobs</a>, visualization (<a title="ggplot and ggplot2 tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/ggplot2">ggplot2</a>, <a title="Boxplots using lattice and ggplot2 tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/boxplot">Boxplots</a>, <a title="Maps and gis" rel="nofollow" href="https://www.r-bloggers.com/search/map">maps</a>, <a title="Animation in R" rel="nofollow" href="https://www.r-bloggers.com/search/animation">animation</a>), programming (<a title="RStudio IDE for R" rel="nofollow" href="https://www.r-bloggers.com/search/RStudio">RStudio</a>, <a title="Sweave and literate programming" rel="nofollow" href="https://www.r-bloggers.com/search/sweave">Sweave</a>, <a title="LaTeX in R" rel="nofollow" href="https://www.r-bloggers.com/search/LaTeX">LaTeX</a>, <a title="SQL and databases" rel="nofollow" href="https://www.r-bloggers.com/search/SQL">SQL</a>, <a title="Eclipse IDE for R" rel="nofollow" href="https://www.r-bloggers.com/search/eclipse">Eclipse</a>, <a title="git and github, Version Control System" rel="nofollow" href="https://www.r-bloggers.com/search/git">git</a>, <a title="Large data in R using Hadoop" rel="nofollow" href="https://www.r-bloggers.com/search/hadoop">hadoop</a>, <a title="Web Scraping of google, facebook, yahoo, twitter and more using R" rel="nofollow" href="https://www.r-bloggers.com/search/Web+Scraping">Web Scraping</a>) statistics (<a title="Regressions and ANOVA analysis tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/regression">regression</a>, <a title="principal component analysis tutorial" rel="nofollow" href="https://www.r-bloggers.com/search/PCA">PCA</a>, <a title="Time series" rel="nofollow" href="https://www.r-bloggers.com/search/time+series">time series</a>, <a title="finance trading" rel="nofollow" href="https://www.r-bloggers.com/search/trading">trading</a>) and more...
<img height="1" alt="" width="1" src="http://feeds.feedburner.com/~r/RBloggers/~4/npaWbA8RUKs"></a></div>