The Museum of HP Calculators


Primes , Divisor Functions & Euler Function 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 following program displays the factorization of any integer N  ( 1 < N < E10 ) and when it stops,
  sk(n) = the sum of the k-th powers of the divisors of n is in X-register and in R06.
-It also calculates the Euler function phi(N)  in Y-register and in R04.
-phi(N) is the number of integers not exceeding and relatively prime to N

-Then, a second program computes sk(n) using multi-precision arithmetic. ( n < 100000 , k integer > 1 )
 

1°) Program#1
 

Registers:          R00 , R07 , R08:  temp
                           R01 = 2  ;  R02 = 4  ;  R03 = 6     ( these numbers are stored in data registers because digit entry is very slow on the HP-41 )
                           R04 = phi(N)
                           R05 = k ;  R06 =  sk(n)
Flag:  F29
Subroutines: /
 
 

  01  LBL "PRF"
  02  SIGN
  03  STO 06
  04  X<>Y
  05  STO 05
  06  LASTX
  07  ENTER^
  08  STO 04
  09  6
  10  STO 03
  11  4
  12  STO 02
  13  -
  14  STO 01
  15  FIX 0
  16  CF 29
  17  CLA
  18  ARCL Y
  19  "~="             (  I mean:  append  =  )
  20  MOD
  21  X=0?
  22  XEQ 02
  23  CLX
  24  3
  25  MOD
  26  X=0?
  27  XEQ 02
  28  CLX
  29  5
  30  MOD
  31  X=0?
  32  XEQ 02
  33  SIGN
  34  SIGN
  35  LBL 01
  36  X<> L
  37  RCL 03
  38  +
  39  MOD
  40  X=0?
  41  XEQ 02
  42  X<> L
  43  RCL 02
  44  +
  45  MOD
  46  X=0?
  47  XEQ 02
  48  X<> L
  49  RCL 01
  50  +
  51  MOD
  52  X=0?
  53  XEQ 02
  54  X<> L
  55  RCL 02
  56  +
  57  MOD
  58  X=0?
  59  XEQ 02
  60  X<> L
  61  RCL 01
  62  +
  63  MOD
  64  X=0?
  65  XEQ 02
  66  X<> L
  67  RCL 02
  68  +
  69  MOD
  70  X=0?
  71  XEQ 02
  72  X<> L
  73  RCL 03
  74  +
  75  MOD
  76  X=0?
  77  XEQ 02
  78  X<> L
  79  RCL 01
  80  +
  81  MOD
  82  X=0?
  83  XEQ 02
  84  X<> L
  85  X^2
  86  X<Y?
  87  GTO 01
  88  SIGN
  89  X=Y?
  90  GTO 05
  91  X<>Y
  92  ARCL X
  93  "~^1"             ( append  ^  1  )
  94  ST/ 04
  95  DSE X
  96  ST* 04
  97  R^
  98  RCL 05
  99  Y^X
100  1
101  +
102  ST* 06
103  AVIEW
104  GTO 05
105  LBL 02
106  STO 00
107  LBL 03
108  ISG 00
108  CLX
110  X<> L
111  ST/ Y
112  ST/ Z
113  ST/ T
114  MOD
115  X=0?
116  GTO 03
117  ARCL L
118  "~^"              ( append ^ )
119  ARCL 00
120  X<> L
121  ST/ 04
122  SIGN
123  X#Y?
124  "~*"             ( append * )
125  CLX
126  LASTX
127  DSE X
128  ST* 04
129  X<> L
130  STO 07
131  RCL 05
132  Y^X
133  SIGN
134  STO 08
135  LBL 04
136  LASTX
137  *
138  ST+ 08
139  DSE 00
140  GTO 04
141  X<> 08
142  ST* 06
143  X<> 07
144  SIGN
145  AVIEW
146  RTN
147  LBL 05
148  FIX 4
149  SF 29
150  RCL 04
151  RCL 06
152  END

( 232 bytes / SIZE 009 )
 
 
      STACK        INPUTS      OUTPUTS
           Y             k         phi(n) 
           X             n          sk(n) 

 

Example1:                 1  ENTER^
                       3238704  XEQ "PRF"  displays  ( successively )

           3238704=2^4*
           3238704=2^4*3^5*
           3238704=2^4*3^5*7*2*
           3238704=2^4*3*5*7^2*17^1         ( if there are more than 24 characters, the left part of the alpha string will be gradually truncated )

           s1(3238704) = 11577384  in X-register and in R06
  and   phi(3238704) =    870912  in Y-register and in R04

Example2:                 7  ENTER^
                                 24    R/S           produces   24^1=2^3*3*1              s7(24) = 4624699020  in registers X and R06
                                                                                                      and    phi(24) =         8            in registers Y and R04

Example3:                 0  ENTER^
                         999983    R/S            yields  999983=999983^1   ( in 42 seconds )         s0(999983) =      2        in registers X and R04
                                                            thus,   999983   is prime                                       phi(999983) = 999982  in registers Y and R06
 

Notes:

-If N is a prime, execution time is approximately    N1/2 / 25  seconds.
-The greatest prime < E10 is  9999999967  ( 1h06m with an HP-41CX )
-If you set flag F21, the program will stop at each AVIEW.
-s0(n) is the number of divisors of n.
-s1(n) is the sum of the divisors of n.
 

2°) Program#2  ( Divisor Functions only )
 

-"SKN" computes sk(n) and stores the result ( by groups of 5 digits ) in registers R09  R10 ......  from the right to the left.
-Unlike the previous program, k must be an integer greater than 1 and n can't exceed 100,000
 

Data Registers:   R00 = bbb.eee = control number of the result , R01 = n , R02 = k , R03 thru R08: temp
                              Rbb to Ree = the digits of sk(n)      Ree+1 to Ree+1+ee-bb: temp
Flags: /
Subroutines: /
 

  01  LBL "SKN"
  02  STO 01
  03  X<>Y
  04  STO 02
  05  Y^X
  06  LOG
  07   E5
  08  STO 08
  09  LOG
  10  /
  11  INT
  12  .1
  13  %
  14  9.009
  15  +
  16  STO 00
  17  CLRGX
  18  X<>Y
  19  1
  20  +
  21  1.001
  22  *
  23  +
  24  STO 03
  25  RCL 01
  26  SQRT
  27  INT
  28  STO 04
  29  LBL 01
  30  RCL 01
  31  RCL 04
  32  /
  33  FRC
  34  X#0?
  35  GTO 04
  36  LASTX
  37  STO 07
  38  XEQ 10
  39  RCL 07
  40  RCL 04
  41  STO 07
  42  X#Y?
  43  XEQ 10
  44  LBL 04
  45  DSE 04
  46  GTO 01
  47  RCL 00
  48  RTN
  49  LBL 10
  50  RCL 02
  51  STO 05
  52  RCL 03
  53  CLRGX
  54  RCL 07
  55  STO IND Y
  56  DSE 05
  57  LBL 02
  58  ST* IND Y
  59  ISG Y
  60  GTO 02
  61  RCL 03
  62  0
  63  LBL 09
  64  RCL IND Y
  65  +
  66  RCL X
  67  RCL 08
  68  MOD
  69  STO IND Z
  70  -
  71  RCL 08
  72  /
  73  ISG Y
  74  GTO 09
  75  RCL 03
  76  RCL 07
  77  DSE 05
  78  GTO 02
  79  RCL 00
  80  STO 05
  81  RCL 03
  82  STO 06
  83  CLX
  84  LBL 03
  85  RCL IND 05
  86  +
  87  RCL IND 06
  88  +
  89  STO Y
  90  RCL 08
  91  MOD
  92  STO IND 05
  93  -
  94  RCL 08
  95  /
  96  ISG 05
  97  ""                            TEXT 0  or another  NOP instruction like STO X
  98  ISG 06
  99  GTO 03
100  LASTX
101  *
102  DSE 05
103  ""                           TEXT 0  or another  NOP instruction like STO X
104  ST+ IND 05
105  END

( 153 bytes )
 
 
      STACK        INPUTS      OUTPUTS
           Y             k             /
           X             n        bbb.eee

 where  bbb.eee  =  control number of the result  ( in registers Rbb to Ree )

Example:           7      ENTER^
                     99999   XEQ "SKN"   >>>>  9.015  ( execution time = 7mn03s )

    we find   R09 = 61408 ,  R10 = 13064 , R11 = 95537 , R12 = 84451 , R13 = 30096 , R14 = 74265 , R15 = 100038

    whence   s7(99999)  = 100038,74265,30096,84451,95537,13064,61408

Notes:   -The last group of digits ( in register Ree ) may have more than 5 digits.
           -If you want to reverse the content of registers Rbb thru Ree, in order to get the groups of digits from the left to the right,
             add   XEQ "RVL"  RCL 00  after line 47  where "RVL" is the short routine listed below:
 

 01  LBL "RVL"
 02  ENTER^
 03  FRC
 04   E3
 05  *
 06  LBL 01
 07  RCL IND Y
 08  X<> IND Y
 09  STO IND Z
 10  RDN
 11  ISG Y
 12  DSE X
 13  X>Y?
 14  GTO 01
 15  END

( 30 bytes )
 

Reference:    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