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.1?
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______________________________________________________________________________
52
54 This package is for collecting various number-theoretic operations,
55 with a slight bias to prime numbers.
56 math::numtheory::isprime N ?option value ...?
58 The isprime command tests whether the integer N is a prime, re‐
59 turning a boolean true value for prime N and a boolean false
60 value for non-prime N. The formal definition of ´prime' used is
61 the conventional, that the number being tested is greater than 1
62 and only has trivial divisors.
63 To be precise, the return value is one of 0 (if N is definitely
65 not a prime), 1 (if N is definitely a prime), and on (if N is
66 probably prime); the latter two are both boolean true values.
67 The case that an integer may be classified as "probably prime"
68 arises because the Miller-Rabin algorithm used in the test im‐
69 plementation is basically probabilistic, and may if we are un‐
70 lucky fail to detect that a number is in fact composite. Options
71 may be used to select the risk of such "false positives" in the
72 test. 1 is returned for "small" N (which currently means N <
73 118670087467), where it is known that no false positives are
74 possible.
75 The only option currently defined is:
77 -randommr repetitions
79 which controls how many times the Miller-Rabin test
80 should be repeated with randomly chosen bases. Each repe‐
81 tition reduces the probability of a false positive by a
82 factor at least 4. The default for repetitions is 4.
83 Unknown options are silently ignored.
85 math::numtheory::firstNprimes N
87 Return the first N primes
88 integer N (in)
90 Number of primes to return
91 math::numtheory::primesLowerThan N
93 Return the prime numbers lower/equal to N
94 integer N (in)
96 Maximum number to consider
97 math::numtheory::primeFactors N
99 Return a list of the prime numbers in the number N
100 integer N (in)
102 Number to be factorised
103 math::numtheory::primesLowerThan N
105 Return the prime numbers lower/equal to N
106 integer N (in)
108 Maximum number to consider
109 math::numtheory::primeFactors N
111 Return a list of the prime numbers in the number N
112 integer N (in)
114 Number to be factorised
115 math::numtheory::uniquePrimeFactors N
117 Return a list of the unique prime numbers in the number N
118 integer N (in)
120 Number to be factorised
121 math::numtheory::factors N
123 Return a list of all unique factors in the number N, including 1
124 and N itself
125 integer N (in)
127 Number to be factorised
128 math::numtheory::totient N
130 Evaluate the Euler totient function for the number N (number of
131 numbers relatively prime to N)
132 integer N (in)
134 Number in question
135 math::numtheory::moebius N
137 Evaluate the Moebius function for the number N
138 integer N (in)
140 Number in question
141 math::numtheory::legendre a p
143 Evaluate the Legendre symbol (a/p)
144 integer a (in)
146 Upper number in the symbol
147 integer p (in)
149 Lower number in the symbol (must be non-zero)
150 math::numtheory::jacobi a b
152 Evaluate the Jacobi symbol (a/b)
153 integer a (in)
155 Upper number in the symbol
156 integer b (in)
158 Lower number in the symbol (must be odd)
159 math::numtheory::gcd m n
161 Return the greatest common divisor of m and n
162 integer m (in)
164 First number
165 integer n (in)
167 Second number
168 math::numtheory::lcm m n
170 Return the lowest common multiple of m and n
171 integer m (in)
173 First number
174 integer n (in)
176 Second number
177 math::numtheory::numberPrimesGauss N
179 Estimate the number of primes according the formula by Gauss.
180 integer N (in)
182 Number in question, should be larger than 0
183 math::numtheory::numberPrimesLegendre N
185 Estimate the number of primes according the formula by Legendre.
186 integer N (in)
188 Number in question, should be larger than 0
189 math::numtheory::numberPrimesLegendreModified N
191 Estimate the number of primes according the modified formula by
192 Legendre.
193 integer N (in)
195 Number in question, should be larger than 0
196 math::numtheory::differenceNumberPrimesLegendreModified lower upper
198 Estimate the number of primes between tow limits according the
199 modified formula by Legendre.
200 integer lower (in)
202 Lower limit for the primes, should be larger than 0
203 integer upper (in)
205 Upper limit for the primes, should be larger than 0
206
208 This document, and the package it describes, will undoubtedly contain
209 bugs and other problems. Please report such in the category math ::
210 numtheory of the Tcllib Trackers [http://core.tcl.tk/tcllib/re‐
211 portlist]. Please also report any ideas for enhancements you may have
212 for either package and/or documentation.
213 When proposing code changes, please provide unified diffs, i.e the out‐
215 put of diff -u.
216 Note further that attachments are strongly preferred over inlined
218 patches. Attachments can be made by going to the Edit form of the
219 ticket immediately after its creation, and then using the left-most
220 button in the secondary navigation bar.
221
223 number theory, prime
224
226 Mathematics
227
229 Copyright (c) 2010 Lars Hellström <Lars dot Hellstrom at residenset dot net>
230tcllib 1.1.1 math::numtheory(n)