3 ms·

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

• Someone 13y ago
  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 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_formula 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.