FactorInteger

The prime factorisation of n as a list of [prime, exponent] pairs.

✓ checked against that system · ! checked, with disagreements (hover a chip)WikipediaInteger factorization↗MathWorldPrimeFactorization↗WikidataQ4846249↗Wolfram LanguageFactorInteger!↗Rosetta CodePrime decomposition↗

FactorInteger(n)prime factorization of $n$ as $[\mathrm{prime}, \mathrm{exponent}]$ pairs.

SageMathenumeratio_factor_integer(n)SymPylist(factorrat(S(n)).items())Juliaenumeratio_factor_integer(n)Rustfactor_integer(n)

FactorInteger(n, Over -> GaussianIntegers)the factorisation in $\mathbb{Z}[i]$: a unit first when it is not 1, then first-quadrant primes; a complex $n$ is always factored there

FactorInteger(n, Over -> QuadraticIntegers(d))the prime factorisation of $n$ in the ring of integers of $\mathbb{Q}(\sqrt d)$, where that ring factors uniquely

SageMathenumeratio_factor_integer(d)SymPylist(factorrat(S(d)).items())Juliaenumeratio_factor_integer(d)Rustfactor_integer(d)

Typed signatures

Type	Package	Applies
(integer) -> list<tuple<integer, integer>>	compute-engine	always
(number | quadratic_integer, any*) -> list	number-theoryreplaces compute-engine	always

Domain: Number theory

Details

• For $n=p_1^{k_1}\cdots p_m^{k_m}$, returns the pairs $\{p_1,k_1\},\ldots,\{p_m,k_m\}$ in increasing order of prime.
• Multiplying the $p^e$ factors back together recovers $n$.
• compute-engine represents 1 as $1^1$ and 0 as $0^1$.
• Negative $n$ carries an explicit $-1^1$ unit factor ahead of the prime factors.
• compute-engine handles ordinary integers only.

Examples

28 more kept as data, checked against the oracles

Basic #

live ↗

In$\mathrm{FactorInteger}(360)$Out$\bigl\lbrack(2,3), (3,2), (5,1)\bigr\rbrack$

live ↗

In$\mathrm{FactorInteger}(84)$Out$\bigl\lbrack(2,2), (3,1), (7,1)\bigr\rbrack$

live ↗

In$\mathrm{FactorInteger}(120)$Out$\bigl\lbrack(2,3), (3,1), (5,1)\bigr\rbrack$

live ↗

In$\mathrm{FactorInteger}(36)$Out$\bigl\lbrack(2,2), (3,2)\bigr\rbrack$

Scope #

Threads element-wise over a list, as Wolfram's Listable heads do

live ↗

In$\mathrm{FactorInteger}(\bigl\lbrack12, 18\bigr\rbrack)$Out$\bigl\lbrack\bigl\lbrack(2,2), (3,1)\bigr\rbrack, \bigl\lbrack(2,1), (3,2)\bigr\rbrack\bigr\rbrack$

$5 = -i(1 + 2i)(2 + i)$

live ↗

In$\mathrm{FactorInteger}(5, \mathrm{Rule}(\mathrm{Over}, \mathrm{GaussianIntegers}))$Out$\bigl\lbrack(-i,1), (1+2i,1), (2+i,1)\bigr\rbrack$

$3 + 4i = (2 + i)^2$

live ↗

In$\mathrm{FactorInteger}(3+4i)$Out$\bigl\lbrack(2+i,2)\bigr\rbrack$

a 21-digit Gaussian integer, through its norm

live ↗

In$\mathrm{FactorInteger}(100\,000\,000\,000\,000\,000\,039+100\,000\,000\,000\,000\,000\,129i)$Out$\bigl\lbrack(-i,1), (1+i,1), (99+34i,1), (1\,538+213i,1), (277\,789\,996\,706\,096+549\,000\,467\,740\,335i,1)\bigr\rbrack$

Rationals: the denominator's primes get negative exponents

live ↗

In$\mathrm{FactorInteger}(\frac{3}{8})$Out$\bigl\lbrack(2,-3), (3,1)\bigr\rbrack$

$9+12i=3(2+i)^2$

live ↗

In$\mathrm{FactorInteger}(9+12i)$Out$\bigl\lbrack(2+i,2), (3,1)\bigr\rbrack$

$36=-(1+i)^4\cdot3^2$: 2 ramifies, 3 stays prime

live ↗

In$\mathrm{FactorInteger}(36, \mathrm{Rule}(\mathrm{Over}, \mathrm{GaussianIntegers}))$Out$\bigl\lbrack(-1,1), (1+i,4), (3,2)\bigr\rbrack$

Listable: threads over a list

live ↗

In$\mathrm{FactorInteger}(\bigl\lbrack11, 101, 1\,001\bigr\rbrack)$Out$\bigl\lbrack\bigl\lbrack(11,1)\bigr\rbrack, \bigl\lbrack(101,1)\bigr\rbrack, \bigl\lbrack(7,1), (11,1), (13,1)\bigr\rbrack\bigr\rbrack$

A 21-digit prime cubed factors at once

live ↗

In$\mathrm{FactorInteger}(100\,000\,000\,000\,000\,000\,039^3)$Out$\bigl\lbrack(100\,000\,000\,000\,000\,000\,039,3)\bigr\rbrack$

Properties #

Multiplying the $p^e$ factors back together recovers $n$: $2^3\cdot3^2\cdot5=360$

live ↗

In$2^3×3^2×5=360$Out$\mathrm{True}$

Possible issues #

compute-engine returns the trivial factor $1^1$

live ↗

In$\mathrm{FactorInteger}(1)$Out$\bigl\lbrack(1,1)\bigr\rbrack$

0 is represented as $0^1$

live ↗

In$\mathrm{FactorInteger}(0)$Out$\bigl\lbrack(0,1)\bigr\rbrack$

Negative numbers carry an explicit $-1$ unit factor

live ↗

In$\mathrm{FactorInteger}(-60)$Out$\bigl\lbrack(-1,1), (2,2), (3,1), (5,1)\bigr\rbrack$

$-1$ is a unit and factors as itself

live ↗

In$\mathrm{FactorInteger}(-1)$Out$\bigl\lbrack(-1,1)\bigr\rbrack$

Neat examples #

The Hardy-Ramanujan taxicab number, $7\times13\times19$. See Divisors

live ↗

In$\mathrm{FactorInteger}(1\,729)$Out$\bigl\lbrack(7,1), (13,1), (19,1)\bigr\rbrack$

About

Examples	47
Checked against	Wolfram Language 45 agree2 differSageMath 33 agree3 differSymPy 11 agree7 differ4 errormathlib4 6 agree3 differ13 errorJulia 18 agree19 errorRust 8 agree2 differ12 errormpmath 1 agreeOscar 1 agree
Crosswalk	WikipediaMathWorldWikidataWolfram LanguageSageMathSymPyJuliaRustRosetta Code

Implementation

mappedsagepackages/oracle/src/mappings.ts

Sage has no unit factor for 1, 0 or a negative n — a shape difference from compute-engine's explicit 1^1/0^1/-1^1, not a bug.

mappedsympypackages/oracle/src/mappings.ts

factorrat is SymPy's factorint that also takes a rational, giving the denominator's primes negative exponents as ours does. SymPy has no factor for 1, writes the -1 of a negative integer after the primes and a negative rational's between the numerator's primes and the denominator's, and lists factors in the order it finds them, which for a large n is not always ascending. A Complex operand is not emitted: factorrat takes rationals only, and SymPy has no factorization in Z[i] to ask for.

mappedsympypackages/oracle/src/mappings.ts

The Over -> GaussianIntegers and QuadraticIntegers(d) forms have no SymPy counterpart: factorint and factorrat are over Z and Q, GaussianIntegerRing has a gcd but no prime factorization, and factor(n, gaussian=True) factors polynomials, leaving an integer as it is. Composing one from factorint of the norm and a gcd would test our algorithm against a restatement of itself.

mappedjuliapackages/oracle/src/mappings.ts

mappedrustpackages/oracle/src/mappings.ts

Positive operands only.

mappedmathlib4packages/oracle/src/mappings.ts

Nat.primeFactorsList (ascending, with multiplicity) grouped into [prime, exponent] pairs. Natural n only: Mathlib has no unit factor, so 0 and 1 give [] where ours gives 0^1 and 1^1, and a negative or rational n is a domain error.

See also: NthPrime, Divisors, PrimeNu, PrimeOmega