nerd.tex

\documentclass{article}
\usepackage{geometry}
\usepackage{fancyhdr}
\usepackage{amsmath ,amsthm ,amssymb}
\usepackage{graphicx}
\usepackage{hyperref}

\begin{document}

Problem 28 can be solved analytically. It's certainly not the most efficient route,
unless we're dealing with enormous number spirals.

Consider the lower right diagonal of the spiral, \((3, 13, 31, \ldots)\).


\begin{align}
\nonumber
f(0)& =3\\
\nonumber
f(1)& =f(0) + 1 + 3\cdot3\\
\nonumber
f(2)& =f(1) + 3 + 3\cdot5
\end{align}

More generally:

\begin{align}
\nonumber
f(x)& =f(x-1) + (2x - 1) + 3(2x + 1)
\end{align}

We can attempt to find a closed-form solution by repeatedly substituting until a
pattern emerges

\begin{align}
\nonumber
f(x)& =f(x-1) + (2x - 1) + 3(2x + 1)\\
\nonumber
	& =f(x-2) + (2x - 3) + 4(2x - 1) + 3(2x + 1)
\end{align}

Redefining $f(x)$ in terms of $f(x-i)$:

\begin{align}
\nonumber
f(x)& =f(x-i) + 3(2x + 1) + \sum_{l=1}^{i} 4(2x - 2l + 1) - 3(2x - 2i + 1)
\end{align}

The closed form solution can be found by choosing $x = i$

\begin{align}
\nonumber
f(x)& =f(0) + 3(2x + 1) + \sum_{l=1}^{x} 4(2x - 2l + 1) - 3\\
\nonumber
	& =f(0) + 6x + \sum_{l=1}^{x} 4(2x - 2l + 1)\\
\nonumber
	& =f(0) + 6x + 8\sum_{l=1}^{x} x - 8\sum_{l=1}^{x} l + 4\sum_{l=1}^{x} 1\\
\nonumber
	& =f(0) + 6x + 8x^2 - 4(x^2 + x) + 4x\\
\nonumber
	& =f(0) + 6x + 4x^2\\
	& =3 + 6x + 4x^2
\end{align}

This function gives us the numeric value of a corner along the lower right
diagonal. Interestingly, it works for $x = -1$, yielding $1$. The sum of the
diagonal (excluding 1) can be found.

\begin{align}
\nonumber
F(n)& =\sum_{x=0}^{n} f(x)\\
\nonumber
	& =\sum_{x=0}^{n} (3 + 6x + 4x^2)\\
\nonumber
	& =\sum_{x=0}^{n} 3 + 6\sum_{x=0}^{n} x + 4\sum_{x=0}^{n} x^2\\
\nonumber
	& =3(n + 1) + 3(n^2 + n) + 4\left(\frac{n^3}{3} + \frac{n^2}{2} + \frac{n}{6}\right)\\
	& =3 + 6n + 5n^2 + 4\left(\frac{n^3}{3} + \frac{n}{6}\right)
\end{align}

A similar process can be followed for the other diagonals:

\begin{align}
\nonumber
f(x)& =3 + 6x + 4x^2\\
\nonumber
g(x)& =5 + 8x + 4x^2\\
\nonumber
h(x)& =7 + 10x + 4x^2\\
\nonumber
i(x)& =9 + 12x + 4x^2
\end{align}

\begin{align}
\nonumber
p(x)& =f(x) + g(x) + h(x) + i(x)\\
\nonumber
	& =24 + 36x + 16x^2\\
\nonumber
P(n)& =\sum_{x=0}^{n} p(x)\\
\nonumber
	& =\sum_{x=0}^{n} 24 + 36\sum_{x=0}^{n} x + 16\sum_{x=0}^{n} x^2\\
\nonumber
	& =24(n + 1) + 18(n^2 + n) + 16\left(\frac{n^3}{3} + \frac{n^2}{2} + \frac{n}{6}\right)\\
	& =24 + 42n + 26n^2 + 16\left(\frac{n^3}{3} + \frac{n}{6}\right)
\end{align}

where $n = \frac{L - 3}{2}$. Therefore, for a spiral of length $1001$

\begin{align}
\nonumber
n& =499\\
P(499)& =669171000
\end{align}

Since 1 is not included in this formula, it must be added to find the true sum
of the diagonals.

\end{document}

p027.hs

-- cheating because I don't want to build a sieve
import Data.Numbers.Primes

($>) = flip ($)

-- find longest sequence of primes for formula of form
-- n^2 + an + b
-- where |a| < 1000, |b| < 1000

-- search space is 3996001 pairs (1999^2)

-- simplifications:

-- b must be prime < 1000, to satisfy equation at n = 0
-- search space now 335832 pairs

-- a >= -b, to satisfy equation at n=1
-- search space now 244127 pairs

-- a > 0 or a^2 > 2b, to ensure formula never returns number <= 0
-- search space now 239368 pairs
-- probably not worth it

-- these two additions make the search space linear in limit
-- where a brute force approach is quadritic in limit

primePotential a b n = n*n + a*n + b

pickGreaterWith f a b = if f a > f b then a else b

fst3 (a,_,_) = a

maxWith f = foldl (pickGreaterWith f) (0, 0, 0)

res limit = [
    map (primePotential a b) [0..]
        $> takeWhile isPrime
        $> (\v -> (length v, a, b)) |
    -- b must be a prime, to satisfy condition for n = 0
    b <- takeWhile (< limit) primes,
    -- a must be >= -b, to satisfy condition for n = 1
    a <- [-b..limit - 1]
    ]
    $> maxWith fst3
    $> (\(_,a,b) -> a*b)

main = do
    putStrLn $ show $ res 1000

-- cheating because I don't want to build a sieve
import Data.Numbers.Primes

($>) = flip ($)

-- find longest sequence of primes for formula of form
-- n^2 + an + b
-- where |a| < 1000, |b| < 1000

-- search space is 3996001 pairs (1999^2)

-- simplifications:

-- b must be prime < 1000, to satisfy equation at n = 0
-- search space now 335832 pairs

-- a >= -b, to satisfy equation at n=1
-- search space now 244127 pairs

-- a > 0 or a^2 > 2b, to ensure formula never returns number <= 0
-- search space now 239368 pairs
-- probably not worth it

-- these two additions make the search space linear in limit
-- where a brute force approach is quadritic in limit

primePotential a b n = n*n + a*n + b

pickGreaterWith f a b = if f a > f b then a else b

fst3 (a,_,_) = a

maxWith f = foldl (pickGreaterWith f) (0, 0, 0)

res limit = [
    map (primePotential a b) [0..]
        $> takeWhile isPrime
        $> (\v -> (length v, a, b)) |
    -- b must be a prime, to satisfy condition for n = 0
    b <- takeWhile (< limit) primes,
    -- a must be >= -b, to satisfy condition for n = 1
    a <- [-b..limit - 1]
    ]
    $> maxWith fst3
    $> (\(_,a,b) -> a*b)

main = do
    putStrLn $ show $ res 1000

-- real 0m0.237s
-- user 0m0.231s
-- sys  0m0.004s

p029.hs

import qualified Data.Set

($>) = flip ($)

-- v^0, v^1, v^2, .., v^100
powersOf v = iterate (*v) 1

main = do [2..100]
    $> map (take 99 . drop 2 . powersOf)
    $> concat
    $> Data.Set.fromList
    $> Data.Set.size
    $> show
    $> putStrLn

-- real 0m0.020s
-- user 0m0.015s
-- sys  0m0.004s