HP Forums
(35S) Number Theory Library - Printable Version

+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: General Software Library (/forum-13.html)
+--- Thread: (35S) Number Theory Library (/thread-4236.html)

(35S) Number Theory Library - Gerald H - 06-26-2015 02:58 PM

Edit 2015-12-14: Changed line 343 of programme.
Edit: Corrected description of PPT.

A suite of number theory programmes - I've tried to include everything I find essential.

If you think something is missing please make suggestions.

Improvements very welcome.

Entry points:

ADD MOD 511
A, B, MOD -> A+B mod MOD

SUB MOD 519
A, B, MOD -> A-B mod MOD

MULT MOD 525
A, B, MOD -> A*B mod MOD

DIV MOD 528
A, B, MOD -> A/B mod MOD

BEZO 208
A, B -> gcd(A,B), C, D where A*C+B*D=gcd((A,B)

FIBO 849
A -> FNUMBER

CRT 600
A, B, C, D -> E, B*D where E satisfies E mod B=A & E mod D=C, B & D co-prime.

PRIME? 148
A -> 0 OR 1 as A is composite or probably prime.

CORNACCHIA 531
A, PRIME -> [B,C] such that B^2+A*C^2=PRIME or 0 if there is no solution.

NEXT CORN 768
E, PRIME -> [B,C], A, B & C as above, A the smallest integer > E so above equation has a solution.

√MOD 420
A, B -> C, C=√A modulo B or 0 if no solution.

PELL 621
A, 1 or 0 -> [B,C,1 or -1] or 0.
For input A, 1 the B & C satisfy B^2-A*C^2=1;
for input A, 0 the B & C satisfy B^2-A*C^2=-1 & if no solution 0 is returned.

PWR MOD 035
A, B, MOD -> A^B mod MOD

INV MOD 237
A, MOD -> A^-1 mod MOD or 0 if no solution.

NEXT PRIME 161
A -> nextprime(A) if A positive, prevprime(A) if A negative.

PPT 301
A -> prime or 0 as A is a prime power or not.

#PQARTS 665
A, 0 or 1 -> B, for 0 B is number of integer partitions, for 1 the number of integer partitions in distinct parts.

KRONECKER 340
A, B -> 1 or -1 or 0, Kron(A/B)

RABIN? 571
A, B -> 0 or 1, 1 if A is a strong pseudo-prime base B, 0 if not.

SPLIT 565
COMPOSITE -> FACTOR

MODF CORNA 780
A, PRIME -> [B,C] such that B^2+A*C^2=4*PRIME or 0 if there is no solution.

NEXT M CORN 829
E, PRIME -> [B,C], A, B & C as above, A the smallest integer > E so above equation has a solution.

PFOR 575
A -> B, B an A-digit prime.

COMP# 581
A -> B*C, B & C are A-digit primes.

ALL FACS 590
COMPOSITE -> A, B where COMPOSITE= A*B. Pressing R/S then factorises A etc until 1 appears.

RANDOM# 000
No input, produces a random integer.
Code:

1    LBL Z
2    12
3    10^x
4    RANDOM
5    *
6    IP
7    RTN
8    REGX
9    1,000,000
10    RMDR
11    STO Z
12    -
13    ENTER
14    x^2
15    RCL B
16    RMDR
17    x<>y
18    RCL*Z
19    RCL A
20    RMDR
21    ENTER
22    RCL- A
23    +
24    RCL A
25    RMDR
26    +
27    RCL B
28    RMDR
29    RCL Z
30    x^2
31    +
32    RCL A
33    RMDR
34    RTN
35    XEQ Z506
36    R↓
37    STO M
38    R↓
39    STO N
40    1►R
41    RCL M
42    x≠0?
43    GTO Z047
44    RCL R
45    RTN
46    RCL M
47    2
48    RMDR
49    x≠0?
50    GTO Z057
51    2
52    STO/ M
53    RCL N
54    XEQ Z008
55    STO N
56    GTO Z046
57    STO- M
58    RCL N
59    XEQ Z264
60    GTO Z041
61    XEQ Z506
62    -1►I
63    +
64    0
65    CLx
66    2
67    /
68    ISG I
69    IP
70    REGX
71    2
72    RMDR
73    x=0?
74    GTO Z065
75    R↓
76    STO P
77    RTN
78    RCL P
79    XEQ Z037
80    1
81    x=y?
82    RTN
83    +/-
84    RCL+ A
85    x=y?
86    RTN
87    CLx
88    RCL I
89    x=0?
90    RTN
91    CLx
92    A-1
93    x<>y
94    XEQ Z008
95    x=y?
96    RTN
97    REGX-1
98    x=0?
99    RTN
100    R↓
101    DSE I
102    GTO Z094
103    0
104    RTN
105    XEQ Z062
106    A-3
107    XEQ Z004
108    2
109    +
110    XEQ Z078
111    SGN
112    RCL A
113    x<>y
114    RTN
115    XEQ Z506
116    4
117    x>y?
118    RTN
119    CLx
120    2
121    RMDR
122    x=0?
123    RTN
124    SQRT(A)
125    FP
126    x=0?
127    RTN
128    LASTx
129    IP
130    199
131    x>y?
132    x<>y
133    1000
134    /
135    3.00002
136    +
137    STO I
138    RCL A
139    RCL I
140    IP
141    RMDR
142    x=0?
143    RTN
144    ISG I
145    GTO Z138
146    1►C
147    RTN
148    ABS
149    XEQ Z115
150    RCL A
151    x<>y
152    x=0?
153    RTN
154    CLx
155    47053
156    x<>y
157    x>=y?
158    GTO Z105
159    1
160    RTN
161    IP
162    RMDR(REGX,2)+REGX-1►T
163    2+T►T
164    XEQ Z148
165    x=0?
166    GTO Z163
167    R↓
168    RTN
169    RMDR
170    LASTx
171    x<>y
172    x≠0?
173    GTO Z169
174    R↓
175    ABS
176    RTN
177    CLx
178    RCL A
179    x<>y
180    x≠y?
181    RTN
182    C+1►C
183    1►U►V
184    IP(RAND*A)
185    STO X
186    XEQ Z008
187    RCL+ C
188    ENTER
189    RCL- X
190    RCL A
191    XEQ Z169
192    1
193    x≠y?
194    GTO Z177
195    R↓
196    R↓
197    DSE U
198    GTO Z186
199    2*V►V►U
200    R↓
201    XEQ Z008
202    RCL+ C
203    DSE U
204    GTO Z201
205    V►U
206    R↓
207    GTO Z185
208    STO G
209    1►E►F-1►C►D
210    R↓
211    REGY
212    REGY
213    INT/
214    +/-
215    ENTER
216    RCL* D
217    RCL+ E
218    x<> D
219    STO E
220    R↓
221    ENTER
222    RCL* F
223    RCL+ C
224    x<> F
225    STO C
226    R↓
227    REGY
228    *
229    REGZ
230    +
231    x≠0?
232    GTO Z211
233    R↓
234    RCL E
235    RCL C
236    RTN
237    XEQ Z208
238    R↓
239    REGY
240    *
241    REGY
242    ABS
243    1
244    -
245    x≠0?
246    GTO Z251
247    REGY
248    RCL G
249    RMDR
250    RTN
251    CLx
252    RTN
253    STO N
254    x<>y
255    STO R
256    R↓
257    RCL A
258    XEQ Z237
259    x=0?
260    RTN
261    RCL R
262    STO R
263    x<>y
264    REGX
265    1,000,000
266    RMDR
267    STO C
268    -
269    STO D
270    RCL R
271    REGX
272    1,000,000
273    RMDR
274    STO Z
275    -
276    STO Y
277    RCL* D
278    RCL B
279    RMDR
280    RCL Y
281    RCL* C
282    RCL A
283    RMDR
284    +
285    RCL B
286    RMDR
287    RCL D
288    RCL* Z
289    RCL A
290    RMDR
291    +
292    RCL B
293    RMDR
294    RCL Z
295    RCL* C
296    +
297    RCL A
298    RMDR
299    STO R
300    RTN
301    STO F
302    STO H
303    SGN
304    STO E
305    RCL F
306    STO G
307    SGN
308    STO+ E
309    RCL E
310    RCL F
311    ENTER
312    XEQ Z035
313    RCL- E
314    RCL F
315    XEQ Z169
316    STO F
317    1
318    -
319    x=0?
320    GTO Z338
321    RCL F
322    XEQ Z148
323    x=0?
324    GTO Z305
325    R↓
326    RCL G
327    ENTER
328    R↓
329    REGY
330    /
331    1
332    x<y?
333    GTO Z328
334    x≠y?
335    CLx
336    REGX*REGZ
337    RCL H
338    x<>y
339    RTN
340    STO E
341    x<>y
342    STO C
343    2*(1►D)
344    RMDR
345    x<>y
346    x=0?
347    GTO Z414
348    LASTx
349    RMDR
350    +
351    x=0?
352    RTN
353    SGN
354    STO D
355    XEQ Z389
356    RCL C
357    x<> E
358    STO C
359    x>=0?
360    GTO Z367
361    ABS
362    STO C
363    RCL E
364    SGN
365    x<0?
366    STO* D
367    RCL E
368    x=0?
369    GTO Z414
370    XEQ Z389
371    RCL E
372    4
373    RMDR
374    RCL C
375    LASTx
376    RMDR
377    *
378    9
379    x=y?
380    -D►D
381    RCL E
382    ABS
383    ENTER
384    x<> C
385    x<>y
386    RMDR
387    STO E
388    GTO Z368
389    0
390    RCL E
391    2
392    RMDR
393    x≠0?
394    GTO Z400
395    2
396    STO/ E
397    REGZ
398    NOT
399    GTO Z390
400    R↓
401    x=0?
402    RTN
403    RCL C
404    8
405    RMDR
406    4
407    -
408    ABS
409    1
410    x=y?
411    +/-
412    STO* D
413    RTN
414    ABS(C)
415    1
416    x≠y?
417    CLx
418    RCL* D
419    RTN
420    XEQ Z506
421    RMDR
422    SQRT(REGX)
423    FP
424    x≠0?
425    GTO Z428
426    LASTx
427    RTN
428    x<>y
429    STO F
430    RCL A
431    XEQ Z340
432    0
433    x≥y?
434    RTN
435    RMDR(A,4)-(1►I)
436    x=0?
437    GTO Z441
438    RCL F
439    (A+1)/4
440    GTO Z037
441    CLx
442    STO G
443    A-1
444    REGX
445    2
446    RMDR
447    x≠0?
448    GTO Z456
449    R↓
450    LASTx
451    /
452    1
453    STO+ G
454    R↓
455    GTO Z444
456    R↓
457    STO H
458    1+I►I
459    RCL A
460    XEQ Z340
461    x>0?
462    GTO Z458
463    RCL I
464    RCL H
465    XEQ Z037
466    STO J
467    G►I
468    RCL F
469    (H-1)/2
470    XEQ Z037
471    STO E
472    RCL F
473    XEQ Z262
474    ENTER
475    x<> E
476    XEQ Z262
477    STO F
478    1
479    x=y?
480    GTO Z504
481    STO G
482    R↓
483    XEQ Z008
484    1
485    x=y?
486    GTO Z490
487    STO+ G
488    R↓
489    GTO Z483
490    RCL J
491    2^(I-G-1)
492    XEQ Z037
493    XEQ Z008
494    STO J
495    G►I
496    RCL E
497    RCL R
498    XEQ Z262
499    STO E
500    RCL F
501    RCL J
502    XEQ Z262
503    GTO Z477
504    RCL E
505    RTN
506    +/-
507    STO B
508    +/-
509    STO A
510    RTN
511    XEQ Z506
512    R↓
513    RCL B
514    RMDR
515    +
516    RCL A
517    RMDR
518    RTN
519    XEQ Z506
520    R↓
521    -
522    RCL A
523    RMDR
524    RTN
525    XEQ Z506
526    R↓
527    GTO Z262
528    XEQ Z506
529    R↓
530    GTO Z253
531    XEQ Z506
532    √x
533    IP
534    STO K
535    R↓
536    STO L
537    +/-
538    RCL A
539    XEQ Z421
540    x=0?
541    RTN
542    RCL A
543    x<>y
544    REGY-REGX
545    x>y?
546    x<>y
547    R↓
548    RCL K
549    x>=y?
550    GTO Z556
551    R↓
552    x<>y
553    REGY
554    RMDR
555    GTO Z548
556    R↓
557    SQRT((A-SQ(REGX))/L)
558    FP
559    x≠0?
560    GTO Z563
561    [REGY,LASTx]
562    RTN
563    CLx
564    RTN
565    XEQ Z115
566    x≠0?
567    GTO Z183
568    RCL A
569    LASTx
570    RTN
571    x<>y
572    XEQ Z061
573    x<>y
574    GTO Z110
575    XEQ Z003
576    999,999,999,989
577    x<=y?
578    RTN
579    R↓
580    GTO Z162   (corrected, was erroneously Z163, 2018-03-02)
581    6
582    x>y?
583    x<>y
584    STO G
585    XEQ Z575
586    x<> G
587    XEQ Z575
588    RCL* G
589    RTN
590    XEQ Z148
591    x≠0?
592    RTN
593    R↓
594    XEQ Z565
595    /
596    LASTx
597    STOP
598    R↓
599    GTO Z590
600    STO O
601    R↓
602    STO N
603    R↓
604    STO M
605    R↓
606    STO L
607    CLx
608    RCL M
609    XEQ Z208
610    RCL* N
611    RCL* M
612    x<>y
613    RCL* L
614    RCL* O
615    +
616    RCL M
617    RCL* O
618    RMDR
619    LASTx
620    RTN
621    STO K
622    1►F
623    (REGZ►A-SQ(IP(SQRT(A))►B►D►H))►I
624    x=0?
625    RTN
626    IDIV(2*B,I)►C►G*B+1►E
627    RCL I
628    1
629    x≠y?
630    GTO Z637
631    RCL K
632    x>0?
633    GTO Z662
634    RCL A
635    [D,F,-1]
636    RTN
637    0►J
638    NOT(J)►J
639    IP((A-SQ((C*I-H)►H))/I)►I
640    1
641    x≠y?
642    GTO Z655
643    RCL K
644    x<0?
645    GTO Z650
646    RCL J
647    x≠0?
648    GTO Z662
649    GTO Z655
650    RCL J
651    x=0?
652    GTO Z662
653    0
654    RTN
655    IDIV(B+H,I)►C*E+D
656    x<>E
657    STO D
658    C*G+F
659    x<>G
660    STO F
661    GTO Z638
662    RCL A
663    [E,G,K]
664    RTN
665    x≠0?
666    GTO Z669
667    CF 0
668    GTO Z670
669    SF 0
670    RAD
671    2*REGY►K/2
672    24
673    1/x
674    FS? 0
675    +/-
676    -
677    STO G
678    FS? 0
679    GTO Z681
680    π*√(2/3)/G►I*(G^1.5►J) ►H
681    CLx
682    STO B
683    1►C
684     C►D
685    CLx
686    STO E
687    RCL C
688    RCL D
689    RMDR
690    LASTx
691    x<>y
692    x≠0?
693    GTO Z689
694    1
695    +
696    x≠y?
697    GTO Z721
698    +/-
699    RCL+ C
700    x=0?
701    GTO Z713
702    STO F
703    0
704    F/C
705    FP(REGX*D)-0.5
706    x<>y
707    0.5
708    -
709    *
710    +
711    DSE F
712    GTO Z704
713    0.25
714    +
715    K*D/C
716    -
717    π
718    *
719    COS
720    STO+ E
721    DSE D
722    GTO Z687
723    FS? 0
724    GTO Z737
725    EXP(H/C)
726    ENTER
727    1/x
728    (REGY+REGX)*I/C
729    (REGZ-REGY)/J
730    -
731    C+1►C-1
732    √x
733    *
734    π
735    4
736    GTO Z761
737    SQ(π/C)►L*G/12►D
738    SGN
739    ENTER
740    STO F
741    ENTER
742    R↓
743    x<> y
744    RCL* D
745    RCL/ F
746    RCL F
747    1
748    +
749    STO F
750    /
751    +
752    LASTx
753    x<>y
754    REGZ
755    x≠y?
756    GTO Z742
757    RCL* L
758    2
759    STO+ C
760    6
761    *
762    /
763    IP(REGX*E+B►B+0.5)
764    IP(REGY+B+0.5)
765    x≠y?
766    GTO Z684
767    RTN
768    XEQ Z506
769    R↓
770    STO U
771    RMDR(1+U,A)►U
772    RCL A
773    XEQ Z532
774    ABS
775    x=0?
776    GTO Z771
777    LASTx
778    RCL U
779    RTN
780    XEQ Z506
781    x<>y
782    +/-
783    x<>y
784    2
785    x≠y
786    GTO Z793
787    √(8+REGZ)
788    FP
789    x≠0?
790    GTO Z827
791    [LASTx,1]
792    RTN
793    R↓
794    x<>y
795    STO K
796    x<>y
797    XEQ Z421
798    x=0?
799    RTN
800    RMDR(REGX+K,2)
801    x=0?
802    GTO Z808
803    R↓
804    RCL A
805    x<>y
806    -
807    GTO Z809
808    R↓
809    2*A
810    x<>y
811    IP(2*SQRT(A))
812    x≥y?
813    GTO Z820
814    R↓
815    RMDR
816    LASTx
817    x<>y
818    R↑
819    GTO Z812
820    R↓
821    SQRT(ABS((4*A-SQ(REGX))/K))
822    FP
823    x≠0?
824    GTO Z827
825    [REGY,LASTx]
826    RTN
827    0
828    RTN
829    XEQ Z506
830    R↓
831    STO L
832    3-RMDR(L,4)
833    1
834    x<y?
835    x<>y
836    RCL+ L
837    4
838    RCL* A
839    RMDR
840    STO L
841    RCL A
842    XEQ Z781
843    ABS
844    x=0?
845    GTO Z832
846    LASTx
847    RCL L
848    RTN
849    IP(((1+√5)/2)^REGX/√5+.4)-IDIV(REGX,56)-2*(IDIV(REGX,58)+ IDIV(REGX,59))
850    RTN


RE: (35S) Number Theory Library - Gerald H - 03-02-2018 10:37 AM

Update: Error in PFOR entry corrected, line Z580.

RE: (35S) Number Theory Library - fred_76 - 02-13-2019 04:41 PM

Sorry for my noob question.

Problem : in line 92, what is "A-1" ? How do you get this ?

I can't find it on the manual...

RE: (35S) Number Theory Library - Gerald H - 02-15-2019 05:34 AM

Line 92 puts the value of variable "A" on the stack at level X & subtracts 1 from stack level X.

Enter the expression with keystrokes

EQN RCL A - 1 ENTER

RE: (35S) Number Theory Library - Dieter - 02-16-2019 05:05 PM

(02-15-2019 05:34 AM)Gerald H Wrote:  Line 92 puts the value of variable "A" on the stack at level X & subtracts 1 from stack level X.

That's not quite right. First the expression is evaluated as a whole, then the result is moved to X (and the stack is pushed). So the equation first calculates A–1 and then it returns this value to the stack. The variable A alone is never moved to X. During the calculation the whole stack is not affected.

BTW, is there a special reason why the program uses so many equations? For instance what's the advantage of "-1►R" instead of -1 STO R, or "SQRT A" instead of RCL A √x? Especially as equations are rather slow.

Dieter

RE: (35S) Number Theory Library - Gerald H - 02-16-2019 06:49 PM

Thank you Dieter for correcting me.

Reason for using equations is to save lines, the published programme has 850, which still leaves a little room for development.

Further, some stack manipulations are more elegantly managed in an equation & the stack commands are not as inclusive as on the 42S.

RE: (35S) Number Theory Library - Gerald H - 02-17-2019 05:51 AM

The programme library has now been discussed here

http://www.hpmuseum.org/forum/thread-12406.html

Well worth reading, particulary for statistics concerning reliability of PRIME? calculation.