It is estimated that in its existence the observable universe has performed no more than 10^120 operations on no more than 10^90 bits. Thus I believe the universe itself does not have the computational capacity to compute each one of the partitions of 10^5. As we are part of the universe, neither do we.

Edit: just to be clear, I'm referring to the obviously comedic comments about the Hungarian Pengo, not the computation that Fredrik reports having completed. Apparently the Pengo project is not only ill-advised, but actually impossible.

You seem to be assuming that, to calculate the partitions of a number, it is necessary to actually enumerate every one of those partitions. This is not true.

I'm assuming nothing of the sort. I said to compute "each one of" the partitions, which is a totally different problem to counting them.

Then we definitely need a bigger universe. ^^

or a faster one

The universe is expanding and therefore becoming colder and colder - it should be safe to slowly increase the clock frequency over time.

That's so 2004. Nowadays we just increase the number of cores. Unfortunately the string theory landscape only has about 10^500 possible settings, and they are still unable to figure out how to have the cores use a shared state (so that each universe can know which partitions it should be computing in the enumeration).

This is computing the cardinality (size) of the set of partitions, not enumerating all of its members.

Obviously. However, the article talks not only about the cardinality of the set (which has been computed) but about enumerating the set using Hungarian Pengo. As the article already points out artfully that the attempting the latter may be bad for one's health, I decided to point out that it is actually impossible.

Numberwang, classy.

Reference: http://www.youtube.com/watch?v=qjOZtWZ56lc

Is there a simple/intuitive explanation why there is no simple closed form for p(n)?

In general, it is only by coincidence when something does have a nice closed form.

But finding all partitions seems like a simple combinatorial problem at first sight.

Firstly, "closed form" is not objectively defined. Do you include infinite sums? Bernoulli numbers? Euler's constant? etc (http://www.ams.org/notices/201301/rnoti-p50.pdf). If you wanted to, you could call p(n) a closed form for p(n).

You cannot call that cheating. In the past, we similarly introduced n!, n^n, and n!!!!!!!!!n and, going further back, even n*n and n+n as shorthands for more cumbersome expressions (n^2 is sum(1,n;n))

So, I think you aren't asking for a closed form, but for an easy way to compute p(n). p(n) is trivially defined recursively (a way is with a helper function p(n,m) for the number of partitions of n where each number in the partition is at least equal to m). The only difference is that that trivial definition has an enormous branching factor.

That's where number theorists come in. They manage to replace that rapidly branching method with easier ones, where it often isn't clear that

For example, see https://oeis.org/wiki/Partition_function#Partition_function_.... It states p(n) equals an infinite sum of some seemingly hideous function containing derivatives, sinh, square roots, etc. Evaluating that does not involve branching, though. That can make it much faster to approximate such a function by 'only' iterating until you know you are within 0.5 of the real answer. That must be an integer, so if you are within 0.5, rounding gives you the correct answer. That's what this computation did, too, for a different formula.

Generally, there are infinitely more things that don't have a closed form at all than things that do.

This was considered a big breakthrough: http://www.aimath.org/news/partition/brunier-ono.pdf

Notice Theorem 1.1 gives a nice formulation, but unfortunately Tr(n) is really difficult to describe.

Does anyone know what he used to generate the equations in HTML? Most of the tools I've used simply convert LaTeX equations to an image.

MathJax:

http://www.mathjax.org/

This is also what the math-related Stack Exchange sites use. (Ex: Math SE, Crypto SE, Physics SE, ...). For example, see the home page of the Math SE: http://math.stackexchange.com/

Tip: Wikipedia has experimental support for MathJax, making most equations look way better. (it's in user preferences)

The real story here is the Arb software the creator's developed for arbitrary-precision computations with rigorous error bounds.

Anything limited by a data type requiring billions of digits is indistinguishable from magic.