Euler Problem 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 way of generating quadratic primes (Euler Problem 27).

## Euler Problem 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 07 08 09 10

19 06 01 02 11

18 05 04 03 12

17 16 15 14 13

It 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 . The lowest number in the matrix with size is . The numbers increase by .

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.

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 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 code then identifies all primes using the *is.prime* function from Euler Problem 7. A heat map visualises the results.

# Ulam Spiral 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) # Visualise 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(panel.grid.major = element_blank(), panel.grid.minor = element_blank(), panel.background = element_blank()) + theme(axis.title.x=element_blank(), axis.text.x=element_blank(), axis.ticks.x=element_blank(), axis.title.y=element_blank(), axis.text.y=element_blank(), axis.ticks.y=element_blank() )

View the latest version of this code on GitHub.

Something wrong in the code – first you create a matrix:

ulam <- matrix(ncol = size, nrow = size)

next you correctly set the middle number:

ulam[mid, mid] <- 1

but later, you reference it as a variable:

ulam <- numbers[(l – n + 1):l]

It can't work this way!

Hi World Observer,

Thanks for pointing this out. The SyntaxHighlighter plugin removed some of the code because it was confused by “[c”. Now that I have changed the variable c to d, the code displays correctly.

I have updated the code in the post.

Peter

Actually, you should replace:

ulam <- numbers[(l – n + 1):l]

ulam <- numbers[(n – 1):(n – 2 + n)]

with:

ulam[c, c:(c + n -1)] <- numbers[(l – n + 1):l]

ulam[c + n -1, (c + n -1):c] <- numbers[(n – 1):(n – 2 + n)]

Indeed, see my response to your previous comment. Thanks again for helping out.

Great!

Thanks for interesting article.

Pingback: The Ulam Spiral (Euler Problem 28) – Mubashir Qasim

Pingback: The Ulam Spiral (Euler Problem 28) | A bunch of data

Pingback: Generating Quadratic Primes: Euler Problem 27 | The Devil is in the Data