The Museum of HP Calculators

# Number of Partitions for the HP-41

This program is Copyright © 2004 by Jean-Marc Baillard and is used here by permission.

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:   (3k2-k)/2 ;  (3k2+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) SUMk=1,2,3,..... k1/2 Ak(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     Ak(n) = SUMh=1,2,...,k ; GCD(h,k)=1  cos( pi.S(h,k) - 2(pi)n.h/k )    where  S(h,k) = SUMj=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  1026  ( 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) = En + q(n-1) + q(n-2) - q(n-5) - q(n-7) + ......

where the signs are alternatively   + + - - + + - - ..... , the number subtracted from n are:   (3k2-k)/2 ;  (3k2+k)/2    ( k = 1 , 2 , ..... ),
and   En = (-1)r  if  n = 3r2+r  or  3r2-r  with  r = an integer
En =   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) =  SUMk=1,2,3,.....   A2k-1(n).  I1(pi((n+1/24)/3)1/2/(2k-1)) (1/3)1/2 pi/(2k-1) )/(2(n+1/24)1/2)

where     Ak(n) and S(h,k)  are defined as above ( 1°)b) )  and  I1(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  1021  ( 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