The Museum of HP Calculators

Number of Partitions for the HP-41

This program is supplied without representation or warranty of any kind. Jean-Marc Baillard and The Museum of HP Calculators therefore assume no responsibility and shall have no liability, consequential or otherwise, of any kind arising from the use of this program material or any part thereof.

Overview

-The number of unrestricted partitions p(n) is the number of decompositions of n into integer summands without regard to order.
-The number of partitions into distinct parts q(n) is the number of decompositions of n into distinct integer summands without regard to order.
-The following programs use 2 methods to compute p(n) and q(n):

a) A recurrence relation ( for n < 319 )
b) A series expansion

1°) Unrestricted Partitions: p(n)

a) Recurrence Relation

Formula: p(1) = 1 and p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + ...... where the signs are alternatively + + - - + + - - .....
and the number subtracted from n are: (3k²-k)/2 ; (3k²+k)/2 ( k = 1 , 2 , ..... )

Data Registers: R00 = 1 ; R01 = p(1) ; ............ ; Rnn = p(n)
Flags: F10
Subroutines: /

01 LBL "PART1"
02 STO O
03 E3
04 /
05 STO N
06 SIGN
07 STO 00
08 ST+ N
09 LBL 01
10 CF 10
11 2
12 STO M
13 CLX
14 LBL 02
15 RCL M
16 RCL X
17 RCL 00
18 +
19 *
20 6
21 /
22 STO Z
23 RCL N
24 -
25 X>0?
26 GTO 03
27 X<>Y
28 RCL IND Y
29 FS? 10
30 CHS
31 +
32 R^
33 RCL M
34 RCL 00
35 +
36 3
37 ST+ M
38 /
39 +
40 RCL N
41 -
42 X>0?
43 GTO 03
44 X<>Y
45 RCL IND Y
46 FS? 10
47 CHS
48 +
49 FC?C 10
50 SF 10
51 GTO 02
52 LBL 03
53 X<>Y
54 STO IND N
55 ISG N
56 GTO 01
57 RCL O
58 SIGN
59 RCL IND L
60 CF 10
61 CLA
62 END

( 100 bytes / SIZE = max( 2 ; nnn+1 ))

      STACK        INPUTS      OUTPUTS

           X             n           p(n)

           L             /             n

Example: 41 XEQ "PART1" >>>> p(41) = 44,583 ( in 2mn29s ) and p(1) , p(2) , ....... , p(41) in R01 , R02 , ........ , R41

b) A Series expansion

Formula: p(n) = 1/(pi) SUM_{k=1,2,3,.....} k^1/2 A_k(n).( ( cosh(pi(2(n-1/24)/3)^1/2/k) (2/3)^1/2 pi/k )/(n-1/24) - sinh(pi(2(n-1/24)/3)^1/2/k)/(n-1/24)^3/2 )/2

with A_k(n) = SUM_{h=1,2,...,k ; GCD(h,k)=1} cos( pi.S(h,k) - 2(pi)n.h/k ) where S(h,k) = SUM_{j=0,1,...,k-1} ( frc(h.j/k) -1/2 )( j/k - 1/2 )

Data Registers: R00 = n ; R01 = partial sums and p(n) ; R02 to R08 = temp
Flags: /
Subroutines: /

01 LBL "PART2"
02 DEG
03 STO 00
04 24
05 1/X
06 -
07 STO 06
08 SQRT
09 1.5
10 1/X
11 SQRT
12 STO 08
13 *
14 STO 07
15 CLX
16 STO 01
17 SIGN
18 STO 02
19 FIX 0
20 LBL 01
21 RCL 02
22 STO 03
23 CLX
24 STO 04
25 LBL 02
26 RCL 02
27 RCL 03
28 LBL 03
29 MOD
30 LASTX
31 X<>Y
32 X#0?
33 GTO 03
34 SIGN
35 X#Y?
36 GTO 06
37 RCL 02
38 X<>Y
39 -
40 X=0?
41 GTO 05
42 STO 05
43 CLX
44 LBL 04
45 RCL 03
46 RCL 05
47 *
48 RCL 02
49 /
50 FRC
51 RCL 05
52 RCL 02
53 /
54 .5
55 ST- Z
56 -
57 *
58 +
59 DSE 05
60 GTO 04
61 LBL 05
62 4
63 1/X
64 +
65 RCL 00
66 ST+ X
67 RCL 03
68 *
69 RCL 02
70 /
71 -
72 PI
73 R-D
74 *
75 COS
76 ST+ 04
77 LBL 06
78 DSE 03
79 GTO 02
80 RCL 07
81 PI
82 *
83 RCL 02
84 /
85 E^X
86 ENTER^
87 ENTER^
88 1/X
89 ST- Z
90 +
91 RCL 08
92 *
93 RCL 06
94 ST/ Z
95 /
96 PI
97 *
98 RCL 02
99 /
100 X<>Y
101 RCL 06
102 SQRT
103 /
104 -
105 RCL 02
106 SQRT
107 *
108 PI
109 4
110 *
111 /
112 ENTER^
113 ISG 02
114 CLX
115 RCL 04
116 *
117 RCL 01
118 +
119 STO 01
120 ST+ Y
121 RND
122 X<>Y
123 RND
124 X#Y?
125 GTO 01 ( a three-byte GTO )
126 FIX 4
127 END

( 159 bytes / SIZE 009 )

Examples: 100 XEQ "PART2" >>>> p(100) = 190,569,292 ( in 45seconds )
721 R/S >>>> p(721) = 1.610617578 10²⁶ ( in 9seconds ) ( the last digits should be 57 instead of 78 )

2°) Partitions Into Distinct Parts: q(n)

a) Recurrence Relation

Formula: q(0) = 1 and q(n) = E_n + q(n-1) + q(n-2) - q(n-5) - q(n-7) + ......

where the signs are alternatively   + + - - + + - - ..... , the number subtracted from n are:   (3k²-k)/2 ; (3k²+k)/2    ( k = 1 , 2 , ..... ),
and   E_n = (-1)^r if n = 3r²+r or 3r²-r with r = an integer
          E_n =   0     otherwise.

Data Registers: R00 = 1 ; R01 = q(1) ; ............ ; Rnn = q(n)
Flags: F10
Subroutines: /

01 LBL "PART3"
02 STO O
03 E3
04 /
05 STO N
06 SIGN
07 STO 00
08 ST+ N
09 LBL 01
10 CF 10
11 2
12 STO M
13 RCL N
14 INT
15 12
16 *
17 RCL 00
18 +
19 SQRT
20 STO Y
21 RCL 00
22 ST+ Z
23 -
24 6
25 ST/ Z
26 /
27 FRC
28 X=0?
29 GTO 04
30 X<>Y
31 FRC
32 X=0?
33 GTO 04
34 CLX
35 GTO 02
36 LBL 04
37 RCL 00
38 CHS
39 LASTX
40 Y^X
41 LBL 02
42 RCL M
43 RCL X
44 RCL 00
45 +
46 *
47 6
48 /
49 STO Z
50 RCL N
51 -
52 X>0?
53 GTO 03
54 X<>Y
55 RCL IND Y
56 FS? 10
57 CHS
58 +
59 R^
60 RCL M
61 RCL 00
62 +
63 3
64 ST+ M
65 /
66 +
67 RCL N
68 -
69 X>0?
70 GTO 03
71 X<>Y
72 RCL IND Y
73 FS? 10
74 CHS
75 +
76 FC?C 10
77 SF 10
78 GTO 02
79 LBL 03
80 X<>Y
81 STO IND N
82 ISG N
83 GTO 01
84 RCL O
85 SIGN
86 RCL IND L
87 CF 10
88 CLA
89 END

( 135 bytes / SIZE = max( 2 ; nnn+1 ) )

      STACK        INPUTS      OUTPUTS

           X             n           q(n)

           L             /             n

Example: 41 XEQ "PART3" >>>> q(41) = 1,260 ( in 3mn ) and q(1) , q(2) , ....... , q(41) in R01 , R02 , ........ , R41

b) A Series expansion

Formula: q(n) = SUM_{k=1,2,3,.....} A_2k-1(n). I₁(pi((n+1/24)/3)^1/2/(2k-1)) (1/3)^1/2 pi/(2k-1) )/(2(n+1/24)^1/2)

where A_k(n) and S(h,k) are defined as above ( 1°)b) ) and I₁(x) = the modified Bessel function of order 1.

Data Registers: R00 = n ; R01 = partial sums and q(n) ; R02 to R06 = temp
Flags: /
Subroutines: /

01 LBL "PART4"
02 DEG
03 STO 00
04 24
05 1/X
06 +
07 STO 06
08 CLX
09 STO 01
10 SIGN
11 STO 02
12 FIX 0
13 LBL 01
14 RCL 02
15 STO 03
16 CLX
17 STO 04
18 LBL 02
19 RCL 02
20 RCL 03
21 LBL 03
22 MOD
23 LASTX
24 X<>Y
25 X#0?
26 GTO 03
27 SIGN
28 X#Y?
29 GTO 06
30 RCL 02
31 X<>Y
32 -
33 X=0?
34 GTO 05
35 STO 05
36 CLX
37 LBL 04
38 RCL 03
39 RCL 05
40 *
41 RCL 02
42 /
43 FRC
44 RCL 05
45 RCL 02
46 /
47 .5
48 ST- Z
49 -
50 *
51 +
52 DSE 05
53 GTO 04
54 LBL 05
55 4
56 1/X
57 +
58 RCL 00
59 ST+ X
60 RCL 03
61 *
62 RCL 02
63 /
64 -
65 PI
66 R-D
67 *
68 COS
69 ST+ 04
70 LBL 06
71 DSE 03
72 GTO 02
73 RCL 06
74 PI
75 RCL 02
76 /
77 X^2
78 *
79 12
80 /
81 STO 03
82 SIGN
83 ENTER^
84 STO 05
85 ENTER^
86 LBL 07
87 X<> Z
88 RCL 03
89 *
90 RCL 05
91 ST/ Y
92 1
93 +
94 STO 05
95 /
96 ST+ Y
97 X<> Z
98 X#Y?
99 GTO 07
100 PI
101 RCL 02
102 /
103 X^2
104 *
105 2
106 ST+ 02
107 6
108 *
109 /
110 STO Y
111 RCL 04
112 *
113 RCL 01
114 +
115 STO 01
116 ST+ Y
117 RND
118 X<>Y
119 RND
120 X#Y?
121 GTO 01 ( a three-byte GTO )
122 FIX 4
123 END

( 158 bytes / SIZE 007 )

Examples: 200 XEQ "PART4" >>>> q(200) = 487,067,755 ( in 58s ) ( exact value is 487,067,746 )
1,000 R/S >>>> q(1000) = 8.635565946 10²¹ ( in 49s )

-"PART4" seems to produce greater roundoff errors than "PART2"

References: John H. Conway & Richard K. Guy , "The Book of Numbers" - Springer Verlag - ISBN 0-387-97993-X
Abramowitz and Stegun , "Handbook of Mathematical Functions" - Dover Publications - ISBN 0-486-61272-4

Go back to the HP-41 software library
Go back to the general software library
Go back to the main exhibit hall