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.0?
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::uniquePrimeFactors N
24 math::numtheory::factors N
26 math::numtheory::totient N
28 math::numtheory::moebius N
30 math::numtheory::legendre a p
32 math::numtheory::jacobi a b
34 math::numtheory::gcd m n
36 math::numtheory::lcm m n
38 math::numtheory::numberPrimesGauss N
40 math::numtheory::numberPrimesLegendre N
42 math::numtheory::numberPrimesLegendreModified N
44______________________________________________________________________________
46
48 This package is for collecting various number-theoretic operations,
49 with a slight bias to prime numbers.
50 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 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 The only option currently defined is:
71 -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 Unknown options are silently ignored.
79 math::numtheory::firstNprimes N
81 Return the first N primes
82 integer N (in)
84 Number of primes to return
85 math::numtheory::primesLowerThan N
87 Return the prime numbers lower/equal to N
88 integer N (in)
90 Maximum number to consider
91 math::numtheory::primeFactors N
93 Return a list of the prime numbers in the number N
94 integer N (in)
96 Number to be factorised
97 math::numtheory::uniquePrimeFactors N
99 Return a list of the unique prime numbers in the number N
100 integer N (in)
102 Number to be factorised
103 math::numtheory::factors N
105 Return a list of all unique factors in the number N, including 1
106 and N itself
107 integer N (in)
109 Number to be factorised
110 math::numtheory::totient N
112 Evaluate the Euler totient function for the number N (number of
113 numbers relatively prime to N)
114 integer N (in)
116 Number in question
117 math::numtheory::moebius N
119 Evaluate the Moebius function for the number N
120 integer N (in)
122 Number in question
123 math::numtheory::legendre a p
125 Evaluate the Legendre symbol (a/p)
126 integer a (in)
128 Upper number in the symbol
129 integer p (in)
131 Lower number in the symbol (must be non-zero)
132 math::numtheory::jacobi a b
134 Evaluate the Jacobi symbol (a/b)
135 integer a (in)
137 Upper number in the symbol
138 integer b (in)
140 Lower number in the symbol (must be odd)
141 math::numtheory::gcd m n
143 Return the greatest common divisor of m and n
144 integer m (in)
146 First number
147 integer n (in)
149 Second number
150 math::numtheory::lcm m n
152 Return the lowest common multiple of m and n
153 integer m (in)
155 First number
156 integer n (in)
158 Second number
159 math::numtheory::numberPrimesGauss N
161 Estimate the number of primes according the formula by Gauss.
162 integer N (in)
164 Number in question
165 math::numtheory::numberPrimesLegendre N
167 Estimate the number of primes according the formula by Legendre.
168 integer N (in)
170 Number in question
171 math::numtheory::numberPrimesLegendreModified N
173 Estimate the number of primes according the modified formula by
174 Legendre.
175 integer N (in)
177 Number in question
178
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 When proposing code changes, please provide unified diffs, i.e the out‐
187 put of diff -u.
188 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
195 number theory, prime
196
198 Mathematics
199
201 Copyright (c) 2010 Lars Hellström <Lars dot Hellstrom at residenset dot net>
202tcllib 1.0 math::numtheory(n)