1math::numtheory(n) Tcl Math Library math::numtheory(n)
2______________________________________________________________________________
6
8 math::numtheory - Number Theory
9
11 package require Tcl ?8.5?
12 package require math::numtheory ?1.1.3?
14 math::numtheory::isprime N ?option value ...?
16 math::numtheory::firstNprimes N
18 math::numtheory::primesLowerThan N
20 math::numtheory::primeFactors N
22 math::numtheory::primesLowerThan N
24 math::numtheory::primeFactors N
26 math::numtheory::uniquePrimeFactors N
28 math::numtheory::factors N
30 math::numtheory::totient N
32 math::numtheory::moebius N
34 math::numtheory::legendre a p
36 math::numtheory::jacobi a b
38 math::numtheory::gcd m n
40 math::numtheory::lcm m n
42 math::numtheory::numberPrimesGauss N
44 math::numtheory::numberPrimesLegendre N
46 math::numtheory::numberPrimesLegendreModified N
48 math::numtheory::differenceNumberPrimesLegendreModified lower upper
50 math::numtheory::listPrimePairs lower upper step
52 math::numtheory::listPrimeProgressions lower upper step
54______________________________________________________________________________
56
58 This package is for collecting various number-theoretic operations,
59 with a slight bias to prime numbers.
60 math::numtheory::isprime N ?option value ...?
62 The isprime command tests whether the integer N is a prime, re‐
63 turning a boolean true value for prime N and a boolean false
64 value for non-prime N. The formal definition of ´prime' used is
65 the conventional, that the number being tested is greater than 1
66 and only has trivial divisors.
67 To be precise, the return value is one of 0 (if N is definitely
69 not a prime), 1 (if N is definitely a prime), and on (if N is
70 probably prime); the latter two are both boolean true values.
71 The case that an integer may be classified as "probably prime"
72 arises because the Miller-Rabin algorithm used in the test im‐
73 plementation is basically probabilistic, and may if we are un‐
74 lucky fail to detect that a number is in fact composite. Options
75 may be used to select the risk of such "false positives" in the
76 test. 1 is returned for "small" N (which currently means N <
77 118670087467), where it is known that no false positives are
78 possible.
79 The only option currently defined is:
81 -randommr repetitions
83 which controls how many times the Miller-Rabin test
84 should be repeated with randomly chosen bases. Each repe‐
85 tition reduces the probability of a false positive by a
86 factor at least 4. The default for repetitions is 4.
87 Unknown options are silently ignored.
89 math::numtheory::firstNprimes N
91 Return the first N primes
92 integer N (in)
94 Number of primes to return
95 math::numtheory::primesLowerThan N
97 Return the prime numbers lower/equal to N
98 integer N (in)
100 Maximum number to consider
101 math::numtheory::primeFactors N
103 Return a list of the prime numbers in the number N
104 integer N (in)
106 Number to be factorised
107 math::numtheory::primesLowerThan N
109 Return the prime numbers lower/equal to N
110 integer N (in)
112 Maximum number to consider
113 math::numtheory::primeFactors N
115 Return a list of the prime numbers in the number N
116 integer N (in)
118 Number to be factorised
119 math::numtheory::uniquePrimeFactors N
121 Return a list of the unique prime numbers in the number N
122 integer N (in)
124 Number to be factorised
125 math::numtheory::factors N
127 Return a list of all unique factors in the number N, including 1
128 and N itself
129 integer N (in)
131 Number to be factorised
132 math::numtheory::totient N
134 Evaluate the Euler totient function for the number N (number of
135 numbers relatively prime to N)
136 integer N (in)
138 Number in question
139 math::numtheory::moebius N
141 Evaluate the Moebius function for the number N
142 integer N (in)
144 Number in question
145 math::numtheory::legendre a p
147 Evaluate the Legendre symbol (a/p)
148 integer a (in)
150 Upper number in the symbol
151 integer p (in)
153 Lower number in the symbol (must be non-zero)
154 math::numtheory::jacobi a b
156 Evaluate the Jacobi symbol (a/b)
157 integer a (in)
159 Upper number in the symbol
160 integer b (in)
162 Lower number in the symbol (must be odd)
163 math::numtheory::gcd m n
165 Return the greatest common divisor of m and n
166 integer m (in)
168 First number
169 integer n (in)
171 Second number
172 math::numtheory::lcm m n
174 Return the lowest common multiple of m and n
175 integer m (in)
177 First number
178 integer n (in)
180 Second number
181 math::numtheory::numberPrimesGauss N
183 Estimate the number of primes according the formula by Gauss.
184 integer N (in)
186 Number in question, should be larger than 0
187 math::numtheory::numberPrimesLegendre N
189 Estimate the number of primes according the formula by Legendre.
190 integer N (in)
192 Number in question, should be larger than 0
193 math::numtheory::numberPrimesLegendreModified N
195 Estimate the number of primes according the modified formula by
196 Legendre.
197 integer N (in)
199 Number in question, should be larger than 0
200 math::numtheory::differenceNumberPrimesLegendreModified lower upper
202 Estimate the number of primes between tow limits according the
203 modified formula by Legendre.
204 integer lower (in)
206 Lower limit for the primes, should be larger than 0
207 integer upper (in)
209 Upper limit for the primes, should be larger than 0
210 math::numtheory::listPrimePairs lower upper step
212 Return a list of pairs of primes each differing by the given
213 step.
214 integer lower (in)
216 Lower limit for the primes, should be larger than 0
217 integer upper (in)
219 Upper limit for the primes, should be larger than the
220 lower limit
221 integer step (in)
223 Step by which the primes should differ, defaults to 2
224 math::numtheory::listPrimeProgressions lower upper step
226 Return a list of lists of primes each differing by the given
227 step from the previous one.
228 integer lower (in)
230 Lower limit for the primes, should be larger than 0
231 integer upper (in)
233 Upper limit for the primes, should be larger than the
234 lower limit
235 integer step (in)
237 Step by which the primes should differ, defaults to 2
238
240 This document, and the package it describes, will undoubtedly contain
241 bugs and other problems. Please report such in the category math ::
242 numtheory of the Tcllib Trackers [http://core.tcl.tk/tcllib/re‐
243 portlist]. Please also report any ideas for enhancements you may have
244 for either package and/or documentation.
245 When proposing code changes, please provide unified diffs, i.e the out‐
247 put of diff -u.
248 Note further that attachments are strongly preferred over inlined
250 patches. Attachments can be made by going to the Edit form of the
251 ticket immediately after its creation, and then using the left-most
252 button in the secondary navigation bar.
253
255 number theory, prime
256
258 Mathematics
259
261 Copyright (c) 2010 Lars Hellström <Lars dot Hellstrom at residenset dot net>
262tcllib 1.1.3 math::numtheory(n)