Prime numbers are the engine of the Internet economy. One of the reasons prime numbers are so useful is that they cannot be generated through an algorithm. This impossibility has not stopped mathematicians from trying to find formulas to generate prime numbers.

Euler problem 27 deals with quadratic formulas that can be used to generate sets of prime numbers. We have already discussed this in the post about the Ulam Spiral. This Numerphile video discusses quadratic primes.

## Euler Problem 27 Definition

Euler discovered the remarkable quadratic formula:

It turns out that the formula will produce primes for the consecutive integer values . However, when , is divisible by , and certainly when , is clearly divisible by .

The incredible formula was discovered, which produces 80 primes for the consecutive values . The product of the coefficients, and , is .

Considering quadratics of the form: ,

where and , where is the modulus/absolute value of , e.g. and .

Find the product of the coefficients, and , for the quadratic expression that produces the maximum number of primes for consecutive values of , starting with .

## Proposed Solution

The only way to solve this problem is through brute force and reduce the solution space to optimise it for speed (source: mathblog.dk). Because the outcome of the equation must be prime for , also has to be prime. We can use the prime sieve from Euler Problem 3, which reduces it from 2000 to 168 options. When we insert it follows that a has to be an even number. If has to be prime and has to be a prime number, then a can only be an odd number. However, when , a has to be even.

## Euler Problem 27 code

seq.a <- seq(-999, 1001, 2) # a has to be odd seq.b <- (esieve(1000)) # b has to be prime max.count <- 0 for (a in seq.a) { if (a == 2) seq.a <- seq(-1000, 1000, 2) # a has to be even for (b in seq.b) { n <- 0 # Find sequence of primes for a and b while (is.prime(n^2 + a * n + b)) { n <- n + 1 } # Store maximum values if (n > max.count) { max.count <- n max.a <- a max.b <- b } } } answer <- max.a * max.b print(answer)

View the latest version of this code on GitHub.

Pingback: Generating Quadratic Primes: Euler Problem 27 – Mubashir Qasim

Pingback: Generating Quadratic Primes: Euler Problem 27 – Cloud Data Architect