hp41programs

Partitions Number of Partitions for the HP-41

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) = 44583 ( 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: /

-Line 125 is a three-byte GTO 01

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
126 FIX 4
127 END

( 159 bytes / SIZE 009 )

STACK	INPUTS	OUTPUTS
X	n	p(n)

Examples:

100 XEQ "PART2" >>>> p(100) = 190569292 ( 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 , ..... ),

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) = 1260 ( 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: /

-Line 121 is a three-byte GTO 01

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
122 FIX 4
123 END

( 158 bytes / SIZE 007 )

STACK	INPUTS	OUTPUTS
X	n	q(n)

Examples:

200 XEQ "PART4" >>>> q(200) = 487067755 ( in 58s ) ( exact value is 487067746 )
1000 R/S >>>> q(1000) = 8.635565946 10²¹ ( in 49s )

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

References:

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