math::numtheory(3tcl)

📦
version 2.0 · 3 versions
, in debian trixie, ubuntu questing, ubuntu resolute, ubuntu stonking

🎀 math::numtheory 🎀 — the Tcl Math Library's number theory era 💖

okay so bestie, welcome to math::numtheory(3tcl), a whole manual page from the Tcl Math Library that is literally all about number theory. it's giving math girlie, it's giving primes, it's giving "I know what a totient is and I'm not sorry." 🦋

✨ NAME ✨

math::numtheory — Number Theory. that's it, that's the name, and it ate. 👑

🌸 SYNOPSIS 🌸

the way that you load this whole situation is:

package require Tcl ?8.5 9?

package require math::numtheory ?1.1.4?

and then all the little commands you get to call, no cap:

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
yes primesLowerThan and primeFactors really do show up twice up there. that's not a typo on my end, that's just the page being the page. we respect it. 💅

💜 DESCRIPTION 💜

so this package exists to collect a bunch of number-theoretic operations, and ngl it has a slight bias toward prime numbers. it's a prime stan account. that's the vibe.

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

the isprime command tests whether the integer N is a prime, and it hands you back a boolean true value if N is prime and a boolean false value if it's not. the formal definition of "prime" it's using is the conventional one: the number being tested is greater than 1 and only has trivial divisors. classic. ✨

to be precise (and we ARE being precise), the return value is one of:

  • 0 — if N is definitely not a prime
  • 1 — if N is definitely a prime
  • on — if N is probably prime

the latter two are both boolean true values, so if you're just vibe-checking truthiness, you're fine. 💅

the whole "probably prime" situation exists because the Miller-Rabin algorithm used in the test implementation is basically probabilistic, and it may — if we are unlucky — fail to detect that a number is in fact composite. so that's a thing that can happen. 🙈

options let you pick how much risk of these "false positives" you want in the test. and for "small" N (which currently means N < 118670087467), it returns 1, because in that range it is known that no false positives are possible. slay. 🔥

the only option currently defined is:

  • -randommr repetitions — 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. no error, no drama, just vibes. 🫶

🌸 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

(yes bestie, again. it's in the original twice and I am nothing if not faithful. 😭)

🌸 math::numtheory::primeFactors N

return a list of the prime numbers in the number N.

  • integer N (in) — number to be factorised

(also again. iconic behaviour honestly.)

🌈 math::numtheory::uniquePrimeFactors N

return a list of the unique prime numbers in the number N. no duplicates, only main characters. 👑

  • 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. so like, the whole friend group.

  • integer N (in) — number to be factorised

🦋 math::numtheory::totient N

evaluate the Euler totient function for the number N (that's the number of numbers relatively prime to N). we love a function named after a person. periodt.

  • integer N (in) — number in question

🦋 math::numtheory::moebius N

evaluate the Moebius function for the number N. yes it's spelled Moebius here, that's the spelling, we're keeping it. 💅

  • 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)
p must be non-zero. that is not a suggestion. 🚨

⭐ 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)
b must be odd. odd only, bestie. ✨

💖 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. estimates are still valid, we don't gatekeep. 💅

  • 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. glow-up edition. ✨

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

heads up: "tow" is what the page says, and I am not here to fix it, I am here to report it. 😭
  • 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. twin primes, but make it configurable. 👯

  • 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. yes, a list of lists. nested. we're nesting, bestie. 🌈

  • 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 💀

okay so real talk, and I need you to hear me on this: this document, and the package it describes, will undoubtedly contain bugs and other problems. like, the page itself said it. that's just how it is. 😭

please report such in the category math :: numtheory of the Tcllib Trackers at http://core.tcl.tk/tcllib/reportlist.

also please report any ideas for enhancements you may have for either package and/or documentation. they want your ideas. they want them fr fr. 🫶

when proposing code changes, please provide unified diffs, i.e the output of diff -u.

and 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. that's the whole treasure map, go forth. 🗺️✨

👑 KEYWORDS 👑

number theory, prime

📚 CATEGORY 📚

Mathematics

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

okay bestie that's the whole page 💖 this came to you from tcllib, version 1.1.4, and it's the math::numtheory(3tcl) page — go forth and factorise responsibly. mwah. 🎀✨

📦 where this page comes from