<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-12-highly-divisible-triangular-number/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="http://r.prevos.net/euler-problem-12-triangular-number/"> 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="Euler Problem 12: Divisors of triangular numbers." src="https://i1.wp.com/upload.wikimedia.org/wikipedia/commons/thumb/b/b0/Cuisenaire_ten.JPG/320px-Cuisenaire_ten.JPG?resize=320%2C162&ssl=1" data-recalc-dims="1">
<p class="wp-caption-text">The divisors of 10 illustrated with Cuisenaire rods: 1, 2, 5, and 10 (Wikipedia).</p>
</div>
<p>Euler Problem 12 takes us to the realm of <a target="_blank" rel="nofollow" href="https://en.wikipedia.org/wiki/Triangular_number">triangular numbers</a> and <a target="_blank" rel="nofollow" href="https://en.wikipedia.org/wiki/Divisor">proper divisors</a>.</p>
<p>The image on the left shows a hands-on method to visualise the number of divisors of an integer. <a target="_blank" rel="nofollow" href="https://en.wikipedia.org/wiki/Cuisenaire_rods">Cuisenaire rods</a> are learning aids that provide a hands-on way to explore mathematics.</p>
<h2>Euler Problem 12 Definition</h2>
<p>The sequence of triangle numbers is generated by adding the natural numbers. So the 7<sup>th</sup> triangle number would be <img title="1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 " alt="1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 " class="latex" src="http://s0.wp.com/latex.php?latex=1+%2B+2+%2B+3+%2B+4+%2B+5+%2B+6+%2B+7+%3D+28+&bg=ffffff&%23038;fg=000&%23038;s=0">. The first ten terms would be: <img title="1, 3, 6, 10, 15, 21, 28, 36, 45, 55, \ldots " alt="1, 3, 6, 10, 15, 21, 28, 36, 45, 55, \ldots " class="latex" src="http://s0.wp.com/latex.php?latex=1%2C+3%2C+6%2C+10%2C+15%2C+21%2C+28%2C+36%2C+45%2C+55%2C+%5Cldots+&bg=ffffff&%23038;fg=000&%23038;s=0"> Let us list the factors of the first seven triangle numbers:</p>
<p><strong>1</strong>: 1</p>
<p><strong>3</strong>: 1, 3</p>
<p><strong>6</strong>: 1, 2, 3, 6</p>
<p><strong>10</strong>: 1, 2, 5, 10</p>
<p><strong>15</strong>: 1, 3, 5, 15</p>
<p><strong>21</strong>: 1, 3, 7 ,21</p>
<p><strong>28</strong>: 1, 2, 4, 7, 14, 28</p>
<p>We can see that 28 is the first triangle number to have over five divisors. What is the value of <a target="_blank" rel="nofollow" href="https://projecteuler.net/problem=12">the first triangle number to have over five hundred divisors</a>?</p>
<h2>Solution</h2>
<p>Vishal Kataria explains a simple method to determine the number of divisors using prime factorization as explained by in his video below. The prime factorization of <img title="n " alt="n " class="latex" src="http://s0.wp.com/latex.php?latex=n+&bg=ffffff&%23038;fg=000&%23038;s=0"> is given by:</p>
<p><img title="n = p^{\alpha_1}_1 \times p^{\alpha_2}_2 \times p^{\alpha_k}_k " alt="n = p^{\alpha_1}_1 \times p^{\alpha_2}_2 \times p^{\alpha_k}_k " class="latex" src="http://s0.wp.com/latex.php?latex=n+%3D+p%5E%7B%5Calpha_1%7D_1+%5Ctimes+p%5E%7B%5Calpha_2%7D_2+%5Ctimes+p%5E%7B%5Calpha_k%7D_k+&bg=ffffff&%23038;fg=000&%23038;s=0"></p>
<p>The number of proper divisors is:</p>
<p><img title="d = (\alpha_1 + 1) (\alpha_2 + 1) \ldots (\alpha_k + 1) " alt="d = (\alpha_1 + 1) (\alpha_2 + 1) \ldots (\alpha_k + 1) " class="latex" src="http://s0.wp.com/latex.php?latex=d+%3D+%28%5Calpha_1+%2B+1%29%C2%A0%28%5Calpha_2+%2B+1%29+%5Cldots+%28%5Calpha_k+%2B+1%29+&bg=ffffff&%23038;fg=000&%23038;s=0"></p>
<p><iframe height="359" width="584" allowfullscreen="true" src="http://www.youtube.com/embed/jXRHfgqE1qY?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 code reuses the prime factorisation function developed for <a target="_blank" rel="nofollow" href="http://r.prevos.net/euler-problem-3/">Euler Problem 3</a>. This function results in a vector of all prime factors, e.g. the prime factors of 28 are 2, 2 and 7.</p>
<p>The code to solve this problem determines the values for alpha using the <a target="_blank" rel="nofollow" href="https://stat.ethz.ch/R-manual/R-devel/library/base/html/rle.html">run length function</a>. This function counts the number of times each element in a sequence is repeated. The outcome of this function is a vector of the values and the number of times each is repeated. The prime factors of 28 are 2 and 7 and their run lengths are 2 and 1. The number of divisors can now be determined.</p>
<p><img title="28 = 2^2 \times 7^1 " alt="28 = 2^2 \times 7^1 " class="latex" src="http://s0.wp.com/latex.php?latex=28+%3D+2%5E2+%5Ctimes+7%5E1+&bg=ffffff&%23038;fg=000&%23038;s=0"></p>
<p><img title="d = (2+1)(1+1) = 6 " alt="d = (2+1)(1+1) = 6 " class="latex" src="http://s0.wp.com/latex.php?latex=d+%3D+%282%2B1%29%281%2B1%29+%3D+6+&bg=ffffff&%23038;fg=000&%23038;s=0"></p>
<p>The code to solve Euler Problem 12 is shown below. The loop continues until it finds a triangular number with 500 divisors. The first two lines increment the index and create the next triangular number. The third line in the loop determines the number of times each factor is repeated (the run lengths). The last line calculates the number of divisors using the above-mentioned formula.</p>
<pre>
i &lt;- 0
divisors &lt;- 0
while (divisors &lt; 500) {
    i &lt;- i + 1
    triangle &lt;- (i * (i+1)) / 2
    pf &lt;- prime.factors(triangle)
    alpha &lt;- rle(pf)
    divisors &lt;- prod(alpha$lengths+1)
}
answer &lt;- triangle
print(answer)
</pre>
<p>The post <a target="_blank" rel="nofollow" href="http://r.prevos.net/euler-problem-12-triangular-number/">Euler Problem 12: Highly Divisible Triangular Number</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-12-triangular-number/"> 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/LqIi8-WDhs4"></a></div>