# Partition and composition calculator

## work in progress by Henry Bottomley 2002/2003

This is the original version of my partitions page, but the Eolas/Microsoft dispute puts the Java applets at risk, so there is also a what I hope is a more automatic page available though missing the three later applets (although written earlier).

Lots of choices: choose constraints if any, put non-negative integer(s) into box(es) and click the button.

Java Code

Some of these calculations may be slow. Others may produce very large results. If the result in the final box fills the box then it is likely that the number is even bigger. (At least in Windows) double clicking on this number will allow it to be copied (Ctrl-C) and then pasted into another application.

The seven partitions of 5 are: 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, and 1+1+1+1+1. So the three partitions of 5 into distinct terms are: 5, 4+1, and 3+2.

Similarly, the sixteen compositions of 5 are: 5, 4+1, 3+2, 3+1+1, 2+3, 2+2+1, 2+1+2, 2+1+1+1, 1+4, 1+3+1, 1+2+2, 1+2+1+1, 1+1+3, 1+1+2+1, 1+1+1+2, and 1+1+1+1+1. So the five compositions of 5 into distinct terms are: 5, 4+1, 3+2, 2+3, and 1+4.

The rest of this page was written earlier (starting with the applet at the bottom) and provides some discussion.

The next applet works out the number of partitions on n. For example, 8 can be written 22 different ways:
8, 7+1, 6+2, 6+1+1, 5+3, 5+2+1, 5+1+1+1, 4+4, 4+3+1, 4+2+2, 4+2+1+1, 4+1+1+1+1, 3+3+2, 3+3+1+1, 3+2+2+1, 3+2+1+1+1, 3+1+1+1+1+1, 2+2+2+2, 2+2+2+1+1, 2+2+1+1+1+1, 2+1+1+1+1+1+1, 1+1+1+1+1+1+1+1.

Just put a positive integer into the left hand box and click the button.

Here is an indication of how large the numbers of partitions can become (partitioning powers of 2) - you may need to scroll right to see the end of some of the bigger results below, in the same way as the result above may stretch beyond the box it is in:
1 1
2 2
4 5
8 22
16 231
32 8349
64 1741630
128 4351078600
256 365749566870782
512 4453575699570940947378
1024 61847822068260244309086870983975
2048 18116048323611252751541173214616030020513022685
4096 6927233917602120527467409170319882882996950147283323368445315320451
8192 1181439874128599109971249397860343958559859263335823651875555915473905892636341722762111648746675
16384 344000337355815290368737859724271378055780665044280608303640703019052218992626803411292513134005029559536822813269418600987644288209503225
32768 19951134337408105736642454272091952569829539699845648716451663760974203400085273251115951972201415740430051470634296617335652416695640010012442146056932684309619132097804261003216042433712827589561
65536 3375638811922922155622997677970676411503193024179029675479255490872598542700001280937511869723154909719539821359520748618125254310314222068304969117505347994307169958539732863947210860791478913713614853329658306996159866453282108698155550982208953567868886634273542018540012370232
131072 22674714460321944267524151730340791834729708422428170799101316045907635882570958938366535712917682396170864129968099484282216456453966228466334673226786159672330595238163084594770994361550682172092540733107028631792345492795065286011303073360230304520477515679799196316861705347838431285467041063583015436006311566210026935177564255144029672140021602245194110911727330063730634331395081202107451005
262144 1296823682580806678252620436987760039669460982399363423263654269209880975956182298718024754405652747850840853021300920551605413807482101776464677070970730988737526404073002579531904220008513319080191002087301493686453673808601037215166546326372477459550445386626789436787147147116184409680707357220078941964199255353373827070986816002335909711317541128178955655143001683564019919739712996651809956723558239355326324947027002219786611433561212587991812697089165150066432298578166004340423391764987709447953257360223253746318480526350212192359783057131753951529623345

If it seems that a surprising number of these end in 5 or 0, that is because it is true. Indeed, a disproportionate number of partitions are congruent to 0 modulo 5, 7 or 11, as the following table of partitions of numbers from 1 to 100000 modulo 1 to 20 shows:

 mod/value 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 1 100000 2 49800 50200 3 33344 33193 33463 4 24796 25026 25004 25174 5 36256 15758 16133 16028 15825 6 16699 16713 16621 16645 16480 16842 7 27193 12078 12203 12260 12231 12003 12032 8 12452 12636 12525 12758 12344 12390 12479 12416 9 11243 10940 11196 11077 11078 11115 11024 11175 11152 10 17994 7897 8117 7973 7773 18262 7861 8016 8055 8052 11 17444 8315 8306 8187 8430 8307 8283 8145 8249 8159 8175 12 8360 8199 8366 8314 8181 8496 8339 8514 8255 8331 8299 8346 13 8031 7802 7584 7701 7702 7636 7504 7681 7650 7835 7513 7654 7707 14 13441 6043 6126 6186 6126 6073 6068 13752 6035 6077 6074 6105 5930 5964 15 12135 5130 5415 5285 5227 12056 5341 5335 5307 5200 12065 5287 5383 5436 5398 16 6197 6398 6216 6306 6105 6264 6280 6183 6255 6238 6309 6452 6239 6126 6199 6233 17 5855 5880 5845 5864 5945 5864 5939 5949 5832 5796 5898 6032 5856 5696 5977 5867 5905 18 5644 5461 5529 5506 5513 5545 5484 5687 5522 5599 5479 5667 5571 5565 5570 5540 5488 5630 19 5120 5402 5352 5340 5350 5187 5334 5132 5206 5329 5185 5312 5156 5283 5192 5354 5277 5314 5175 20 8953 3918 4071 3974 3887 9150 3936 4059 3985 4002 9041 3979 4046 3999 3886 9112 3925 3957 4070 4050

The next applet also calculates partitions, but much more slowly than the one above. It offers a variety of options, though some are in fact identical. If you choose a restricted one with "..." then you need to put the ... integer value in the second small box as well as the number being partitioned in the first box, before clicking on the calculate button.

The partitions into distinct terms (or equivalently into odd terms) is not surprisingly smaller than the total number of partitions - the ratio of their numbers of digits (i.e. of their logarithms) approachs the square root of 2. Here are the numbers of partitions into distinct terms for various powers of 2:
1 1
2 1
4 2
8 6
16 32
32 390
64 16444
128 4013544
256 11784471548
512 1168225267521350
1024 16816734263788624008200
2048 276565526698898057002583240473088
4096 96052644365764024805972019009272150642974291708
8192 43586702014259316987395017345466711329303914541873541942193666197800
16384 8827143488223486762466819968698422632152886338011679785283252783955091881854704616260162240597984
32768 3053304330024838448180845274595214664326737562363336996610979021919615792015959034318568940246229815022583171851479621858752844823592006022
65536 210433388508833775468028401870151733401658913525044681345354735169063332364028916249215731776925628054134802192056354692711345644113116024086506315163983761702528400513318774942750160396240601420096
131072 42318770960359583789988644118915089624828279705852293016397412440111554181897121558680195968563078895466157071383088460984793490965679933593163631387624285965869981759225557650656141144253500198111020608933859855298258047585820501887920508712109294411172587339441053188474119230088
262144 337921274602269292386513683479868464446547970090173436135676243425076667414647182678643347479504423685956166574967004335481798804071368815228200985411893618540391179496426485388956468320643141128113572441213099161554174008432809835998369904762367848771564953678585996936859404431031344330748379170029610527780387086976884267842617034458971559098431729081431616824641350333475713304741328821232136928

All of these are even after the first two. This is because the only numbers whose number of partitions into distinct terms is odd are the general pentagonal numbers (numbers of the form n*(3n-1)/2 for n a positive, negative or zero integer, i.e. 0, 1, 2, 5, 7, 12, 15, 22, 26, 35, 40, etc.) These numbers are also the basis of the lags in the fast recurrance used in the first applet on this page to calculate all partitions of a number.

The applet above applied one constraint. The next applies two, and so is slower and uses more memory. You put the total in the first box, the constraints in the next two small boxes, and click the Calculate button. You can choose how the constraints apply.

MORE TO COME HERE.

The next little applet calculates terms of the "magic sequence".
In an x*x magic square, the numbers in the square add up to x2(x2+1)/2 so each row of x numbers adds up to x(x2+1)/2.
How many potential rows are there? i.e. how many partitons of x(x2+1)/2 into x distinct positive integers each less than or equal to x2?
This is the same as the number of partitions of x2(x-1)/2 into up to x positive integers (not necessarily distinct) where each is less than or equal to x(x-1).

Just put a small positive integer (e.g. 10) in the first box and press the button. There is a memory constraint on the size of the number as well as a speed issue, and the smaller the number the more quickly terms can be calculated.

The Java source code is here. This applet was the original of this set, and the inspiration for the others.

Using essentially the same code but as a java application, I obtained the following sequence for x=1 through to 36:
1 1
2 2
3 8
4 86
5 1394
6 32134
7 957332
8 35154340
9 1537408202
10 78132541528
11 4528684996756
12 295011186006282
13 21345627856836734
14 1698954263159544138
15 147553846727480002824
16 13888244935445960871352
17 1408407905312396429259944
18 153105374581396386625831530
19 17762616557326928950637660912
20 2190684864446863915195866500356
21 286221079001041327793634043938470
22 39493409270082248457567923104977298
23 5739019677324553608481368828138484550
24 876085202984795348523051418634128837562
25 140170526450793924490478768121814869629364
26 23456461153390020211328759135664689342531028
27 4097641100787806775815644958425464097739938654
28 745947846718066619823209422870621836022069177558
29 141280774936453250057100993123755087750662375504136
30 27797610141981037322555479186167243505129073097363174
31 5673858009208148397135070998960708533898456476297052346
32 1199872454897380013845796517790093662180055383301098878668
33 262575529501655719245725510596713937964488091566840353740484
34 59394620657532913580290882324816355506080733247883160869518486
35 13872534241478210358349096341203128450357241660871429860873721318
36 3342339793871651580291139212736788281034702731706602993356140483430

Henry Bottomley 2002