(49g 50g) Partition Numbers, Q Partition numbers

[John Keith]

Edited to replace second program with smaller and faster version, and to add program for Q partitions.

Edited again 07/20/2023 with improved second and third programs.

Given an integer n on the stack, the first two programs return a list of the partition numbers (A000041) from 0 through n. The first program is small, and the second one is fast.

The following program is based on a summation involving the divisor sigma function (sum of divisors of an integer) shown here. It uses Gerald Hillier's SUMDIVISORS program from hpcalc.org. It also requires ListExt, and must be run in exact mode.

Code:


\<< DUP LSEQ 1 SUMDIVISORS { 1 1 } ROT 2 SWAP
  FOR n OVER 1 n SUB REV OVER * LSUM n / +
  NEXT NIP
\>>

The next program uses a recurrence based on Euler's Pentagonal Number Theorem, as shown here. The first part of the program is devoted to generating a list of generalized pentagonal numbers. This program requires ListExt and should be run in exact mode to give exact results for larger values of n.

Code:


\<< I\->R DUP \v/ CEIL 1. 2. PICK3 LASEQ SWAP LSEQ
2. \->LIST LCLLT :: + LSCAN 3. \-> s gpn j
  \<< 1 1 2. s
    FOR n DUP2 + 3. DUP 'j' STO
      WHILE 'gpn' SWAP GET DUP n \<=
      REPEAT 1. + PICK j 2. / CEIL 2. MOD { + } { - } IFTE 'j' INCR
      END DROP
    NEXT s 1. + \->LIST
  \>>
\>>

The second program is 2 to 6 times as fast as the first depending on list size.


This next program returns a list of Q partitions ( A000009) which are the number of partitions into distinct parts, or odd parts. See here for description.

Edit: this program is semi-obsolete for the HP 49 and 50. See post #3 below.

Code:


\<< I\->R DUP \v/ CEIL 1. 2. PICK3 LASEQ SWAP LSEQ 2. \->LIST LCLLT
:: + LSCAN 3. \-> s gpn j
  \<< 1 1 2. s
    FOR n DUP2 + 3. DUP 'j' STO
      WHILE 'gpn' SWAP GET DUP n \<=
      REPEAT 1. + PICK j 2. / CEIL 2. MOD { + } { - } IFTE 'j' INCR
      END DROP gpn n 2. / POS
      IF DUP
      THEN 2. / CEIL 2. MOD { 1 - } { 1 + } IFTE
      ELSE DROP
      END
    NEXT s 1. + \->LIST
  \>>
\>>

This program is essentially the same as the second program except for the IF...THEN...ELSE structure at the end. The two can easily be combined into one program if desired.

[John Keith]

Next, a program that returns the partition number triangle, A008284, as a list of lists. It is large (214 bytes) but fast, as it takes advantage of many patterns that occur in the triangle.

HP-48G compatible if the commands I->R and R->I are removed and PICK3 changed to 3 PICK.

Code:


\<< I\->R \-> n
  \<< { 1 } DUP 1 + DUP 1 + 4. n
    FOR k { 1 } k 2. / IP R\->I +
      IF k 5. >
      THEN 3. DUP k 6. - 2. / IP +
        FOR j j 1. + PICK j GET PICK3 j 1. - GET + +
        NEXT
      END OVER k 2. / IP k SUB +
    NEXT n \->LIST
  \>>
\>>

Partial sums of rows are A026820, the partition of n into at most k parts. These are the numbers returned by Gerald Hillier's program here.

[John Keith]

The next program returns rows 1 through n of A008289, the Q partition triangle, Q(n,m) = number of partitions of n into m distinct parts, n>=1, m>=1. Computation starts with row 6 to avoid time-consuming tests inside the loop.

First, the HP 49/50 version using exact integers.

Code:


\<< I\->R \-> n
  \<< { 1 } DUPDUP 1 + DUP PICK3 2 + 6. n
    FOR k { 1 } k 1. - 2. / IP R\->I +
      3. k 8. * 1. + \v/ 1. - 2. / IP
      FOR j j 1. + PICK 0 +
        j 1. - j SUB EVAL + +
      NEXT
    NEXT n \->LIST
  \>>
\>>

Next, an HP-28 compatible version. For the HP-48, LIST\-> DROP can be replaced with EVAL.

Code:


\<< \-> n
  \<< { 1 } DUP DUP 1 + DUP 3 PICK 2 + 6 n
    FOR k { 1 } k 1 - 2 / IP +
      3 k 8 * 1 + \v/ 1 - 2 / IP
      FOR j j 1 + PICK 0 +
        j 1 - j SUB LIST\-> DROP + +
      NEXT
    NEXT n \->LIST
  \>>
\>>

Additional note: The sum of the terms of each row is A000009(n) which is the sequence computed by the third program in post #1. On the HP 49 and 50 with ListExt, this program can be followed by :: LSUM LMAP to return a list of A000009 from 1..n. This is actually a bit faster than the above program, which should now be considered semi-obsolete on the HP 49 and 50.