7 ms·
New partition function record: p(10^20) computed
- wbhart 13y agoIt 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.
- danbruc 13y agoThen we definitely need a bigger universe. ^^
- gosub 13y agoor a faster one
- danbruc 13y agoThe universe is expanding and therefore becoming colder and colder - it should be safe to slowly increase the clock frequency over time.
- wbhart 13y agoThat'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).
- duskwuff 13y agoYou 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.
- deleted 13y ago[deleted]
- wbhart 13y agoI'm assuming nothing of the sort. I said to compute "each one of" the partitions, which is a totally different problem to counting them.
- jey 13y agoThis is computing the cardinality (size) of the set of partitions, not enumerating all of its members.
- deleted 13y ago[deleted]
- wbhart 13y agoObviously. 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.
- jjgreen 13y agoNumberwang, classy.
- sp332 13y agoReference: http://www.youtube.com/watch?v=qjOZtWZ56lc http://www.youtube.com/watch?v=qjOZtWZ56lc
- ahassan 13y agoDoes 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.
- bbatsell 13y agoMathJax: http://www.mathjax.org/ http://www.mathjax.org/
- ReidZB 13y agoThis 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/ http://math.stackexchange.com/
- bajsejohannes 13y agoTip: Wikipedia has experimental support for MathJax, making most equations look way better. (it's in user preferences)
- 3rd3 13y agoIs there a simple/intuitive explanation why there is no simple closed form for p(n)?
- j2kun 13y agoThis was considered a big breakthrough: http://www.aimath.org/news/partition/brunier-ono.pdf 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.
- monochromatic 13y agoIn general, it is only by coincidence when something does have a nice closed form.
- 3rd3 13y agoBut finding all partitions seems like a simple combinatorial problem at first sight.
- Someone 13y agoFirstly, "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.
- coldcode 13y agoAnything limited by a data type requiring billions of digits is indistinguishable from magic.
- csense 13y agoThe real story here is the Arb software the creator's developed for arbitrary-precision computations with rigorous error bounds.