Project Euler 33: Digit Cancelling Fractions
Peter Prevos |
772 words | 4 minutes
Share this content
Project Euler 33 takes us back to the world of fractions from our primary school days. This article provides a solution for the Euler problem and discusses how to solve this problem using Farey sequences and how to visualise Ford Circles with the ggplot2 package.
Project Euler 33 Definition
The fraction 49/98 is curious, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the nines. We shall consider fractions like 30/50 = 3/5, to be trivial examples.
There are precisely 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, find the value of the denominator.
Proposed Solution in R
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 denominators 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.
## Project Euler 33: Digit Cancelling Fractions
num <- vector()
den <- vector()
for (a in 11:99) {
for (b in (a + 1):99) {
trivial <- (a %% 10 == 0 | b && 10 == 0 | a %% 11 == 0 | b %% 11 == 0)
if (!trivial) {
i <- as.numeric(unlist(strsplit(as.character(a), "")))
j <- as.numeric(unlist(strsplit(as.character(b), "")))
digs <- c(i, j)
dup <- digs[duplicated(digs)]
digs <- digs[which(digs != dup)]
if (length(digs) == 2 & a/b == digs[1]/digs[2]) {
num <- c(num, a)
den <- c(den, b)
}
}
}
}
paste(num, den, sep = "/")
answer <- prod(den) / prod(num)
print(answer)Farey Sequences and Ford Circles
Next step is to generalise Euler problem 33 and write a function to generate Farey Sequences and visualise them using Ford Circles. 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 Farey sequence of order n is the sequence of completely reduced fractions between 0 and 1. These fractions have denominators less than or equal to n, arranged in order of increasing size. For example, the Farey Sequence with order 3 is:
$$F_3 = \Big\{ \frac{0}{1},\frac{1}{3},\frac{1}{2},\frac{2}{3},\frac{1}{1}\Big\}$$
Ford Circles are a fractal-esque way to visualise Farey sequences, but before we get to this, first solve Euler problem 33.
The farey 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 Denominator, as defined by the gcd() function.
## Farey sequence function
farey <- function(n) {
fseq <- list()
fseq[[1]] <- c(0, 1)
i <- 2
gcd <- 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]] <- c(p, q)
i <- i + 1
}
}
}
fseq[[i]] <- c(1, 1)
fseq <- as.data.frame(do.call(rbind, fseq))
names(fseq) <- c("p", "q")
fseq <- fseq[order(fseq$p / fseq$q), ]
return(fseq)
}Standard ggplot2 cannot draw circles where the radius of the circles is related to the coordinate system. I used a circle function sourced from StackOverflow. This function is called in a for-loop to build the circles on top of the empty canvas.
library(ggplot2)
lm_palette <- c("#008da1", "#005395", "#262e43", "#3b2758", "#865596", "#f26230")
ford_circles <- farey(20) %>%
mutate(x = p / q,
y = 1 / (2* q^2),
r = y,
c = lm_palette[(q - 1)%%6 + 1])
g_circle <- function(r, x, y, color = NA, fill = "black", ...) {
x <- x + r * cos(seq(0, pi, length.out = 100))
ymax <- y + r * sin(seq(0, pi, length.out = 100))
ymin <- y + r * sin(seq(0, -pi, length.out = 100))
annotate("ribbon", x = x, ymin = ymin, ymax = ymax,
color = color, fill = fill, ...)
}
p <- ggplot(ford_circles, aes(x, y))
for (i in 1:nrow(ford_circles)) {
p <- 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()
ggsave("images/problem-033.png", width = 6, height = 4)Share this content
