(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.