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

-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  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 , ..... ),

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

-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  1021  ( 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