<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/euler-problem-33-digit-cancelling-fractions-and-ford-circles/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="https://lucidmanager.org/euler-problem-33/"> The Devil is in the Data – The Lucid Manager</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<p>Euler Problem 33 takes us back to the world of fractions from our primary school days. Many kids hate and struggle learning about fractions but once you master them, a new world of numbers opens up. Unfortunately, the proliferation of digital calculators has negated the use of fractions in favour of decimal expressions. <a rel="nofollow" href="https://lucidmanager.org/euler-problem-26/" target="_blank">Fractions</a> are an aesthetic way to express numbers, without having to resort to ugly random sequences of decimals. This is why I prefer to use 22/7 as an <a rel="nofollow" href="https://lucidmanager.org/approximations-of-pi/" target="_blank">approximation of Pi</a> over the ugly infinite series of decimals.</p>
<p>This Numberphile video below explains fractions and Farey sequences. A Farey sequence contains all fractions between 0 and 1 with a maximum denominator. More formally, a <a rel="nofollow" href="https://en.wikipedia.org/wiki/Farey_sequence" target="_blank">Farey sequence</a> of order <em>n</em> is the sequence of completely reduced fractions between 0 and 1 which, when in lowest terms, have denominators less than or equal to <img alt="n" title="n" src="https://s0.wp.com/latex.php?latex=n&bg=ffffff&%23038;fg=000&%23038;s=2" class="latex">, arranged in order of increasing size. For example, the Farey Sequence with order 3 is:</p>
<p><img alt="F_3 = Big{ frac{0}{1},frac{1}{3},frac{1}{2},frac{2}{3},frac{1}{1}Big}" title="F_3 = Big{ frac{0}{1},frac{1}{3},frac{1}{2},frac{2}{3},frac{1}{1}Big}" src="https://s0.wp.com/latex.php?latex=F_3+%3D+%5CBig%5C%7B+%5Cfrac%7B0%7D%7B1%7D%2C%5Cfrac%7B1%7D%7B3%7D%2C%5Cfrac%7B1%7D%7B2%7D%2C%5Cfrac%7B2%7D%7B3%7D%2C%5Cfrac%7B1%7D%7B1%7D%5CBig%5C%7D&bg=ffffff&%23038;fg=000&%23038;s=3" class="latex"></p>
<p>These sequences can be visualised in fractal-esque Ford Circles, but before we get to this, first solve Euler problem 33.</p>
<p><iframe allowfullscreen="true" src="https://www.youtube.com/embed/0hlvhQZIOQw?version=3&rel=1&%23038;fs=1&%23038;autohide=2&%23038;showsearch=0&%23038;showinfo=1&%23038;iv_load_policy=1&%23038;wmode=transparent" width="450" type="text/html"></iframe></p>
<h2>Euler Problem 33 Definition</h2>
<p>The fraction <sup>49</sup>/<sub>98</sub> is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that <sup>49</sup>/<sub>98</sub> = <sup>4</sup>/<sub>8</sub>, which is correct, is obtained by cancelling the 9s. We shall consider fractions like <sup>30</sup>/<sub>50</sub> = <sup>3</sup>/<sub>5</sub>, to be trivial examples.</p>
<p>There are exactly four nontrivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator. If the product of these four fractions is given in its lowest common terms, <a rel="nofollow" href="https://projecteuler.net/problem=33" target="_blank">find the value of the denominator</a>.</p>
<h2>Proposed Solution in R</h2>
<p>To solve this problem, we create a pseudo-Farey sequence by generating all different fractions with two decimals in the numerator and denominator. The loop generates all combinations of demoninators and numerators, excluding the trivial ones (multiples of 10 and 11). This solution converts the numbers to strings, strips any common duplicates, and tests the condition. The code concatenates vectors, which is not good practice. However, the loop is so short it does not matter much.</p>
<p>You can view the code below or download it from my <a rel="nofollow" href="https://github.com/pprevos/r.prevos.net/blob/master/ProjectEuler/problem033.R" target="_blank">GitHub page</a>.</p>
<pre>
num &lt;- vector()
den &lt;- vector()
for (a in 11:99) {
    for (b in (a + 1):99) {
        trivial &lt;- (a %% 10 == 0 | b &amp;&amp; 10 == 0 | a %% 11 == 0 | b %% 11 == 0)
        if (!trivial) {
            i &lt;- as.numeric(unlist(strsplit(as.character(a), &quot;&quot;)))
            j &lt;- as.numeric(unlist(strsplit(as.character(b), &quot;&quot;)))
            digs &lt;- c(i, j)
            dup &lt;- digs[duplicated(digs)]
            digs &lt;- digs[which(digs != dup)]
            if (length(digs) == 2 &amp; a/b == digs[1]/digs[2]) {
                num &lt;- c(num, a)
                den &lt;- c(den, b)
                }
        }
    }
}
answer &lt;- prod(den) / prod(num)
print(answer)
</pre>
<h2>Farey Sequences and Ford Circles</h2>
<p>Next step is to generalise Euler problem 33 and write a function to generate Farey Sequences and visualise them using Ford Circles.</p>
<p>The <code>farey</code> function generates a data table with the numerators (p) and denominators (q) of a Farey sequence. The function builds a list of all possible fractions for the solution space, excluding those with one as a Greatest Common Dominator, as defined by the <code>gcc</code> function.</p>
<pre>
farey &lt;- function(n) {
    fseq &lt;- list()
    fseq[[1]] &lt;- c(0, 1)
    i &lt;- 2
    gcd &lt;- function(a, b) { # Euclid's method
        if (a == 0) return(b)
        if (b == 0) return(a)
        gcd(b, a%%b)
    }
    for (q in 2:n) {
        for (p in 1:(q - 1)){
            if (gcd(p, q) == 1) {
                fseq[[i]] &lt;- c(p, q)
                i &lt;- i + 1
                }
        }
    }
    fseq[[i]] &lt;- c(1, 1)
    fseq &lt;- as.data.frame(do.call(rbind, fseq))
    names(fseq) &lt;- c(&quot;p&quot;, &quot;q&quot;)
    fseq &lt;- fseq[order(fseq$p / fseq$q), ]
    return(fseq)
}
</pre>
<p>Standard ggplot2 cannot draw circles where the radius of the circles is related to the coordinate system. I tried to use the <a rel="nofollow" href="https://cran.r-project.org/web/packages/ggforce/vignettes/Visual_Guide.html" target="_blank">ggforce</a> package to plot circles in ggplot2, but for some reason, I was not able to install this package on Ubuntu. As an alternative, I used a circle function sourced from <a rel="nofollow" href="https://stackoverflow.com/questions/6862742/draw-a-circle-with-ggplot2" target="_blank">StackOverflow</a>. This function is called in a for-loop to build the circles on top of the empty canvas.</p>
<figure class="wp-caption"><a rel="nofollow" href="https://lucidmanager.org/euler-problem-33/fordcircles/" target="_blank"><img data-orig-file="https://i1.wp.com/lucidmanager.org/wp-content/uploads/sites/2/2017/10/FordCircles.png?fit=2096%2C2097&amp;ssl=1" data-orig-size="2096,2097" data-medium-file="https://i1.wp.com/lucidmanager.org/wp-content/uploads/sites/2/2017/10/FordCircles.png?fit=300%2C300&amp;ssl=1" data-attachment-id="5098" data-image-meta="{" data-image-description="" src="https://i1.wp.com/lucidmanager.org/wp-content/uploads/sites/2/2017/10/FordCircles.png?resize=731%2C731" data-permalink="https://lucidmanager.org/euler-problem-33/fordcircles/" data-large-file="https://i1.wp.com/lucidmanager.org/wp-content/uploads/sites/2/2017/10/FordCircles.png?fit=731%2C731&amp;ssl=1" alt="Farey Sequence and Ford Circles: Euler Problem 33" data-image-title="FordCircles" sizes="(max-width: 731px) 100vw, 731px" width="450" data-comments-opened="1" class="wp-image-5098" data-recalc-dims="1"></a><figcaption class="wp-caption-text">Farey Sequence and Ford Circles (n = 20).</figcaption></figure>
<pre>
library(tidyverse)
lm_palette &lt;- c(&quot;#008da1&quot;, &quot;#005395&quot;, &quot;#262e43&quot;, &quot;#3b2758&quot;, &quot;#865596&quot;, &quot;#f26230&quot;)
ford_circles &lt;- farey(20) %>%
    mutate(x = p / q,
           y = 1 / (2* q^2),
           r = y,
           c = lm_palette[(q - 1)%%6 + 1])

g_circle &lt;- function(r, x, y, color = NA, fill = &quot;black&quot;, ...) {
    x &lt;- x + r * cos(seq(0, pi, length.out = 100))
    ymax &lt;- y + r * sin(seq(0, pi, length.out = 100))
    ymin &lt;- y + r * sin(seq(0, -pi, length.out = 100))
    annotate(&quot;ribbon&quot;, x = x, ymin = ymin, ymax = ymax,
             color = color, fill = fill, ...)
}

p &lt;- ggplot(ford_circles, aes(x, y))
for (i in 1:nrow(ford_circles)) {
    p &lt;- p + g_circle(ford_circles$r[i], ford_circles$x[i], ford_circles$y[i],
                      fill = ford_circles$c[i])
}
p + xlim(c(0, 1)) + coord_fixed() + theme_void()
</pre>
<p>The post <a rel="nofollow" href="https://lucidmanager.org/euler-problem-33/" target="_blank">Euler Problem 33: Digit Cancelling Fractions and Ford Circles</a> appeared first on <a rel="nofollow" href="https://lucidmanager.org/" target="_blank">The Lucid Manager</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="https://lucidmanager.org/euler-problem-33/"> The Devil is in the Data – The Lucid Manager</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 alt="" width="1" src="http://feeds.feedburner.com/~r/RBloggers/~4/5i3h-BngYPk" height="1"></a></div>