+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: General Software Library (/forum-13.html)
+--- Thread: (49g 50g) Partition Numbers, Q Partition numbers (/thread-11466.html)
(49g 50g) Partition Numbers, Q Partition numbers - John Keith - 09-25-2018 08:36 PM
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.
RE: (49g 50g) Partition Numbers, Q Partition numbers - John Keith - 08-27-2019 01:02 PM
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.
RE: (49g 50g) Partition Numbers, Q Partition numbers - John Keith - 07-20-2023 11:59 AM
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.