PART2K.BAS
January 2000 by Marc Kummel aka Treebeard.
Contact mkummel@rain.org, http://www.rain.org/~mkummel/

 What is PART2K.BAS?
--------------------
PART2K is a BASIC program to find partitions of a number N into all parts,
possibly unique, that add up to that sum, with the optional constraints that
all partitions have just M parts and that all parts be <= P.  I wrote this 
program to solve a problem that arises with with magic squares and other 
recreational math stumpers:

    What are all the ways in which m different numbers can add up to n, 
    without regard to order?

Partitioning is a bit like factoring in that it decomposes a number, but it 
uses addition rather than multiplication. This was a fun programming 
challenge that uses recursive functions.  

There are several different partition functions that PART2K can solve:

  P(n)    gives the number of ways of writing the number n as a sum
          of positive integers without regard to order.
  Q(n)    gives the number of ways of writing the number n as a sum
          of unique positive integers without regard to order.
  P(n,m)  gives the number of ways of writing the number n as a sum 
          of m positive integers without regard to order.
  Q(n,m)  gives the number of ways of writing the number n as a sum 
          of m unique positive integers without regard to order.

It's also possible to add the constraint to any of these functions that no 
number be greater than p.

For example, consider the 11 partitions of 6:
  (1) 6  =  6 
  (2)    =  5 + 1 
  (3)    =  4 + 2 
  (4)    =  4 + 1 + 1 
  (5)    =  3 + 3 
  (6)    =  3 + 2 + 1 
  (7)    =  3 + 1 + 1 + 1 
  (8)    =  2 + 2 + 2 
  (9)    =  2 + 2 + 1 + 1 
  (10)   =  2 + 1 + 1 + 1 + 1 
  (11)   =  1 + 1 + 1 + 1 + 1 + 1

From this partitioning, we see that:
  P(6)   =  11     {1 .. 11}      (all partitions)
  Q(6)   =  4      {1, 2, 3, 6}   (all partitions with unique numbers)
  P(6,2) =  3      {2, 3, 5}      (all partitions into 2 numbers)
  Q(6,2) =  2      {2, 3}         (all partitions into 2 unique numbers)

This is easy with small numbers, but P() and Q() are eponential functions 
that grow large fast!

  P(1000) = 24,061,467,864,032,622,473,692,149,727,991  (2.4 x 10^31)

My program uses the BASIC currancy data type to keep the exact count, so the 
upper limit is about 9.2 x 10^14.  Big, but not big enough for the P(2000) 
problem I originally wanted to solve.  On the other hand, my program doesn't
just count partitions, it actually finds them, and time is a factor.  There 
are faster ways to just get the count that I would like to implement.

For more info on Partition functions, check out my Millenium Magic stumper
at <http://www.rain.org/~mkummel/stumpers/17dec99a.html>.  There's advanced
discussion of the math at Eric Weisstein's World of Mathematics site at
<http://mathworld.wolfram.com/Partition.html>.

 Using PART2K.BAS
-----------------
PART2K is a simple DOS program.  Run it in DOS, or a Command session in 
Windows.  There are several options that can be set from the command line, 
or interactively if the program is started without parameters (which I 
recommend).

Usage: PART2K [n m [p] [/q] [/swc?] [/d[x]] [/f[name.ext]]
Options:
    n   =  The positive integer N to partition,
   [m]  =  with the constraint that partitions have just M parts, and
   [p]  =  with the additional constraint that no part be > P.
  [/q]  =  Find only partitions into unique parts Q(n).
  [/d]  =  Process multiple partitions with step value x.
  [/s]  =  Show partitions on screen as found.
  [/w]  =  Show working count on screen.
  [/c]  =  Add partition count to <numpart.dat> compilation file.
  [/f]  =  Write all partitions to <name.ext>, could be huge!
  [/?]  =  This help.
 
The /d and /c options are useful together to partition many numbers and save 
the counts into a tab delimited file for import into a spreadsheet program.  
Use the /f option to save the actual partitions, but the file might be huge! 
Pressing <Esc> should stop the program while it is working, but you may have 
to wait a while for it to take effect.  It's faster if you turn off the 
display options.

 The Files:
-----------
I wrote this program to solve a stumper.  You'll have to study the source 
code for more info.  I wrote it using MS Basic PDS v7.10.  It will need 
some work in QBasic or Quick Basic.

  PART2K.EXE         DOS executible to partition a number
  PART2Knn.BAS       BASIC source code
  NUMPPART.DAT       Compilation file to store results with /c option
  README.TXT         This file
  TBVAULT.TXT        Treebeard's Basic Vault info

 Conditions:
------------
This program and source code are yours to use and modify as you will, but 
they are offered as freeware with no warranty whatsoever.  Give me credit, 
but do not distribute any changes under my name, or attribute such changes 
to me in any way.  You're on your own!  

If you find this program or code useful, then let me know what you do with 
it, as a courtesy to a fellow programmer who still hacks for fun and glory.
Any suggestions or comments will be much appreciated.

Send comments and fixes to:

  Marc Kummel aka Treebeard
  mkummel@rain.org
  http://www.rain.org/~mkummel/
  http://www.treebeard.org/

For more interesting Basic software with source code, check out Treebeard's 
Basic Vault at <http://www.rain.org/~mkummel/basic/>.