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