number-theory
A number theory toolkit for JavaScript.
Functions
divisors(n)
Determines all of the divisors for a given number.
var divisors = divisors;; // Returns [1, 2, 3, 6]
eulerPhi(n), totient(n)
Counts the positive integers less than a given number that are co-prime with the given number. For more information see the Wikipedia entry for Euler's Totient Function.
var phi = eulerPhi;; // Returns 12
factor(n)
Determines the prime factorization for a given integer. For more information see Wikipedia's Integer Factorization entry.
var factor = factor; /* Returns: [ { prime: 2, power: 2 }, { prime: 3, power: 1 }, { prime: 11, power: 1 } ]*/;
findDivisor(n)
Uses the Pollard-Rho integer factorization algorithm to quickly find a small divisor of the given number. Note: the divisor found need not be prime (as Pollar-Rho is a general integer factorization algorithm).
var findDivisor = findDivisor;; // Returns 8
gcd(a, b)
Finds the greatest common divisor of two integers a and b.
var gcd = gcd;; // Returns 4
incMixed(tuple, bases)
Given a mixed-radix number and the bases for each digit, this determines the increment of the number. For more information, see Wikipedia's entry on Mixed Radix number systems.
var incMixed = incMixed; // A number representing a mixed-radix "clock" at 11:59 PMvar number = 59 59 23; // The bases for each of the mixed radix digits (60 seconds to a minute,// 60 minutes to an hour, 24 hours to a day).var base = 60 60 24; ; // Returns [0, 0, 0] (or midnight the next day)
inverseMod(a, m)
Given an integer this function computes the modular multiplicative inverse to the given modulo.
var inverseMod = inverseMod;; // Returns 11
isAbundant(n)
Given an integer, returns a Boolean indicating whether it's an abundant number.
var isAbundant = isAbundant;; // Returns true; // Returns false
isDeficient(n)
Given an integer, returns a Boolean indicating whether it's a deficient number.
var isDeficient = isDeficient;; // Returns true; // Returns false
isHeptagonal(n)
Given an integer, returns a Boolean indicating whether it's a heptagonal number.
var isHeptagonal = isHeptagonal;; // Returns true; // Returns false
isHexagonal(n)
Given an integer, returns a Boolean indicating whether it's a hexagonal number.
var isHexagonal = isHexagonal;; // Returns true; // Returns false
isOctagonal(n)
Given an integer, returns a Boolean indicating whether it's an octagonal number.
var isOctagonal = isOctagonal;; // Returns true; // Returns false
isPentagonal(n)
Given an integer, returns a Boolean indicating whether it's a pentagonal number.
var isPentagonal = isPentagonal;; // Returns true; // Returns false
isPerfect(n)
Given an integer, returns a Boolean indicating whether it's a perfect number.
var isPerfect = isPerfect;; // Returns true; // Returns false
isPrime(n)
Determines if the given number is prime.
Note: this is a particularly slow method that uses full prime factorization to
determine if the number is prime. For a faster method see the miller
function
below.
var isPrime = isPrime;; // Returns true; // Returns false
isSquare(n)
Given an integer, returns a Boolean indicating whether it's a square number.
var isSquare = isSquare;; // Returns true; // Returns false
isTriangular(n)
Given an integer, returns a Boolean indicating whether it's a triangular number.
var isTriangular = isTriangular;; // Returns true; // Returns false
jacobiSymbol(a, b)
Computes the Jacobi Symbol for the given numbers.
var jacobiSymbol = jacobiSymbol;; // returns 1
logMod(a, b, m)
Solves a discrete logarithm. For more information see the following:
miller(n), isProbablyPrime(n)
Uses the determinisic Miller-Rabin Primality Test to determine if the given number is prime. Works for all positive integers less than 341,550,071,728,321.
var miller = miller;; // Returns true; // Returns false
multiplyMod(a, b, m)
Multiplies the two given numbers mod the given modulus. See Wikipedia's entry on Modular Arithmetic.
var multiplyMod = multiplyMod;; // Returns 14
powerMod(base, exponent, mod)
Computes the power of a base mod the given modulus. For more information see Wikipedia's entry on Modular Exponentiation.
var powerMod = powerMod;; // Returns 299
primeFactors(n)
Computes a list of all prime factors for the given integer. Note: while this
method fully computes the prime factorization of the integer, it only returns
the primes and not the powers of the factorization. For full prime factorization
please use factor
.
var primeFactors = primeFactors;; // Returns [2, 3]
primitiveRoot(m)
Computes the smallest primitive root for Z mod n, meaning a multiplicative generator for the group of units of Z mod n. For more information see Wikipedia's entry on Primitive roots modulo n.
var primitiveRoot = primitiveRoot;; // Returns 7
quadraticNonresidue(p)
Computes a quadratic nonresidue for the given number. For more information see Wikipedia's entry for Quadratic Residues.
var quadraticNonresidue = quadraticNonresidue;; // Returns 5
randomPrimitiveRoot(m)
Find a random primitive root for Z mod n, meaning a multiplicative generator for the group of units of Z mod n. Unlike primitiveRoot, this function returns a random primitive root. For more information see Wikipedia's entry on Primitive roots modulo n.
sieve(n)
Determines a list of prime numbers up to the given bound by performing the Sieve of Eratosthenes.
var sieve = sieve;; // Returns [ 2, 3, 5, 7 ]
squareRootMod(n, m)
Determines all square roots of a given number modulo the given modulus. For more information see Wikipedia's entry on Quadratic Residues.
var squareRootMod = squareRootMod;; // Returns [76, 1]
squareRootModPrime(n, p)
Uses the Tonelli–Shanks algorithm to determine a single square root in Z mod p.
var squareRootModPrime = squareRootModPrime; // Returns 9
Contributing
Pull requests are very welcome! If you see a function we're missing, have an alternate algorithm implementation, or even want to add a special case function we'd be delighted to review your code.
Try to stick to the following guidelines, as they will help get the PR merged and published quickly:
- New functions should be added to their own file under the
lib/
directory - Make sure to add an entry in the
module.exports
for new functions in theindex.js
file. - Use two space characters per tab
- Please document your function using jsdoc
(see any function in
lib/
for an example on how to do this). - Write a test for your function and place it in the
tests/
folder with the same name that you gave for itslib/
counterpart. - Add an entry to the documentation in this file (
README.md
). Also please try to keep the function list alphabetized for quick reference.
Thanks!
License
MIT