Name

math::numtheory - Number Theory

Table Of Contents

• Table Of Contents
• Synopsis
• Description
• Bugs, Ideas, Feedback
• Keywords
• Category
• Copyright

Synopsis

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. Please also report any ideas for enhancements you may have for either package and/or documentation.

Keywords

number theory, prime

Category

Mathematics

Copyright

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