[//000000001]: # (math::numtheory \- Tcl Math Library)
[//000000002]: # (Generated from file 'numtheory\.man' by tcllib/doctools with format 'markdown')
[//000000003]: # (Copyright © 2010 Lars Hellström <Lars dot Hellstrom at residenset dot net>)
[//000000004]: # (math::numtheory\(n\) 1\.1\.3 tcllib "Tcl Math Library")
<hr> [ <a href="../../../../toc.md">Main Table Of Contents</a> | <a
href="../../../toc.md">Table Of Contents</a> | <a
href="../../../../index.md">Keyword Index</a> | <a
href="../../../../toc0.md">Categories</a> | <a
href="../../../../toc1.md">Modules</a> | <a
href="../../../../toc2.md">Applications</a> ] <hr>
# NAME
math::numtheory \- Number Theory
# <a name='toc'></a>Table Of Contents
- [Table Of Contents](#toc)
- [Synopsis](#synopsis)
- [Description](#section1)
- [Bugs, Ideas, Feedback](#section2)
- [Keywords](#keywords)
- [Category](#category)
- [Copyright](#copyright)
# <a name='synopsis'></a>SYNOPSIS
package require Tcl ?8\.5?
package require math::numtheory ?1\.1\.3?
[__math::numtheory::isprime__ *N* ?*option* *value* \.\.\.?](#1)
[__math::numtheory::firstNprimes__ *N*](#2)
[__math::numtheory::primesLowerThan__ *N*](#3)
[__math::numtheory::primeFactors__ *N*](#4)
[__math::numtheory::primesLowerThan__ *N*](#5)
[__math::numtheory::primeFactors__ *N*](#6)
[__math::numtheory::uniquePrimeFactors__ *N*](#7)
[__math::numtheory::factors__ *N*](#8)
[__math::numtheory::totient__ *N*](#9)
[__math::numtheory::moebius__ *N*](#10)
[__math::numtheory::legendre__ *a* *p*](#11)
[__math::numtheory::jacobi__ *a* *b*](#12)
[__math::numtheory::gcd__ *m* *n*](#13)
[__math::numtheory::lcm__ *m* *n*](#14)
[__math::numtheory::numberPrimesGauss__ *N*](#15)
[__math::numtheory::numberPrimesLegendre__ *N*](#16)
[__math::numtheory::numberPrimesLegendreModified__ *N*](#17)
[__math::numtheory::differenceNumberPrimesLegendreModified__ *lower* *upper*](#18)
[__math::numtheory::listPrimePairs__ *lower* *upper* *step*](#19)
[__math::numtheory::listPrimeProgressions__ *lower* *upper* *step*](#20)
# <a name='description'></a>DESCRIPTION
This package is for collecting various number\-theoretic operations, with a
slight bias to prime numbers\.
- <a name='1'></a>__math::numtheory::isprime__ *N* ?*option* *value* \.\.\.?
The __isprime__ command tests whether the integer *N* is a prime,
returning a boolean true value for prime *N* and a boolean false value for
non\-prime *N*\. The formal definition of 'prime' used is the conventional,
that the number being tested is greater than 1 and only has trivial
divisors\.
To be precise, the return value is one of __0__ \(if *N* is definitely
not a prime\), __1__ \(if *N* is definitely a prime\), and __on__ \(if
*N* is probably prime\); the latter two are both boolean true values\. The
case that an integer may be classified as "probably prime" arises because
the Miller\-Rabin algorithm used in the test implementation is basically
probabilistic, and may if we are unlucky fail to detect that a number is in
fact composite\. Options may be used to select the risk of such "false
positives" in the test\. __1__ is returned for "small" *N* \(which
currently means *N* < 118670087467\), where it is known that no false
positives are possible\.
The only option currently defined is:
* __\-randommr__ *repetitions*
which controls how many times the Miller\-Rabin test should be repeated
with randomly chosen bases\. Each repetition reduces the probability of a
false positive by a factor at least 4\. The default for *repetitions*
is 4\.
Unknown options are silently ignored\.
- <a name='2'></a>__math::numtheory::firstNprimes__ *N*
Return the first N primes
* integer *N* \(in\)
Number of primes to return
- <a name='3'></a>__math::numtheory::primesLowerThan__ *N*
Return the prime numbers lower/equal to N
* integer *N* \(in\)
Maximum number to consider
- <a name='4'></a>__math::numtheory::primeFactors__ *N*
Return a list of the prime numbers in the number N
* integer *N* \(in\)
Number to be factorised
- <a name='5'></a>__math::numtheory::primesLowerThan__ *N*
Return the prime numbers lower/equal to N
* integer *N* \(in\)
Maximum number to consider
- <a name='6'></a>__math::numtheory::primeFactors__ *N*
Return a list of the prime numbers in the number N
* integer *N* \(in\)
Number to be factorised
- <a name='7'></a>__math::numtheory::uniquePrimeFactors__ *N*
Return a list of the *unique* prime numbers in the number N
* integer *N* \(in\)
Number to be factorised
- <a name='8'></a>__math::numtheory::factors__ *N*
Return a list of all *unique* factors in the number N, including 1 and N
itself
* integer *N* \(in\)
Number to be factorised
- <a name='9'></a>__math::numtheory::totient__ *N*
Evaluate the Euler totient function for the number N \(number of numbers
relatively prime to N\)
* integer *N* \(in\)
Number in question
- <a name='10'></a>__math::numtheory::moebius__ *N*
Evaluate the Moebius function for the number N
* integer *N* \(in\)
Number in question
- <a name='11'></a>__math::numtheory::legendre__ *a* *p*
Evaluate the Legendre symbol \(a/p\)
* integer *a* \(in\)
Upper number in the symbol
* integer *p* \(in\)
Lower number in the symbol \(must be non\-zero\)
- <a name='12'></a>__math::numtheory::jacobi__ *a* *b*
Evaluate the Jacobi symbol \(a/b\)
* integer *a* \(in\)
Upper number in the symbol
* integer *b* \(in\)
Lower number in the symbol \(must be odd\)
- <a name='13'></a>__math::numtheory::gcd__ *m* *n*
Return the greatest common divisor of *m* and *n*
* integer *m* \(in\)
First number
* integer *n* \(in\)
Second number
- <a name='14'></a>__math::numtheory::lcm__ *m* *n*
Return the lowest common multiple of *m* and *n*
* integer *m* \(in\)
First number
* integer *n* \(in\)
Second number
- <a name='15'></a>__math::numtheory::numberPrimesGauss__ *N*
Estimate the number of primes according the formula by Gauss\.
* integer *N* \(in\)
Number in question, should be larger than 0
- <a name='16'></a>__math::numtheory::numberPrimesLegendre__ *N*
Estimate the number of primes according the formula by Legendre\.
* integer *N* \(in\)
Number in question, should be larger than 0
- <a name='17'></a>__math::numtheory::numberPrimesLegendreModified__ *N*
Estimate the number of primes according the modified formula by Legendre\.
* integer *N* \(in\)
Number in question, should be larger than 0
- <a name='18'></a>__math::numtheory::differenceNumberPrimesLegendreModified__ *lower* *upper*
Estimate the number of primes between tow limits according the modified
formula by Legendre\.
* integer *lower* \(in\)
Lower limit for the primes, should be larger than 0
* integer *upper* \(in\)
Upper limit for the primes, should be larger than 0
- <a name='19'></a>__math::numtheory::listPrimePairs__ *lower* *upper* *step*
Return a list of pairs of primes each differing by the given step\.
* integer *lower* \(in\)
Lower limit for the primes, should be larger than 0
* integer *upper* \(in\)
Upper limit for the primes, should be larger than the lower limit
* integer *step* \(in\)
Step by which the primes should differ, defaults to 2
- <a name='20'></a>__math::numtheory::listPrimeProgressions__ *lower* *upper* *step*
Return a list of lists of primes each differing by the given step from the
previous one\.
* integer *lower* \(in\)
Lower limit for the primes, should be larger than 0
* integer *upper* \(in\)
Upper limit for the primes, should be larger than the lower limit
* integer *step* \(in\)
Step by which the primes should differ, defaults to 2
# <a name='section2'></a>Bugs, Ideas, Feedback
This document, and the package it describes, will undoubtedly contain bugs and
other problems\. Please report such in the category *math :: numtheory* of the
[Tcllib Trackers](http://core\.tcl\.tk/tcllib/reportlist)\. Please also report
any ideas for enhancements you may have for either package and/or documentation\.
When proposing code changes, please provide *unified diffs*, i\.e the output of
__diff \-u__\.
Note further that *attachments* are strongly preferred over inlined patches\.
Attachments can be made by going to the __Edit__ form of the ticket
immediately after its creation, and then using the left\-most button in the
secondary navigation bar\.
# <a name='keywords'></a>KEYWORDS
[number theory](\.\./\.\./\.\./\.\./index\.md\#number\_theory),
[prime](\.\./\.\./\.\./\.\./index\.md\#prime)
# <a name='category'></a>CATEGORY
Mathematics
# <a name='copyright'></a>COPYRIGHT
Copyright © 2010 Lars Hellström <Lars dot Hellstrom at residenset dot net>
