[ Tcllib Home | Main Table Of Contents | Table Of Contents | Keyword Index | Categories | Modules | Applications ]

math::numtheory - Number Theory

- package require
**Tcl ?8.5?** - package require
**math::numtheory ?1.1.3?**

**math::numtheory::isprime***N*?*option**value*...?**math::numtheory::firstNprimes***N***math::numtheory::primesLowerThan***N***math::numtheory::primeFactors***N***math::numtheory::primesLowerThan***N***math::numtheory::primeFactors***N***math::numtheory::uniquePrimeFactors***N***math::numtheory::factors***N***math::numtheory::totient***N***math::numtheory::moebius***N***math::numtheory::legendre***a**p***math::numtheory::jacobi***a**b***math::numtheory::gcd***m**n***math::numtheory::lcm***m**n***math::numtheory::numberPrimesGauss***N***math::numtheory::numberPrimesLegendre***N***math::numtheory::numberPrimesLegendreModified***N***math::numtheory::differenceNumberPrimesLegendreModified***lower**upper***math::numtheory::listPrimePairs***lower**upper**step***math::numtheory::listPrimeProgressions***lower**upper**step*

This package is for collecting various number-theoretic operations, with a slight bias to prime numbers.

**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:

Unknown options are silently ignored.

**math::numtheory::firstNprimes***N*-
Return the first N primes

- integer
*N*(in) -
Number of primes to return

- integer
**math::numtheory::primesLowerThan***N*-
Return the prime numbers lower/equal to N

- integer
*N*(in) -
Maximum number to consider

- integer
**math::numtheory::primeFactors***N*-
Return a list of the prime numbers in the number N

- integer
*N*(in) -
Number to be factorised

- integer
**math::numtheory::primesLowerThan***N*-
Return the prime numbers lower/equal to N

- integer
*N*(in) -
Maximum number to consider

- integer
**math::numtheory::primeFactors***N*-
Return a list of the prime numbers in the number N

- integer
*N*(in) -
Number to be factorised

- integer
**math::numtheory::uniquePrimeFactors***N*-
Return a list of the

*unique*prime numbers in the number N- integer
*N*(in) -
Number to be factorised

- integer
**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

- integer
**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

- integer
**math::numtheory::moebius***N*-
Evaluate the Moebius function for the number N

- integer
*N*(in) -
Number in question

- integer
**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)

- integer
**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)

- integer
**math::numtheory::gcd***m**n*-
Return the greatest common divisor of

*m*and*n*- integer
*m*(in) -
First number

- integer
*n*(in) -
Second number

- integer
**math::numtheory::lcm***m**n*-
Return the lowest common multiple of

*m*and*n*- integer
*m*(in) -
First number

- integer
*n*(in) -
Second number

- integer
**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

- integer
**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

- integer
**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

- integer
**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

- integer
**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

- integer
**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

- integer

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. 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.

Mathematics

Copyright © 2010 Lars Hellström <Lars dot Hellstrom at residenset dot net>