Additive Number Theory is Hard

.. for example nobody has published a (correct) proof of the Goldbach conjecture that claims every even number is the sum of two primes. Maybe this isn't actually additive number theory as it concerns the addition of prime numbers, and prime numbers are the building blocks of multiplicative number theory.

But let me tell you a couple of interesting results I found recently on the internet.

Question:
Suppose I want to add some numbers and get a specified total. How many ways are there to do this?

Let's see how many ways there are to add up to 4. You have 1+1+1+1, 1+1+2, 1+3, 2+2 and 4. That makes five ways to add up to 4. Amazing. It makes sense to restrict ourselves to using positive integers, and to ignore the order of the summands. Adding up numbers like this to get a total of n is called a partition of n. So we get to say there are 5 partitions of 4.

Let's define a function!

p(n) = The number of partitions of n.

Simple aye? Here are the first few values. Notice how it grows rather quickly.

n	p(n)
1	1
2	2
3	3
4	5
5	7
6	11
7	15
8	22
9	30
10	42
11	56
12	77
13	101
14	135
15	176
16	231
17	297
17	297
18	385
19	490
20	627

This is the partition function and encodes the answer to the above question. Of course it is still hard to evaluate p(n) for a given n, so we are no closer to answering the above question. But you have to feel that by learning about this function, we are making progress.

If you restrict in some way the numbers you can use to get to your specified total, (e.g. primes or squares) then you can do some interesting maths...

Every positive whole number can be written as the sum of four squares. (The four squares theorem)

Now we know a few technical words I can share the interesting result I found.

If n = 5k+4 then p(n) is divisible by 5.
If n = 7k+5 then p(n) is divisible by 7.
If n = 11k+6 then p(n) is divisible by 11.

It seems crazy to me that the divisibility of the number of partitions of n should be related to n like this. Check them for yourself using the table I helpfully provided. The sequence of numbers in the right hand column is one that naturally turns up all over the place and people love to spot patterns in apparent randomness. I strongly suspect that the ancient Greeks or whoever had seen that these results hold for all the values they could check, but were unable to prove them in general.

These results are attributed to Ramanujan, an Indian mathematician whose genius was so unlike anything before or since that you can't help but regard him as a bit mad. His works are dense with the most complicated formulas and I am always bewildered at how he discovered them.