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 R_{01} to R_{mm}

**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 R_{01} up to R_{mm} depending of available memory and the SIZE mmm setting.

The register R_{00} 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*