Gabeland

First, some background.
The number of natural numbers (1, 2, 3, 4, …) and the number of integers (…, -2, -1, 0, 1, 2, …) are both infinite. But are they the same kind of infinite?
The answer is yes, because you can match each integer to a natural number.
Order the integers like this:
0, 1, -1, 2, -2, 3, -3, 4, -4, …
and then match each integer to its position.

But what about rational numbers? You can’t order them that easily. Or can you?
Well, you can. Let’s look at only the positive ones for the moment; making it both is relatively easy.
Take a grid of fractions like this:
1/1 1/2 1/3 1/4 1/5 1/6
2/1 2/2 2/3 2/4 2/5 2/6
3/1 3/2 3/3 3/4 3/5 3/6
etc.
and take each successive diagonal, so you get the ones where the numerator and denominator add up to 1, then 2, then 3, then 4, etc.
The order would be 1/1, 1/2, 2/1, 1/3, 2/2, 3/1, 1/4, 2/3, 3/2, 4/1, …
However, you would get things like 2/2 or 6/3 or 7/14. And the way I’ve always seen that resolved is to just skip over them. If a fraction is the same as one before it, ignore it and move on.

But that’s unsatisfying.
Is there a way to order the rational numbers without having to arbitrarily skip things?
Let’s find out!

The problem with the previous ordering is that you can have fractions which have a shared factor in the numerator and the denominator. So we need some way to make it so that each factor can only be in the numerator or the denominator, not both.

Enter the rational prime factorization:
12/7 = 2² × 3¹ × 7^-1
This effectively turns every rational number into a finite sequence of integers.
2² × 3¹ × 7^-1 -> (2, 1, 0, -1)
It has to be finite, because each positive integer has a greatest prime factor. So after the greatest prime factor of both the numerator and the denominator have passed, there’s no more.

For the next step, we’re going to want the integers to be converted to positive integers via the ordering at the top. So (2, 1, 0, -1) becomes (4, 2, 1, 3). Keep in mind that adding 1s to the end would make it the same fraction, namely 12/7.
Now, convert each number to binary. 4 becomes 100, 2 becomes 10, 1 stays 1, and 3 becomes 11.
Take off the initial 1 (every positive integer has one), and then make all the 0s into 1s and the 1s into 2s.
Our sequence after that is (11, 1, , 2). The 3rd term is… well, these aren’t exactly numbers. But if you want, you can think of it as 0.

Lastly, put them together into a ternary number, backwards, separated by 0s.
12/7 would be 2001011, and converting back into decimal gives us 1489. There we go! We did it!

…but how do I know we don’t need to skip things? Well, the only opportunity for two of the previous sequences to be the same rational number is if you put 1s on the end of the sequence. But if you put an extra 1 at the end of the sequence, it would put a 0 on the start of the ternary number. And putting a 0 at the start of a number does nothing. In fact, it might as well already be there.

Here’s part of the list of rational numbers gotten this way:
1, 2, 1/2, 3, 4, 1/4, 1/3, 8, 1/8, 5, 6, 3/2, 9, 16, 1/16, 1/9, 32, 1/32, 1/5, …
So, to tie it all together, this shows that the rational numbers and the natural numbers are the same size, because you can pair them and have none left over.

Let’s say we have a sequence, and we want to guess what polynomial generated it.
For example:
3, 10, 19, 30, 43, 58, 75, …
Finite differences helps with determining that.

How it works is, take the difference between each pair of terms.
10 – 3 = 7, then 19 – 10 = 9, then 30 – 19 = 11, etc.
The new sequence is 7, 9, 11, 13, 15, 17, …
That’s the odd numbers! Now, which sequence has consecutive pairs of terms differing by odd numbers? The squares. Except this clearly isn’t the squares. So let’s subtract it off:
3 – 1 = 2
10 – 4 = 6
19 – 9 = 10
etc.
2, 6, 10, 14, 18, 22, 26, … is the result.
That’s 4n – 2. So, the function of the original sequence is n² + 4n – 2.

You can use it for more general cases too.
Let’s try 8, 33, 88, 185, 336, 553, 848.

I’m not showing each individual subtraction this time, but here’s the result:
Step 1: 25, 55, 97, 151, 217, 295
Step 2: 30, 42, 54, 66, 78
Step 3: 12, 12, 12, 12

At step 3, every term is the same. That means that there has to be a cube term, and to find the coefficient, divide the constant term by 3!, or 6. That means there’s a 2n³ term. Let’s subtract that off.
6, 17, 34, 57, 86, 121, 162

It still isn’t clear what polynomial this is. But now we can repeat the process with this new sequence.
Step 1: 11, 17, 23, 29, 35, 41
Step 2: 6, 6, 6, 6, 6

Now, every term is the same by step 2. That means there’s a square term, and we can divide the constant term by 2!, which is 2, giving us 3n². Subtract that off again.
3, 5, 7, 9, 11, 13, 15
You could do it again, and get a constant term by step 1, but I’m sure you recognize this as 2n + 1.
So, the full function is 2n³ + 3n² + 2n + 1.

Finite differences also works for some other functions.
Take this sequence: 3, 8, 17, 32, 57, 100, 177, …
Step 1: 5, 9, 15, 25, 43, 77
Step 2: 4, 6, 10, 18, 34
Step 3: 2, 4, 8, 16
That’s the powers of 2. That means that 2ⁿ must be a term in the original function. In fact, the original function was 2ⁿ + n².