# number-theory

A number theory toolkit for JavaScript.

## Functions

### divisors(n)

Determines all of the divisors for a given number.

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

### factor(n)

Determines the prime factorization for a given integer. For more information see Wikipedia's Integer Factorization entry.

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

### gcd(a, b)

Finds the greatest common divisor of two integers a and b.

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

### inverseMod(a, m)

Given an integer this function computes the modular multiplicative inverse to the given modulo.

### isAbundant(n)

Given an integer, returns a Boolean indicating whether it's an abundant number.

### isDeficient(n)

Given an integer, returns a Boolean indicating whether it's a deficient number.

### isHeptagonal(n)

Given an integer, returns a Boolean indicating whether it's a heptagonal number.

### isHexagonal(n)

Given an integer, returns a Boolean indicating whether it's a hexagonal number.

### isOctagonal(n)

Given an integer, returns a Boolean indicating whether it's an octagonal number.

### isPentagonal(n)

Given an integer, returns a Boolean indicating whether it's a pentagonal number.

### isPerfect(n)

Given an integer, returns a Boolean indicating whether it's a perfect number.

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

### isSquare(n)

Given an integer, returns a Boolean indicating whether it's a square number.

### isTriangular(n)

Given an integer, returns a Boolean indicating whether it's a triangular number.

### jacobiSymbol(a, b)

Computes the Jacobi Symbol for the given numbers.

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

### multiplyMod(a, b, m)

Multiplies the two given numbers mod the given modulus. See Wikipedia's entry on Modular Arithmetic.

### powerMod(base, exponent, mod)

Computes the power of a base mod the given modulus. For more information see Wikipedia's entry on Modular Exponentiation.

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

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

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

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

### squareRootModPrime(n, p)

Uses the Tonelli–Shanks algorithm to determine a single square root in Z mod p.

## 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 the `index.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 its `lib/` 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!