As a lot of you, I am unable to clearly understand and play with the specific mathematical notioa couple of n, Bessel function and infinite series extensively used in this publication. I am unable to follow the tricky path the authors have used to achieve to an ‘arithmetic expression’ of the partition p(n) of any integer n.
But the link and recommendations that Katie give us in her post, allow me to use one of the recurrent approach of the problem to write of few codes to calculate partitions on any HP28C/S or HP41C.
Recursion, arithmetic and memory
As Katie have advert it, my code stores the values of p(n) in order to avoid an impossible amount of recursion. In the same time, this makes computation much more time efficient.
The philosophy of my approach is to store the first m pre-calculated values of p(n) into the calculator register
Thus, asking for any partition number p(n) where n<m is as trivial as recalling a register content.
For any non pre-calculated p(n), the following method is used to compute and store in memory p(n) from previous (and already store in most case) p(n-q) :
From Euler’s pentagonal number theorem, we have the general sum:
p(n) = p(n - 1) + p(n - 2) - p(n - 5) - p(n - 7) + p(n - 12) + p(n - 15)...
Where terms of this sum are where k is a relative integer used to generate a suitable set of “Euler’s pentagonal numbers” q.
This summation gives the new and unknown number of partitions p(n) as a function of previous value p(n-q).
Validity is that we have to sum for any 0 < n-q < n, which lead to a sequence of alternatively positive and negative k 1, -1, 2, -2, 3, -3, 4, -4, ... and so on until q>n.
A special attention have to be care incase when q = n where p(0) = 1 has to be consider.
But this will be treated later in code, due to a specific memory usage. Only p(n) for n = 1 to m are store in memory or memory register from R01 to Rmm
Example1:
Already in memory: p(1) = 1, p( 2 ) = 1
Computing p(3)
k | 1 -1 2
------+----------------------------------------------
Sign | + + -
q | 1 2 5 out of range q>n
n-q | 2 1
p(n-q)| +2 +1
------+---------------------------------------------
Thus p(3) = 2 + 1 = 3
Example2:
Already in memory : p(1) = 1, p( 2 ) = 1, p(3) = 3, p(4) = 5
Computing p(5)
k | 1 -1 2
------+----------------------------------------------
Sign | + + -
q | 1 2 5
n-q | 3 2 0
p(n-q)| +3 +5 -1
------+---------------------------------------------
Thus p(5) = 3 + 5 – 1 = 7
Example3:
Already in memory : p(1) to p(5)
Computing p(10)
k | 1 -1 2 -2 3
------+----------------------------------------------
Sign | + + - - +
q | 1 2 5 7 12 out of range q>10
n-q | 9 2 5 3
p(n-q)|+(30) +(22) -7 -3 () indicate external recursive calls
------+---------------------------------------------
Thus p(5) = 30 + 22 – 7 - 3 = 42
The behavior of the summation when attempting to use an non pre-calculated p(n-q) partition depends of the power of the calculator and its ability to recursively compute it.
That why I have first developed an algorithm on my HP28S, since large memory allow directly recursive calls for unknown (and non store) value.
For the HP41C version, the purely recursive algorithm was adapted for using no strictly recursive calls.
In fact, the really first tries on the HP28S show me that any attempt to compute a new p(n) greater that the last p(m) in memory generate cascading recursive calls to compute p(n-1), p(n-2), p(n-3), ... p(m+1) since any summation start with q=1.
So, the HP41C avoid any recursive calls by simply looping from m to n by step 1. This spares large among of memory and time.
To generate the sign sequence, two flag are used which greatly help generated the k sequence and summation/subtraction alternate.
k ope | Flag#1 Flag#2 | q p(n-q) | sum/sub
------------+-----------------+-------------+---------
1 +1 | 0 0 | 1 p(n-1) | +
-1 neg | 1 0 | 2 p(n-2) | +
2 +1 | 0 1 | 5 p(n-5) | -
-2 neg | 1 1 | 7 p(n-7) | -
3 +1 | 0 0 | 12 p(n-12)| +
etc
------------+-----------------+-------------+---------
Clearly two flags are needed to code a four steps sequence.
Flag#1 indicate when
k have to be incremented after its sign change.
Flag#2 indicate when subtraction is replacing addition of
p(n-q)
HP 28C/S version
Three programs:
INIT to initiate PDAT array in memory and set p(1)=1.
P to compute p(n) from memory (i.e. PDAT array) or by recursively calling PCALC
PCALC to compute p(n) when n is greater then pre-calculated p(m).
Memory usage:
The p(n) are stored in the array 'PDAT' initialized up to 200 elements with ‘PDAT(1) = 1’ only, all other set to zero.
Usage:
Before any use of P, one may invoke initialization of memory array ‘PDAT’ by typing INIT [ENTER] or using USER menu soft key.
Recursive computation of any p(n) from 1 to m can be lunch by typing or using softkeys
m P [ENTER] or equivalently m PCALC [ENTER]
After initial pre-calculation, any p(n) with n<m can be obtain immediately by typing :
n P [ENTER]
CODE for HP28C/S or any RPL calculators
@@ -------------------------- INIT ---------------:
« {200} 0 CON 1 1 PUT 'PDAT' STO »
'INIT' STO @ construct an array of 200 elements all zero except #1 which is 1 (p(1)=1)
@@ -------------------------- P ---------------:
« 'PDAT' OVER GET
IF DUP @ test zero which indicate non pre-stored value
THEN SWAP DROP @ makes p(n) top of the stack
ELSE DROP PCALC @ call n PCALC to compute unknown p(n)
END
»
'P' STO
@@ -------------------------- PCALC ---------------:
« -> n @ n
« 1 SF 2 SF
0 @ Initialise sum
0 @ Initialise k
DO @ main loop - summing/soustracting p(q_k)
NEG @ k --> -k
IF 1 FS?C @ clear flag #1 (next loop only change sign of k)
THEN
2 NF @ change position of flag #2 (cf. NF )
1 + @ k --> k+1
ELSE
1 SF @ set flag #1 (next loop increment k)
END
3 OVER * 1 - OVER * 2 / @ compute pentagonal integer q = k(3k-1)/2
n SWAP -
IF DUP 0 > @ test validity of n-q as
THEN
« P » RSTF @ recursively call p(n-q) preserving flags status (cf. RSTF)
ELSE
0 == @ hold 1 when p(0) is involve in the sum
SWAP DROP 0 SWAP @ set k to zero ( = loop exit condition )
END
ROT SWAP
IF 2 FS? @ test flag #2 for
THEN - @ soustrating
ELSE + @ or additing p(n-q) to sum
END
SWAP
UNTIL DUP NOT END @ loop until k has been set to zero
DROP
'PDAT' n 3 PICK PUT @ put p(n) in PDAT for further uses
n 1 DISP @ display n in line 1
DUP 2 DISP @ display p(n) in line 2
CLMF
»
»
'PCALC' STO
@@ -------------------------- flag #1 & #2 rules ---------------:
F#1 F#2 Sum q=k(3k-1)/2 p()
k= 1 c c + 1 p(n-1)
k=-1 s c + 2 p(n-2)
k= 2 c s - 5 p(n-5)
k=-2 s s - 7 p(n-7)
k= 3 c c + 12 p(n-12)
k=-3 s c + 15 ...
etc...
k= 0 exit loop q>n
P.S.: if n=q, p(0)=1 have to be take into account.
@@ -----------------------------------NF subprogram ----------------------
« IF DUP FS? @ negate flag status
THEN CF
ELSE SF
END
»
'NF' STO
@@ ----------------------------------RSTF subprogram ---------------------
« RCLF -> F « EVAL F STOF » » @ Execute (EVAL) a program and restore initial flag's status
HP 41C version
This version is an adaptation of the HP28S version code. The same sub-programs may be found in the code at the specific labels.
Main differences are that direct recursive calls of PCALC have been transform into a from m+1 to n one by one step loop using ISG 00.
Program:
Type [EXC][ALPHA]PART[ALPHA] to initiate memory and set p(1)=1.
The calculator display 1.0000 indicates a successfully initialization.
Usage
To compute p(n) simply enter n and press [ A ] soft key ( S+ key in USER mode).
If p(n) already in memory, result is immediately display. The sequence is equivalent to recalling or viewing register (RCL nn or VIEW nn can be used to display p(nn) for any nn<100).
If n is greater than previously computed and memorized p(n), the calculator sequentially compute any p(n) from last in memory up to n.
The larger n, the slowest is the computation.
Memory usage:
The p(n) are stored in the register from R01 up to Rmm depending of available memory and the SIZE mmm setting.
The register R00 is used to count/loop and store the last register position.
The ALPHA register is used to display progression during extended computations.
Flag#0 is used for indicating erroneous condition (mainly badly initiate register or interrupted R/S)
Flag#1, Flag#2 are used for k sequence and summation/subtraction alternate.
Flag#3 is used for treated the special n = q cases.
CODE for HP41C/CV/CX or any compatible calculators
PRGM t: z: y: x:/disply Comments
01 LBL "PART @ Init PARTition program
02 CLRG @ clear all the registers
03 1 1
04 STO 01 @ p(1) = 1
05 STO 00 @ nb of registred p(n) set to 1 (m)
06 RTN
1.0000
------------------------------------------------------------
n
07 LBL "A @ ENTER n PRESS "A" key
08 CF 00 @ clear error indicator (Flag #0)
09 RCL IND X n Rn @ recall p(n)
10 x=0?
11 GTO 00 n 0 @ Goto to PCalc routine
12 RTN
n p(n)
------------------------------------------------------------ PCalc
13 LBL 00 n 0
14 RDN n
15 1 E 3
16 / .nnn @
17 RCl 00 .nnn m
18 INT
19 + m.nnn
20 STO 00 @ store loop index in R00
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
21 LBL 01 @ increment R00 (m.nnn)
22 ISG 00
23 GTO 02 @ goto new p(n) computation
24 DSE 00 @ decrease R00 to match register contents
25 RTN
26 RTN p(n) @ stop when m = n
@ leave p(n) in x: (true end of program)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - p(n)=SUM +- p(n-q)
27 LBL 02
28 CF 01 @
29 SF 02
30 0 m.nnn 0 @ Initialise sum
31 0 m.nnn 0 0 @ Initialise k
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Main Loop SUM +-
32 LBL 03 S k @ Main loop (summing)
33 CHS
34 FS?C 01 @ F1=c next k is k+1
35 GTO 04
36 1
37 + @ k <-- k+1
38 SF 01 @ F1=s next k is -k
39 FS?C 02
40 GTO 04 @ invert F2
41 SF 02 @ F2=s substrat p(n-q)
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
42 LBL 04 ~ S k @ compute pentagonal integer k(3k-1)/2
43 3 S k 3
44 RCL Y S k 3 k
45 * S S k 3k
46 1 S k 3k 1
47 - S S k 3k-1
48 RCL Y S k 3k-1 k
49 * S S k k(3k-1)
50 2 S k k(3k-1) 2
51 / S S k q @ q=k(3k-1)/2
52 RCL 00 S k q m.nnn
53 INT S k q n
54 x<=y? @ test n<=q ?
55 GTO 05 @ then exit main loop
56 x<->y S k n q
57 - S S k n-q
58 RCl IND X S k n-q p(n-q)
59 x=0?
60 SF 00 @ tag error (unconsistant register value)
61 FS? 02
62 CHS +-p
63 ST+ T S+-p k n-q p(n-q)
64 RDN ~ S+-p k n-q
65 RDN ~ ~ S+-p k
66 GTO 03 @ do main loop (summing)
- - - - - - - - - - - - - - - - - - - - - - - - - - -
67 LBL 05 S k q n @ End of main loop
68 x=y?
69 SF 03 @ n=q flag
70 R^ k q n S
71 FC?C 03 @ test special cas n=q ?
72 GTO 06
73 1 q n S 1
74 FS? 02 @ test +/- sequence position
75 CHS q n S +-1
76 + q q n S+-1
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
77 LBL 06 n S
78 STO IND Y @ memorize p(n) <-- S
79 CLA
80 ARCL Y @ Prepare display
81 "~:
82 ARCL X
83 AVIEW @ display progress during PRGM run
84 GTO 01
85 END
----------------------------------------------------------------------
@@ ------------------ Flag 1 & 2 rules
F1 F2 sum
k= 1 s c +
k=-1 c c +
k= 2 s s -
k=-2 c s -
Conclusion
As expected, this code may not obtain exact partition number up to p(200) due to the calculator’s number of digit limits.
The 12-digit HP28C/S arithmetic allow me to compute exact p(179)= 625846753120.
And the limit of exact partition number on the HP41C (with two memory modules) is p(131)=5964539504.
This result is confirmed by the HP28S display.
Note that expected largest 10-digit partition number was p(135)=9035836076 but is unachieved on the HP41C due to the 10-digits limitation in summation/subtraction process.
As well the expected maximal 12-digit number of partition p(184)= 980462880430 is not exact on the HP28S.
I am waiting for any improvements of this from any HP enthusiast user.
Edit: Add missing END of the DO ... UNTIL main loop
Edited: 31 Mar 2011, 12:10 p.m. after one or more responses were posted