--- name: "numtheory" section: "3tcl" platform: "linux" package: "tcllib" version: "2.0+dfsg-4" release: "Debian 13 (Trixie)" platforms: ["linux"] url: "https://new.carta.tech/numtheory" --- # numtheory(3tcl) Number Theory ``` ``` ## NAME math::numtheory - Number Theory ## SYNOPSIS package require **Tcl ?8.5 9?** package require **math::numtheory ?1.1.4?** **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* ``` ``` ## 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::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, should be larger than 0 - **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 - **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 - **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 - **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 - **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 ## 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 ```