<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-14-longest-collatz-sequence/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="http://r.prevos.net/euler-problem-14-collatz-sequence/"> 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>Euler Problem 14 looks at the <a target="_blank" rel="nofollow" href="https://en.wikipedia.org/wiki/Collatz_conjecture">Collatz Conjecture</a>. These playful sequences, named after German mathematician Lothar Collatz (1910–1990), cause mathematicians a lot of headaches. This video introduces the problem much better than I can describe it.</p>
<p><iframe height="359" width="584" allowfullscreen="true" src="https://www.youtube.com/embed/5mFpVDpKX70?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>
<h2>Euler Problem 14 Definition</h2>
<p>The following iterative sequence is defined for the set of positive integers:</p>
<p><img title="n \rightarrow n/2 " alt="n \rightarrow n/2 " class="latex" src="http://s0.wp.com/latex.php?latex=n+%5Crightarrow+n%2F2+&bg=ffffff&%23038;fg=000&%23038;s=0"> ( <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 even)<br>
<img title="n \rightarrow 3n + 1 " alt="n \rightarrow 3n + 1 " class="latex" src="http://s0.wp.com/latex.php?latex=n+%5Crightarrow+3n+%2B+1+&bg=ffffff&%23038;fg=000&%23038;s=0"> ( <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 odd)</p>
<p>Using the rule above and starting with 13, we generate the following sequence:</p>
<p><img title="13 \rightarrow 40 \rightarrow 20 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1 " alt="13 \rightarrow 40 \rightarrow 20 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1 " class="latex" src="http://s0.wp.com/latex.php?latex=13+%5Crightarrow+40+%5Crightarrow+20+%5Crightarrow+10+%5Crightarrow+5+%5Crightarrow+16+%5Crightarrow+8+%5Crightarrow+4+%5Crightarrow+2+%5Crightarrow+1+&bg=ffffff&%23038;fg=000&%23038;s=0"></p>
<p>This sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1. <a target="_blank" rel="nofollow" href="https://projecteuler.net/problem=14">Which starting number, under one million, produces the longest chain?</a> Note: Once the chain starts the terms are allowed to go above one million.</p>
<h2>Solution</h2>
<p>This problem is highly computationally intensive and it highlights R’s lack of speed. Generating one million Collatz sequences and finding the longest one requires a lot more than a minute of processing time allowed for in Project Euler.</p>
<pre>
collatz.chain &lt;- function(n) {
    chain &lt;- vector()
    i &lt;- 1
    while (n! = 1) {
        if (n%%2 == 0) 
            n &lt;- n / 2
        else
            n &lt;- 3 * n + 1
        chain[i] &lt;- n
        i &lt;- i + 1
    }
    return(chain)
}
answer &lt;- 0
collatz.max &lt;- 0
for (n in 1:1E6) {
    collatz.length &lt;- length(collatz.chain(n)) 
    if (collatz.length > collatz.max) {
        answer &lt;- n
        collatz.max &lt;- collatz.length
        }
}
print(answer)
</pre>
<p>The second version of the code contains some optimisations. The code stores the length of all sequences in an array. When the code generates a sequence and lands on a number already analysed, then it adds that previous number to the current one and moves on. This approach requires more memory but saves a lot of computation time. A minor tweak to the code optimises the rule for uneven numbers. Tripling an uneven number and adding one will always result in an even number so we can skip one step. This solution is more than twice as fast as the first version.</p>
<pre>
collatz.length &lt;- vector(length=1e6)
collatz.length[1] &lt;- 0
for (n in 2:1e6) {
    x &lt;- n
    count &lt;- 0 while (x != 1 &amp; x >= n) {
        if (x %% 2 == 0) {
            x &lt;- x / 2
            count &lt;- count + 1
        }
        else {
            x &lt;- (3 * x + 1) / 2
            count &lt;- count + 2
        } 
    }
    count &lt;- count + collatz.length[x]
    collatz.length[n] &lt;- count
}
answer &lt;- which.max(collatz.length)
print(answer)
</pre>
<h2>Visualising Collatz Sequences</h2>
<p>The Collatz sequence is an example of a simple mathematical rule that can create an unpredictable pattern. The number of steps required to reach 1 is listed in <a target="_blank" rel="nofollow" href="https://oeis.org/A006577">A006577</a> of the Online Encyclopedia of Integer Sequences.</p>
<p>The image below visualises the number of steps for the first 1000 positive numbers. The scatterplot shows some interesting patterns. Does this visualisation show that the Collatz Sequence does have a pattern after all?</p>
<p><a target="_blank" rel="nofollow" href="https://i1.wp.com/r.prevos.net/wp-content/uploads/sites/11/2017/03/collatz-1.png"><img sizes="(max-width: 584px) 100vw, 584px" data-image-description="" data-orig-file="https://i1.wp.com/r.prevos.net/wp-content/uploads/sites/11/2017/03/collatz-1.png?fit=1718%2C962" data-orig-size="1718,962" data-image-title="collatz" class="wp-image-283" data-comments-opened="1" data-recalc-dims="1" data-attachment-id="283" title="Euler Problem 14: Number of halving and tripling steps to reach 1 in the Collatz problem." data-permalink="http://r.prevos.net/euler-problem-14-collatz-sequence/collatz-2/" alt="Euler Problem 14: Number of halving and tripling steps to reach 1 in the Collatz problem." data-medium-file="https://i1.wp.com/r.prevos.net/wp-content/uploads/sites/11/2017/03/collatz-1.png?fit=300%2C168" data-large-file="https://i1.wp.com/r.prevos.net/wp-content/uploads/sites/11/2017/03/collatz-1.png?fit=584%2C327" data-image-meta="{&quot;aperture&quot;:&quot;0&quot;,&quot;credit&quot;:&quot;&quot;,&quot;camera&quot;:&quot;&quot;,&quot;caption&quot;:&quot;&quot;,&quot;created_timestamp&quot;:&quot;0&quot;,&quot;copyright&quot;:&quot;&quot;,&quot;focal_length&quot;:&quot;0&quot;,&quot;iso&quot;:&quot;0&quot;,&quot;shutter_speed&quot;:&quot;0&quot;,&quot;title&quot;:&quot;&quot;,&quot;orientation&quot;:&quot;0&quot;}" src="https://i1.wp.com/r.prevos.net/wp-content/uploads/sites/11/2017/03/collatz-1.png?resize=584%2C327"></a></p>
<h2>Collatz Chains</h2>
<p>The Collatz sequences can also be visualised using networks. Each step between two numbers is an edge and the numbers are the vertices. For example, the network for the Collatz sequence for number 10 is 5–16, 16–8, 8–4, 4–2, 2–1. When generating subsequent sequences the network will start to overlap and a tree of sequences appears. The tree below combines the Collatz sequences for the numbers 2 to 26. Number 27 has a very long sequence, making the tree much harder to read.</p>
<div class="wp-caption"><a target="_blank" rel="nofollow" href="http://r.prevos.net/?attachment_id=413"><img sizes="(max-width: 584px) 100vw, 584px" data-image-description="" data-orig-file="https://i2.wp.com/r.prevos.net/wp-content/uploads/sites/11/2017/03/collatznetwork2-26.png?fit=1184%2C1183" data-orig-size="1184,1183" data-image-title="collatznetwork2-26" data-comments-opened="1" class="wp-image-413" data-recalc-dims="1" data-attachment-id="413" data-permalink="http://r.prevos.net/euler-problem-14-collatz-sequence/collatznetwork2-26/" alt="Network of Collatz sequences n=2-26" data-medium-file="https://i2.wp.com/r.prevos.net/wp-content/uploads/sites/11/2017/03/collatznetwork2-26.png?fit=300%2C300" data-large-file="https://i2.wp.com/r.prevos.net/wp-content/uploads/sites/11/2017/03/collatznetwork2-26.png?fit=584%2C584" data-image-meta="{&quot;aperture&quot;:&quot;0&quot;,&quot;credit&quot;:&quot;&quot;,&quot;camera&quot;:&quot;&quot;,&quot;caption&quot;:&quot;&quot;,&quot;created_timestamp&quot;:&quot;0&quot;,&quot;copyright&quot;:&quot;&quot;,&quot;focal_length&quot;:&quot;0&quot;,&quot;iso&quot;:&quot;0&quot;,&quot;shutter_speed&quot;:&quot;0&quot;,&quot;title&quot;:&quot;&quot;,&quot;orientation&quot;:&quot;0&quot;}" src="https://i2.wp.com/r.prevos.net/wp-content/uploads/sites/11/2017/03/collatznetwork2-26.png?resize=584%2C584"></a>
<p class="wp-caption-text">Network of Collatz sequences n=2-26</p>
</div>
<pre>
edgelist &lt;- data.frame(a = 2, b = 1)
for (n in 3:26) {
   chain &lt;- as.character(c(n, collatz.chain(n)))
   chain &lt;- data.frame(a = chain[-length(chain)], b = chain[-1])
   edgelist &lt;- rbind(edgelist, chain)
}
library(igraph)
g &lt;- graph.edgelist(as.matrix(edgelist))
g &lt;- simplify(g)
par(mar=rep(0,4))
V(g)$color &lt;- degree(g, mode = &quot;out&quot;) + 1
plot(g, 
     layout=layout.kamada.kawai,
     vertex.color=V(g)$color, 
     vertex.size=6,
     vertex.label.cex=.7,
     vertex.label.color=&quot;black&quot;,
     edge.arrow.size=.1,
     edge.color=&quot;black&quot;
     )
</pre>
<p> </p>
<p>The post <a target="_blank" rel="nofollow" href="http://r.prevos.net/euler-problem-14-collatz-sequence/">Euler Problem 14: Longest Collatz Sequence</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-14-collatz-sequence/"> 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/X-ZAI9NqhH8"></a></div>