Euler problem 27.2.2

p_27 = -(2 * a - 1) * (a ^ 2 - a + 41)
  where
    n = 1000
    m = head $ filter (\x -> x ^ 2 - x + 41 > n) [1 ..]
    a = m - 1

Euler Problem 27 asks us to find a quadratic equation of the form $(n^2 + a \cdot n + b)$ that generates the most consecutive prime numbers starting from $n = 0$ , with the constraints $|a| < 1000$ and $|b| \leq 1000$ . The final answer is the product $a \cdot b$ for the winning pair. The “official” Haskell solution looks cryptic, but there’s a clever trick behind it. Let’s break it down step-by-step in a way that’s easier to follow.

A Handy Math Trick: Shifting the Quadratic

Imagine we tweak our quadratic $(n^2 + a \cdot n + b)$ by replacing $n$ with $n - x$ . When we expand it out, we get:

$(n - x)^2 + a(n - x) + b = n^2 + (a - 2x)n + (x^2 - ax + b)$

This is still a quadratic in $n$ , but now the coefficients are:

$a_{\text{new}} = a - 2x$
$b_{\text{new}} = x^2 - ax + b$

By choosing the right $x$ , we can transform any quadratic into a simpler form, like $n^2 + d$ or $n^2 + n + d$ . This is our starting point.

Which Form Works Best?

Form 1: $n^2 + d$
This one’s a dud. Plug in $n = 0, 1, 2, 3$ , and you’ll see every other number is even (e.g., $d, d+1, d+4, d+9$ ). With so many evens, it can’t produce a long run of primes—primes are mostly odd (except 2).
Form 2: $n^2 + n + d$
This is more promising. A mathematician named Rabinowitz proved that for this form to generate the longest sequence of primes, $4d - 1$ must be a special number called a Heegner number. There are only six possibilities, and after testing, $n^2 + n + 41$ comes out on top. It spits out 40 primes from $n = 0$ to $n = 39$ . The runner-up, $n^2 + n + 17$ , doesn’t do as well.

So, $n^2 + n + 41$ is our golden ticket. But there’s more to it.

The Symmetry Bonus

Here’s a cool trick with $n^2 + n + 41$ :

$(-1 - n)^2 + (-1 - n) + 41 = n^2 + n + 41$

This means if $n = 2$ gives a prime (like 47), then $n = -3$ (i.e., $-1 - 2$ ) does too (also 47). The sequence works both ways—positive and negative $n$ . Starting at $n = 0$ , we get 40 primes up to $n = 39$ , but we can also count backward with negative $n$ . Our goal is to shift this quadratic so we capture more of these primes from $n = 0$ onward, while keeping $a$ and $b$ within the problem’s limits.

Fitting It Into the Rules

Let’s start with $n^2 + n + 41$ (where $a = 1, b = 41$ ) and shift it using our trick:

New quadratic: $n^2 + (1 - 2x)n + (x^2 - x + 41)$
New $a = 1 - 2x$
New $b = x^2 - x + 41$

The problem says $|a| < 1000$ and $|b| \leq 1000$ , so:

$|1 - 2x| < 1000$
$|x^2 - x + 41| \leq 1000$

The second condition is trickier because $x^2$ grows fast. We need the biggest $x$ where $x^2 - x + 41 \leq 1000$ .

Crunching the Numbers

Let’s test some $x$ values:

$x = 31$ : $31^2 - 31 + 41 = 961 - 31 + 41 = 971$ (under 1000)
$x = 32$ : $32^2 - 32 + 41 = 1024 - 32 + 41 = 1033$ (over 1000)

So, $x = 31$ is the largest value that works. Now calculate:

$a = 1 - 2 \cdot 31 = 1 - 62 = -61$
$b = 971$ (from above)

Check the constraints:

$|a| = |-61| = 61 < 1000$ ✓
$|b| = 971 \leq 1000$ ✓

The Haskell Code Explained

That’s where this funky code comes in:

n = 1000
m = head $ filter (\x -> x ^ 2 - x + 41 > n) [1 ..]
a = m - 1

It finds $m = 32$ (first $x$ where $x^2 - x + 41 > 1000$ ). Then $x = m - 1 = 31$ .

The final line:

p_27 = -(2 * a - 1) * (a ^ 2 - a + 41)

This is a bit off. It uses $a = 31$ , but we need $a = 1 - 2x = -61$ . The correct product should be:

$a = -61$
$b = 971$
$a \cdot b = -61 \cdot 971 = -59231$

The code’s formula seems to be a typo or a leftover from a different derivation. It should just compute $(1 - 2x) \cdot (x^2 - x + 41)$ .

Why It Works

With $a = -61, b = 971$ , the quadratic $n^2 - 61n + 971$ generates 71 primes from $n = 0$ to $n = 70$ . This shift captures more of the $n^2 + n + 41$ sequence’s primes in the positive direction, thanks to the negative $a$ . The product -59231 is the answer.

Wrapping Up

This solution is sneaky—it starts with a prime-generating champ, shifts it just right, and fits the problem’s rules. It’s not the brute-force way (testing every $a$ and $b$ ), but a math shortcut that lands on the perfect answer. Pretty cool, right?

— Me@2025-03-24 12:25:20 PM

Physics Town

continues

Euler problem 27.2.2

A Handy Math Trick: Shifting the Quadratic

Which Form Works Best?

The Symmetry Bonus

Fitting It Into the Rules

Crunching the Numbers

The Haskell Code Explained

Why It Works

Wrapping Up

A Handy Math Trick: Shifting the Quadratic

Which Form Works Best?

The Symmetry Bonus

Fitting It Into the Rules

Crunching the Numbers

The Haskell Code Explained

Why It Works

Wrapping Up

Related