Integer Partition

In number theory, a partition of a positive integer n is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered to be the same partition; if order matters then the sum becomes a composition. A summand in a partition is also called a part. The number of partitions of n is given by the partition function p(n).(Reference from Wikipeida)

Generating function

A generating function for p(n) is given by the reciprocal of Euler's function:

Expanding each term on the right-hand side as a geometric series, we can rewrite it as

(1 + x + x² + x³ + ...)(1 + x² + x⁴ + x⁶ + ...)(1 + x³ + x⁶ + x⁹ + ...) ....

The xⁿ term in this product counts the number of ways to write

n = a₁ + 2a₂ + 3a₃ + ... = (1 + 1 + ... + 1) + (2 + 2 + ... + 2) + (3 + 3 + ... + 3) + ...,

where each number i appears a_i times. This is precisely the definition of a partition of n, so our product is the desired generating function. More generally, the generating function for the partitions of n into numbers from a set A can be found by taking only those terms in the product where k is an element of A. This result is due to Euler.

The formulation of Euler's generating function is a special case of a q-Pochhammer symbol and is similar to the product formulation of many modular forms, and specifically the Dedekind eta function. It can also be used in conjunction with the pentagonal number theorem to derive a recurrence for the partition function stating that:

p(k) = p(k − 1) + p(k − 2) − p(k − 5) − p(k − 7) + p(k − 12) + p(k − 15) − p(k − 22) − ...

where the sum is taken over all generalized pentagonal numbers of the form ½n(3n − 1), for n running over positive and negative integers: successively taking n = 1, -1, 2, -2, 3, -3, 4, -4, ..., generates the values 1, 2, 5, 7, 12, 15, 22, 26, 35, 40, 51, .... The signs in the summation continue to alternate +, +, −, −, +, +, ...

My first version Common Lisp Code.

(defun penta(x)

  (* x (/ (- (* x 3) 1) 2)))

(defun IntegerPartitions(n)

  (let ((partitionsTable (make-hash-table))

(ipenta 0)

(temp 0)

(tempenta 0))

    (setf (gethash 1 partitionsTable) 1)

    (setf (gethash 2 partitionsTable) 2)

    (setf (gethash 3 partitionsTable) 3)

    (setf (gethash 4 partitionsTable) 5)

    (setf (gethash 0 partitionsTable) 1)

    (case n

       (1 1)

       (2 2)

       (3 3)

       (4 5)

       (0 1)

       (otherwise (progn (loop for i from 5 to n

                                    do(progn (setq ipenta 0)

                                                  (setq tempenta 0)

                                                  (setq temp 0)

                                                  (loop

                                                      do(progn (setq ipenta (+ ipenta 1))

                                                                    (setf tempenta (penta ipenta))

                                                                    (if (> tempenta i)

                                                                         (progn (setf (gethash i partitionsTable) temp)

                                                                                   (return))

                                                                         (setf temp (+ temp (gethash (- i tempenta) partitionsTable))))

                                                                    (setf tempenta (penta (- ipenta)))

                                                                    (if (> tempenta i)

                                                                         (progn (setf (gethash i partitionsTable) temp)

                                                                                   (return))

                                                                         (setf temp (+ temp (gethash (- i tempenta) partitionsTable))))

                                                                    (setf ipenta (+ ipenta 1))

                                                                    (setf tempenta (penta ipenta))

                                                                    (if (> tempenta i)

                                                                         (progn (setf (gethash i partitionsTable) temp)

                                                                                   (return))

                                                                         (setf temp (- temp (gethash (- i tempenta) partitionsTable))))

                                                                    (setf tempenta (penta (- ipenta)))

                                                                    (if (> tempenta i)

                                                                         (progn (setf (gethash i partitionsTable) temp)

                                                                                   (return))

                                                                         (setf temp (- temp (gethash (- i tempenta) partitionsTable)))))))))))

    (gethash n partitionsTable)))