## table of contents

math::numtheory(3tcl) | Tcl Math Library | math::numtheory(3tcl) |

# NAME¶

math::numtheory - Number Theory# SYNOPSIS¶

package require**Tcl ?8.5?**

package require **math::numtheory ?1.0?**

**math::numtheory::isprime** *N* ?*option*
*value* ...?

**math::numtheory::firstNprimes** *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*

# DESCRIPTION¶

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:

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

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

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

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

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

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

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

**math::numtheory::uniquePrimeFactors***N*- Return a list of the
*unique*prime numbers in the number N

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

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

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

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

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

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

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

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

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

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

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

**math::numtheory::numberPrimesGauss***N*- Estimate the number of primes according the formula by Gauss.

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

**math::numtheory::numberPrimesLegendre***N*- Estimate the number of primes according the formula by Legendre.

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

**math::numtheory::numberPrimesLegendreModified***N*- Estimate the number of primes according the modified formula by Legendre.

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

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

# KEYWORDS¶

number theory, prime# CATEGORY¶

Mathematics# COPYRIGHT¶

Copyright (c) 2010 Lars Hellström <Lars dot Hellstrom at residenset dot net>

1.0 | tcllib |