1math::numtheory(n)             Tcl Math Library             math::numtheory(n)
2
3
4
5______________________________________________________________________________
6

NAME

8       math::numtheory - Number Theory
9

SYNOPSIS

11       package require Tcl  ?8.5?
12
13       package require math::numtheory  ?1.0?
14
15       math::numtheory::isprime N ?option value ...?
16
17       math::numtheory::firstNprimes N
18
19       math::numtheory::primesLowerThan N
20
21       math::numtheory::primeFactors N
22
23       math::numtheory::uniquePrimeFactors N
24
25       math::numtheory::factors N
26
27       math::numtheory::totient N
28
29       math::numtheory::moebius N
30
31       math::numtheory::legendre a p
32
33       math::numtheory::jacobi a b
34
35       math::numtheory::gcd m n
36
37       math::numtheory::lcm m n
38
39       math::numtheory::numberPrimesGauss N
40
41       math::numtheory::numberPrimesLegendre N
42
43       math::numtheory::numberPrimesLegendreModified N
44
45______________________________________________________________________________
46

DESCRIPTION

48       This  package  is  for  collecting various number-theoretic operations,
49       with a slight bias to prime numbers.
50
51       math::numtheory::isprime N ?option value ...?
52              The isprime command tests whether the  integer  N  is  a  prime,
53              returning  a  boolean true value for prime N and a boolean false
54              value for non-prime N. The formal definition of ´prime' used  is
55              the conventional, that the number being tested is greater than 1
56              and only has trivial divisors.
57
58              To be precise, the return value is one of 0 (if N is  definitely
59              not  a  prime),  1 (if N is definitely a prime), and on (if N is
60              probably prime); the latter two are both  boolean  true  values.
61              The  case  that an integer may be classified as "probably prime"
62              arises because the  Miller-Rabin  algorithm  used  in  the  test
63              implementation  is  basically  probabilistic,  and may if we are
64              unlucky fail to detect that  a  number  is  in  fact  composite.
65              Options may be used to select the risk of such "false positives"
66              in the test. 1 is returned for "small" N (which currently  means
67              N < 118670087467), where it is known that no false positives are
68              possible.
69
70              The only option currently defined is:
71
72              -randommr repetitions
73                     which controls  how  many  times  the  Miller-Rabin  test
74                     should be repeated with randomly chosen bases. Each repe‐
75                     tition reduces the probability of a false positive  by  a
76                     factor at least 4. The default for repetitions is 4.
77
78              Unknown options are silently ignored.
79
80       math::numtheory::firstNprimes N
81              Return the first N primes
82
83              integer N (in)
84                     Number of primes to return
85
86       math::numtheory::primesLowerThan N
87              Return the prime numbers lower/equal to N
88
89              integer N (in)
90                     Maximum number to consider
91
92       math::numtheory::primeFactors N
93              Return a list of the prime numbers in the number N
94
95              integer N (in)
96                     Number to be factorised
97
98       math::numtheory::uniquePrimeFactors N
99              Return a list of the unique prime numbers in the number N
100
101              integer N (in)
102                     Number to be factorised
103
104       math::numtheory::factors N
105              Return a list of all unique factors in the number N, including 1
106              and N itself
107
108              integer N (in)
109                     Number to be factorised
110
111       math::numtheory::totient N
112              Evaluate the Euler totient function for the number N (number  of
113              numbers relatively prime to N)
114
115              integer N (in)
116                     Number in question
117
118       math::numtheory::moebius N
119              Evaluate the Moebius function for the number N
120
121              integer N (in)
122                     Number in question
123
124       math::numtheory::legendre a p
125              Evaluate the Legendre symbol (a/p)
126
127              integer a (in)
128                     Upper number in the symbol
129
130              integer p (in)
131                     Lower number in the symbol (must be non-zero)
132
133       math::numtheory::jacobi a b
134              Evaluate the Jacobi symbol (a/b)
135
136              integer a (in)
137                     Upper number in the symbol
138
139              integer b (in)
140                     Lower number in the symbol (must be odd)
141
142       math::numtheory::gcd m n
143              Return the greatest common divisor of m and n
144
145              integer m (in)
146                     First number
147
148              integer n (in)
149                     Second number
150
151       math::numtheory::lcm m n
152              Return the lowest common multiple of m and n
153
154              integer m (in)
155                     First number
156
157              integer n (in)
158                     Second number
159
160       math::numtheory::numberPrimesGauss N
161              Estimate the number of primes according the formula by Gauss.
162
163              integer N (in)
164                     Number in question
165
166       math::numtheory::numberPrimesLegendre N
167              Estimate the number of primes according the formula by Legendre.
168
169              integer N (in)
170                     Number in question
171
172       math::numtheory::numberPrimesLegendreModified N
173              Estimate  the number of primes according the modified formula by
174              Legendre.
175
176              integer N (in)
177                     Number in question
178

BUGS, IDEAS, FEEDBACK

180       This document, and the package it describes, will  undoubtedly  contain
181       bugs  and  other  problems.  Please report such in the category math ::
182       numtheory          of           the           Tcllib           Trackers
183       [http://core.tcl.tk/tcllib/reportlist].   Please  also report any ideas
184       for enhancements you may have for either package and/or documentation.
185
186       When proposing code changes, please provide unified diffs, i.e the out‐
187       put of diff -u.
188
189       Note  further  that  attachments  are  strongly  preferred over inlined
190       patches. Attachments can be made by going  to  the  Edit  form  of  the
191       ticket  immediately  after  its  creation, and then using the left-most
192       button in the secondary navigation bar.
193

KEYWORDS

195       number theory, prime
196

CATEGORY

198       Mathematics
199
201       Copyright (c) 2010 Lars Hellström <Lars dot Hellstrom at residenset dot net>
202
203
204
205
206tcllib                                1.0                   math::numtheory(n)
Impressum