In high school, we learn about cartesean and polar coordinates for describing points on the plane. The formulas we are asked to learn are:

$$ \begin{array}{rlcrl} r & = \sqrt{x^2 + y^2} & & x &= r \cos \theta \\ \theta & = \tan^{-1}\left(\frac{y}{x}\right) & & y &= r \sin \theta \end{array} $$

While these four formulas are enough to get you an "A" in the class, there's actually a lot packed into these lines which unfrotunately goes left unsaid, particularly in the two equations on the left. Let's pick up a loose string, pull at it, and see what happens. The place we're going to start is the most intense of the four equations: $\theta = \tan^{-1}\left(\frac{y}{x}\right)$.

As we talked about last time, for two consecutive numbers $n$ and $m$ (with $m$ the larger of the two), the difference of their squares is given by $m^2 - n^2 = 2n + 1$.

If you thought about this long enough, you might start to wonder, would this trick still work if we used a difference of consecutive cubes instead? It might look something like this:

$$ \require{cancel} \begin{array}{rrcrr} & 6^3 - \cancel{5^3} & & \\ + & \cancel{5^3} - \cancel{4^3} & & \\ + & \cancel{4^3} - \cancel{3^3} &=& ?\\ + & \cancel{3^3} - \cancel{2^3} & & \\ + & \cancel{2^3} - \cancel{1^3} & & \\ + & \cancel{1^3} - \cancel{0^3} & & \end{array} $$

We talked last time about the problem of summing the first $n$ consecutive integers. Here is another approach which demonstrates some different, but equally clever tricks. $\require{cancel}$

In high school, we learn that the difference of two squares can be computed by the formula $m^2 - n^2 = (m+n)(m-n)$. If this is unfamiliar, try expanding the right hand side and then simplifying.

Let's suppose for a moment that $m$ is the next number after $n$. We compute that:

$$ \begin{align} m^2 - n^2 &= (m+n)(m-n) \\ &= (2n + 1)(1) \\ &= 2n + 1 \end{align} $$

This formula holds for all $n$ whenever $m$ is the next number up. This means we can instantiate the formula with different values for $n$ like this:

$$ \begin{align} 6^2 - 5^2 = 2 \cdot 5 + 1 \\ 5^2 - 4^2 = 2 \cdot 4 + 1 \\ 4^2 - 3^2 = 2 \cdot 3 + 1 \\ 3^2 - 2^2 = 2 \cdot 2 + 1 \\ 2^2 - 1^2 = 2 \cdot 1 + 1 \\ 1^2 - 0^2 = 2 \cdot 0 + 1 \end{align} $$

This is where we get clever. We add vertically. Something interesting happens on either side of the equals sign.

There is a story that every math student should learn. It's about a mathematician named Gauss. One day, his school teacher wanted to keep the class busy for a long time so he could relax. So he gave the class an impossibly difficult task:

Add up all the numbers from 1 to 100.

The class got busy calculating. But not Gauss. After a few minutes, while most students were just beginning to struggle with the teens, Gauss was just finishing with writing down his final answer.

When he brought it to submit it, his teacher was furious with him for not taking the assignment seriously (and for interrupting his nap behind the desk).

We'll look to see how Gauss got his answer so quickly.

Everyone has, at some point during their childhood, found themselves in a contest to name the largest number. It starts off with perhaps a hundred, or a thousand, then a million, a billion, a trillion. Perhaps the savvy youngsters will know about quadrilions or quintillions.

But at some point, we run out of words for numbers. The argument continues with one-upsmanship. Your friend names a number. You tack "plus one" onto the end. They come back with "plus two". Maybe some multiplication gets thrown in there ("a trillion trillion!").

The game gets boring pretty quickly, though. You decide it's time to pull out your trump card: infinity!

Surely, you've won. No one can top infinity. It's bigger than the biggest number, after all. Your friend will have to forfeit.

Or so you think. But they come right back at you: "Infinity plus one!"

Infinite lists

OCaml and Haskell are both statically typed functional programming languages. Their type systems are very similar. They both have function types, algebraic data types, higher-order types (list of things, maybe/option types, tuple types). They both support type variants of the Hindley-Milner type inference algorithm.

But in Haskell, one often heralded featured is that data types can be "infinite". Haskellers love to showcase this clever one-linear which produces the fibonacci numbers:

fibs :: [Int]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

The Specs for Halt

We suppose the existence of a function called Halt. It takes one parameter: a function, we will call f, that takes 0 parameters. Then Halt(f) returns true if the call to f() ever returns a value, and Halt(f) returns false if f() loops infinitely.

An important part of this assumption is that Halt(f) must always return true or false regardless of your choice of f. It must not itself loop.