Project Euler 28: Number Spiral Diagonals
Peter Prevos |
577 words | 3 minutes
Share this content
Project Euler 28 takes us to the world of the Ulam Spiral. This is a spiral that contains sequential positive integers in a square spiral, marking the prime numbers. Stanislaw Ulam discovered that a lot of primes are located along the diagonals. These diagonals can be described as polynomials. The Ulam Spiral is thus a method to generate quadratic primes (Euler Problem 27).
Project Euler 28 Definition
Starting with the number 1 and moving to the right in a clockwise direction, a 5 by 5 spiral is formed as follows:
21 22 23 24 25
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13It can be verified that the sum of the numbers on the diagonals is 101.
What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?
Proposed Solution
To solve this problem, we do not need to create a matrix. This code calculates the values of the corners of a matrix with size \(n\). The lowest number in the matrix with size \(n\) is \(n(n-3)+4\). The numbers increase by \(n-1\) . The code steps through all matrices from size 3 to 1001. The solution uses only the uneven sized matrices because these have a centre. The answer to the problem is the sum of all numbers.
## Project Euler 28: Number Spiral Diagonals
size <- 1001 # Size of matrix
answer <- 1 # Starting number
## Define corners of subsequent matrices
for (n in seq(from = 3, to = size, by = 2)) {
corners <- seq(from = n * (n - 3) + 3, by = n - 1, length.out = 4)
answer <- answer + sum(corners)
}
print(answer)Plotting the Ulam Spiral
We can go beyond Euler Problem 28 and play with the mathematics. This code snippet plots all the prime numbers in the Ulam Spiral. Watch the Numberphile video for an explanation of the patterns that appear along the diagonals.
The code creates a matrix of the required size and fills it with the Ulam Spiral. The system then identifies all primes using the is.prime() function from Euler Problem 7, as visualised on the top of this article.
## Prime Spirals
source("problem007.R", verbose = FALSE)
size <- 201 # Size of matrix
ulam <- matrix(ncol = size, nrow = size)
mid <- floor(size / 2 + 1)
ulam[mid, mid] <- 1
for (n in seq(from = 3, to = size, by = 2)) {
numbers <- (n * (n - 4) + 5) : ((n + 2) * ((n + 2) - 4) + 4)
d <- mid - floor(n / 2)
l <- length(numbers)
ulam[d, d:(d + n - 1)] <- numbers[(l - n + 1):l]
ulam[d + n - 1, (d + n - 1):d] <- numbers[(n - 1):(n - 2 + n)]
ulam[(d + 1):(d + n - 2), d] <- numbers[(l - n):(l - 2 * n + 3)]
ulam[(d + 1):(d + n - 2), d + n - 1] <- numbers[1:(n - 2)]
}
ulam.primes <- apply(ulam, c(1, 2), is.prime)
library(ggplot2)
library(reshape2)
ulam.primes <- melt(ulam.primes)
ggplot(ulam.primes, aes(x = Var1, y = Var2, fill = value)) +
geom_tile() +
scale_fill_manual(values = c("white", "black")) +
guides(fill = FALSE) +
theme_void()
ggsave("images/problem-028.png", widt = 6, height = 4)Share this content
