Integer number theory
All functions take and return Expression objects holding integer leaves,
so arbitrary precision flows through the existing machinery; passing a
non-integer expression raises. (Exception: continued_fraction_rational
also accepts rational leaves; the three symbol functions return plain
machine integers.)
is_prime#
api::Session method
pub fn is_prime(
&self,
argument: &Expression,
) -> Result<Option<bool>, ApiError>Calling forms
api::Expression method: api::Expression::is_prime
pub fn is_prime(&self) -> Result<TruthValue, ApiError>Deterministic primality verdict; None when the input is outside the
classifier's domain (e.g. not a natural number representation it
handles).
factor_integer#
api::Session method
pub fn factor_integer(
&self,
argument: &Expression,
) -> Result<Vec<(Expression, u32)>, ApiError>Prime factorization as (prime, multiplicity) pairs, ascending. Errors on
zero. Notes: WASM returns PrimeFactor objects with
prime/multiplicity getters; the sign of a negative input is carried
as a leading (-1, 1) factor exactly as the core reports it.
prime_factor (WASM result class)#
prime#
api::results::PrimeFactor method
pub fn prime(&self) -> ExpressionThe prime itself.
multiplicity#
api::results::PrimeFactor method
pub fn multiplicity(&self) -> u32Calling forms and variants
Variant for this object — api::results::RootMultiplicity method: api::results::RootMultiplicity::multiplicity
pub fn multiplicity(&self) -> usizeinteger_gcd#
api::Session method
pub fn integer_gcd(
&self,
left: &Expression,
right: &Expression,
) -> Result<Expression, ApiError>Greatest common divisor (non-negative).
integer_lcm#
api::Session method
pub fn integer_lcm(
&self,
left: &Expression,
right: &Expression,
) -> Result<Expression, ApiError>Least common multiple.
extended_euclidean#
api::number_theory::Session method
pub fn extended_euclidean(
&self,
left: &Expression,
right: &Expression,
) -> Result<(Expression, Expression, Expression), ApiError>(gcd, x, y) with . Notes: WASM returns a 3-element
array [gcd, x, y].
modular_power#
api::number_theory::Session method
pub fn modular_power(
&self,
base: &Expression,
exponent: &Expression,
modulus: &Expression,
) -> Result<Expression, ApiError>base^exponent mod modulus by square-and-multiply; requires positive
modulus and non-negative exponent.
modular_inverse#
api::number_theory::Session method
pub fn modular_inverse(
&self,
value: &Expression,
modulus: &Expression,
) -> Result<Expression, ApiError>Multiplicative inverse of value modulo modulus; errors when
.
chinese_remainder#
api::number_theory::Session method
pub fn chinese_remainder(
&self,
residues_and_moduli: &[(Expression, Expression)],
) -> Result<Expression, ApiError>The smallest non-negative solution of the simultaneous congruences
. Moduli need not be pairwise coprime; inconsistent systems
raise. Notes: WASM passes a flat interleaved array
[residue_0, modulus_0, ...].
euler_totient#
api::number_theory::Session method
pub fn euler_totient(
&self,
value: &Expression,
) -> Result<Expression, ApiError>Euler's ; requires a positive integer.
mobius#
api::Session method
pub fn mobius(
&self,
argument: &Expression,
) -> Result<Expression, ApiError>Möbius ; requires a positive integer.
divisor_count#
api::Session method
pub fn divisor_count(
&self,
argument: &Expression,
) -> Result<Expression, ApiError>Number of positive divisors .
divisor_sigma#
api::Session method
pub fn divisor_sigma(
&self,
argument: &Expression,
power: u32,
) -> Result<Expression, ApiError>Sum of the power-th powers of the positive divisors ;
power = 0 gives divisor_count, power = 1 the divisor sum.
jacobi_symbol#
api::Session method
pub fn jacobi_symbol(
&self,
numerator: &Expression,
denominator: &Expression,
) -> Result<i32, ApiError>The Jacobi symbol ; the denominator must be a positive odd integer.
legendre_symbol#
api::Session method
pub fn legendre_symbol(
&self,
numerator: &Expression,
prime: &Expression,
) -> Result<i32, ApiError>The Legendre symbol; the second argument must be an odd prime.
kronecker_symbol#
api::Session method
pub fn kronecker_symbol(
&self,
numerator: &Expression,
denominator: &Expression,
) -> Result<i32, ApiError>The Kronecker extension of the Jacobi symbol to all integer denominators.
integer_square_root#
api::Session method
pub fn integer_square_root(
&self,
argument: &Expression,
) -> Result<Expression, ApiError>for non-negative n.
integer_nth_root#
api::Session method
pub fn integer_nth_root(
&self,
argument: &Expression,
root_index: u64,
) -> Result<Expression, ApiError>; odd indices accept negative n. Errors when no real root exists (even index, negative n).
continued_fraction_rational#
api::number_theory::Session method
pub fn continued_fraction_rational(
&self,
value: &Expression,
) -> Result<Vec<Expression>, ApiError>Terminating continued-fraction expansion [a0; a1, a2, ...] of an integer
or rational expression leaf.
continued_fraction_quadratic_irrational#
api::number_theory::Session method
pub fn continued_fraction_quadratic_irrational(
&self,
value: &Expression,
) -> Result<QuadraticContinuedFractionExpansion, ApiError>Eventually-periodic expansion of for a non-negative integer d, returned
as (initial_terms, periodic_part). Perfect squares give a one-element
initial part and an empty period. Notes: WASM returns a
QuadraticContinuedFractionExpansion object with
initial_terms/periodic_terms getters.
quadratic_continued_fraction_expansion (WASM result class)#
initial_terms#
api::results::QuadraticContinuedFractionExpansion method
pub fn initial_terms(&self) -> Vec<Expression>The terms preceding the period.
periodic_terms#
api::results::QuadraticContinuedFractionExpansion method
pub fn periodic_terms(&self) -> Vec<Expression>The repeating terms of the period.
Diophantine equations#
The two supported Diophantine subclasses are linear equations via the extended Euclidean algorithm and Pell's equation via the continued fraction of . General Diophantine solving is undecidable (Matiyasevich–Robinson–Davis–Putnam) and is out of scope; the solvers return exact integers and never guess.
solve_linear_diophantine#
api::number_theory::Session method
pub fn solve_linear_diophantine(
&self,
coefficients: &[Expression],
constant: &Expression,
) -> Result<Vec<Expression>, ApiError>General integer solution of , returned as the parametric
coordinates — one expression per unknown, affine in fresh integer parameter
symbols (diophantine_parameter_k) shared across the coordinates so that
choosing any integers for the parameters yields a solution tuple. The list is
empty only when the equation provably has no integer solution
(). When every coefficient and the constant are zero, each
coordinate is its own fresh integer parameter. All coefficients and the constant
must be integer expression leaves; any other input, including an empty coefficient
list, raises a declined-computation error instead of returning an empty list.
solve_linear_diophantine_system#
api::number_theory::Session method
pub fn solve_linear_diophantine_system(
&self,
coefficient_matrix: &Matrix,
constants: &[Expression],
) -> Result<Vec<Expression>, ApiError>General integer solution of the rectangular system , returned as one
parametric coordinate expression per column of A. The coordinates share fresh
integer parameter symbols and describe the complete affine integer lattice of
solutions. The list is empty only when the system provably has no integer
solution. A row count of A that differs from the number of constants raises a
length-mismatch error, and an entry that is not an integer expression leaf raises
a declined-computation error.
solve_pell#
api::number_theory::Session method
pub fn solve_pell(
&self,
radicand: &Expression,
) -> Result<Vec<Expression>, ApiError>Fundamental solution [x, y] of for a positive non-square
integer D, the smallest positive solution from which all others are generated
by the recurrence , . The list is
empty when D is a perfect square or non-positive (no nontrivial fundamental
solution). A radicand that is not an exact integer raises an integer-required
error.
solve_negative_pell#
api::number_theory::Session method
pub fn solve_negative_pell(
&self,
radicand: &Expression,
) -> Result<Vec<Expression>, ApiError>Fundamental solution [x, y] of the negative-Pell equation
when it is solvable (exactly when the continued fraction of has odd period),
and an empty list for an integer D for which it is not. A radicand that is not an
exact integer raises an integer-required error.
pell_solutions#
api::number_theory::Session method
pub fn pell_solutions(
&self,
radicand: &Expression,
count: usize,
) -> Result<Vec<Expression>, ApiError>The first count positive solutions of , materialised from the
fundamental solution by the Pell recurrence and returned as a flat list
. Empty when the integer D has no fundamental
solution; a radicand that is not an exact integer raises an integer-required error.
Integer-domain solving#
solve_integers is the deliberate integer-domain solver. It takes a conjunction of
equations and linear congruences in an ordered list of integer unknowns, and either
states the complete integer solution set or declines with a typed reason. It never
returns a few sampled solutions as if they were all of them, and it never reports
"no solution" for a problem it could not decide. General Diophantine equations are
undecidable, so the accepted classes are deliberately narrow:
| Request | Result |
|---|---|
| One unknown, rational-coefficient polynomial or rational equations | finite, empty, or lattice_family (every integer except undefined_points) |
| One unknown, linear congruences, with or without equations | congruence_family (one residue class), finite, or empty |
| Several unknowns, affine equations and congruences | lattice_family, finite, or empty, by Smith normal form |
Two unknowns, one equation a*x^2 + b*y^2 + c = 0 reducing to x^2 - D*y^2 = N |
pell_orbits, finite, or empty |
| Anything else, including symbolic parameters | declined with unsupported_class |
solve_integers#
api::number_theory::Session method
pub fn solve_integers<'a, IteratorType, VariableType>(
&self,
equations: &[Expression],
unknowns: IteratorType,
congruences: &[Expression],
moduli: &[Expression],
options: IntegerSolveOptions,
) -> Result<IntegerSolveReport, ApiError>
where
IteratorType: IntoIterator<Item = VariableType>,
VariableType: Into<VariableLike<'a>>,Each equation is an equation or an expression meaning expression = 0. Congruence
i states that congruences[i] vanishes modulo the positive integer moduli[i];
congruences are passed through this typed boundary, never parsed from mod syntax,
and must be affine with integer coefficients. An empty or repeated unknown list, a
moduli list of a different length, a modulus that is not a positive integer, and a
zero limit are errors, not declines.
Every report that is not declined reads the same way. The integer solutions are
exactly the tuples obtained by substituting integers for parameters into one of the
solutions, other than the undefined_points. The three kinds of answer are kept
apart:
finiteandemptyhave no parameters:solutionsis the whole enumerated set, and an empty list is a proof of no solution.lattice_familyandcongruence_familyare unbounded integer parameter families:6*x + 9*y = 21gives one tuple affine in one parameter, with itslattice_particularpoint and Hermite-reducedlattice_basis; givesx = 4 + 5*kwithresidue4 andmodulus5.pell_orbitsis a union of orbits under multiplication by the norm-one unit, not a list of samples.x^2 - 5*y^2 = 4reports itspell_equation, the unit(9, 4), one seed per orbit, and two closed-form tuples per seed, one for each sign, exact in an integer exponentk. Every orbit is covered because each solution has exactly one representative in the unit's fundamental interval, and the scan of that interval is exhaustive.
Source definedness is kept: 1/(x - 1) = 0 is empty, and undefined_points still
lists 1. A request whose proof would exceed a limit declines rather than returning
part of the answer: a generalized Pell scan needing more than
maximum_seed_candidates ordinates declines with seed_candidate_limit, and an
integer or unit longer than maximum_integer_bits bits declines with
integer_size_limit or fundamental_unit_limit. x^3 + y^3 + z^3 = 3 declines with
unsupported_class. Python returns a dictionary with one key per report field below;
WASM, Kotlin, and Swift return an IntegerSolveReport object.
IntegerSolveReport#
What solve_integers returns. complete is false only for a declined report.
integer_report_verdict#
api::results::IntegerSolveReport method
pub fn verdict(&self) -> IntegerSolveVerdictGetter on IntegerSolveReport: finite, empty, lattice_family,
congruence_family, pell_orbits, or declined.
integer_report_complete#
api::results::IntegerSolveReport method
pub fn complete(&self) -> boolGetter on IntegerSolveReport: whether the report states the whole integer solution
set.
integer_report_unknowns#
api::results::IntegerSolveReport method
pub fn unknowns(&self) -> Vec<Expression>Getter on IntegerSolveReport: the requested unknowns, in the order every tuple uses.
integer_report_solutions#
api::results::IntegerSolveReport method
pub fn solutions(&self) -> Vec<IntegerSolutionTuple>Getter on IntegerSolveReport: the solution tuples, exact in the integer parameters.
integer_report_parameters#
api::results::IntegerSolveReport method
pub fn parameters(&self) -> Vec<Expression>Getter on IntegerSolveReport: the parameters of the solution tuples, each ranging
over every integer.
integer_report_undefined_points#
api::results::IntegerSolveReport method
pub fn undefined_points(&self) -> Vec<IntegerSolutionTuple>Getter on IntegerSolveReport: the integer points at which some source equation is
undefined. No solution is one of them.
integer_report_lattice_particular#
api::results::IntegerSolveReport method
pub fn lattice_particular(&self) -> Option<IntegerSolutionTuple>Getter on IntegerSolveReport: one point of the solution lattice of a
lattice_family report.
integer_report_lattice_basis#
api::results::IntegerSolveReport method
pub fn lattice_basis(&self) -> Vec<IntegerSolutionTuple>Getter on IntegerSolveReport: a Hermite-reduced basis of the direction lattice of a
lattice_family report.
integer_report_residue#
api::results::IntegerSolveReport method
pub fn residue(&self) -> Option<Expression>Getter on IntegerSolveReport: the least nonnegative member of the class of a
congruence_family report.
integer_report_modulus#
api::results::IntegerSolveReport method
pub fn modulus(&self) -> Option<Expression>Getter on IntegerSolveReport: the positive modulus of the class of a
congruence_family report.
integer_report_pell_equation#
api::results::IntegerSolveReport method
pub fn pell_equation(&self) -> Option<Expression>Getter on IntegerSolveReport: the normalized equation x^2 - D*y^2 = N of a
pell_orbits report, written in the unknowns.
integer_report_pell_unit#
api::results::IntegerSolveReport method
pub fn pell_unit(&self) -> Option<IntegerSolutionTuple>Getter on IntegerSolveReport: the fundamental solution (u, v) of
u^2 - D*v^2 = 1 that generates every orbit.
integer_report_pell_seeds#
api::results::IntegerSolveReport method
pub fn pell_seeds(&self) -> Vec<IntegerSolutionTuple>Getter on IntegerSolveReport: one seed per orbit, in the order of the requested
unknowns.
integer_report_proof_methods#
api::results::IntegerSolveReport method
pub fn proof_methods(&self) -> Vec<IntegerSolveProofMethod>Getter on IntegerSolveReport: the kinds of exact evidence the result rests on, such
as integer_root_theorem, chinese_remainder, smith_normal_form, or
pell_fundamental_interval.
integer_report_decline_reason#
api::results::IntegerSolveReport method
pub fn decline_reason(&self) -> Option<IntegerSolveDeclineReason>Getter on IntegerSolveReport: why the solve made no claim, present exactly when the
verdict is declined.
IntegerSolutionTuple#
One exact tuple of a report, with one coordinate per requested unknown.
integer_tuple_coordinates#
api::results::IntegerSolutionTuple method
pub fn coordinates(&self) -> Vec<Expression>Getter on IntegerSolutionTuple: the coordinates, in the order of the requested
unknowns.
Example#
This family is not part of the recommended symi::api facade in this release. Call it through the native modules in the native Rust API reference.
Additional API#
api::number_theory#
api module
pub mod number_theory;Integer and Diophantine operations of the native API.
prime#
api::Session method
pub fn prime(
&self,
subject: &Expression,
) -> Result<AssumptionProposition, ApiError>Construct a primality proposition for a scalar expression.
prime_factorization#
api::number_theory::Session method
pub fn prime_factorization(
&self,
value: &Expression,
) -> Result<Vec<PrimeFactor>, ApiError>The prime factorization of an integer with each prime's exponent.
IntegerSolutionTuple#
api re_export
pub use results::IntegerSolutionTuple;An ordered tuple of exact integer-valued coordinates, one per requested unknown.
IntegerSolveDeclineReason#
api re_export
pub use results::IntegerSolveDeclineReason;Why a deliberate integer-domain solve made no claim.
IntegerSolveDeclineReason.CertificateReplayFailed#
api::results::IntegerSolveDeclineReason variant
CertificateReplayFailed,An independent replay disagreed with the computed result.
IntegerSolveDeclineReason.DegreeLimit#
api::results::IntegerSolveDeclineReason variant
DegreeLimit,A degree or exponent exceeds the solver's limit.
IntegerSolveDeclineReason.DivisorEnumerationLimit#
api::results::IntegerSolveDeclineReason variant
DivisorEnumerationLimit,The divisors of a constant could not be proved exhaustive within the budget.
IntegerSolveDeclineReason.EnumerationLimit#
api::results::IntegerSolveDeclineReason variant
EnumerationLimit,A finite enumeration has more points than the budget allows.
IntegerSolveDeclineReason.FundamentalUnitLimit#
api::results::IntegerSolveDeclineReason variant
FundamentalUnitLimit,The norm-one unit exceeds the configured bit length.
IntegerSolveDeclineReason.IndeterminateSourceValue#
api::results::IntegerSolveDeclineReason variant
IndeterminateSourceValue,The source equation has no exact value at a candidate.
IntegerSolveDeclineReason.InfiniteNonOrbitFamily#
api::results::IntegerSolveDeclineReason variant
InfiniteNonOrbitFamily,The solutions form an infinite family that is neither a lattice nor a union of orbits.
IntegerSolveDeclineReason.IntegerSizeLimit#
api::results::IntegerSolveDeclineReason variant
IntegerSizeLimit,An input or intermediate integer exceeds the configured bit length.
IntegerSolveDeclineReason.SeedCandidateLimit#
api::results::IntegerSolveDeclineReason variant
SeedCandidateLimit,The generalized Pell seed scan needs more candidates than the configured limit.
IntegerSolveDeclineReason.UnsupportedClass#
api::results::IntegerSolveDeclineReason variant
UnsupportedClass,The request is outside every class with a complete integer solver.
IntegerSolveDeclineReason.name#
api::results::IntegerSolveDeclineReason method
pub fn name(&self) -> &'static strThe stable lowercase spelling shared by every binding.
IntegerSolveOptions#
api re_export
pub use number_theory::IntegerSolveOptions;Deterministic work limits for a deliberate integer-domain solve.
IntegerSolveOptions.from_fields#
api::number_theory::IntegerSolveOptions method
pub fn from_fields(
maximum_seed_candidates: u64,
maximum_integer_bits: u64,
) -> SelfConstruct integer-solve options from the unsigned limits a binding passes.
IntegerSolveOptions.maximum_integer_bits#
api::number_theory::IntegerSolveOptions field
pub maximum_integer_bits:The largest bit length of a coefficient, a Smith entry, D, N, or the Pell unit.
IntegerSolveOptions.maximum_seed_candidates#
api::number_theory::IntegerSolveOptions field
pub maximum_seed_candidates:The largest number of ordinates the generalized Pell seed scan may test.
IntegerSolveOptions.new#
api::number_theory::IntegerSolveOptions method
pub fn new(
maximum_seed_candidates: u64,
maximum_integer_bits: u64,
) -> SelfConstruct integer-solve options from explicit limits.
IntegerSolveProofMethod#
api re_export
pub use results::IntegerSolveProofMethod;One kind of exact evidence behind a complete integer solve.
IntegerSolveProofMethod.BinaryQuadraticEnumeration#
api::results::IntegerSolveProofMethod variant
BinaryQuadraticEnumeration,A binary quadratic equation outside the orbit class was solved by finite enumeration.
IntegerSolveProofMethod.ChineseRemainder#
api::results::IntegerSolveProofMethod variant
ChineseRemainder,Linear congruences were combined by generalized CRT and replayed.
IntegerSolveProofMethod.IntegerRootTheorem#
api::results::IntegerSolveProofMethod variant
IntegerRootTheorem,Integer-root theorem candidates were decided on the source equation.
IntegerSolveProofMethod.PellFundamentalInterval#
api::results::IntegerSolveProofMethod variant
PellFundamentalInterval,Generalized Pell seeds were enumerated over the fundamental interval of the unit.
IntegerSolveProofMethod.RangeEnumeration#
api::results::IntegerSolveProofMethod variant
RangeEnumeration,Every integer of a finite range was decided on the source equation.
IntegerSolveProofMethod.SmithNormalForm#
api::results::IntegerSolveProofMethod variant
SmithNormalForm,A mixed linear system was diagonalised by Smith normal form and replayed.
IntegerSolveProofMethod.UndefinedEverywhere#
api::results::IntegerSolveProofMethod variant
UndefinedEverywhere,An equation is defined at no integer.
IntegerSolveProofMethod.name#
api::results::IntegerSolveProofMethod method
pub fn name(&self) -> &'static strThe stable lowercase spelling shared by every binding.
IntegerSolveReport#
api re_export
pub use results::IntegerSolveReport;The typed result of a deliberate integer-domain solve.
IntegerSolveVerdict#
api re_export
pub use results::IntegerSolveVerdict;What a deliberate integer-domain solve established.
IntegerSolveVerdict.CongruenceFamily#
api::results::IntegerSolveVerdict variant
CongruenceFamily,Every member of one residue class of the single unknown.
IntegerSolveVerdict.Declined#
api::results::IntegerSolveVerdict variant
Declined,No claim was made.
IntegerSolveVerdict.Empty#
api::results::IntegerSolveVerdict variant
Empty,A proof that no integer tuple solves the request.
IntegerSolveVerdict.Finite#
api::results::IntegerSolveVerdict variant
Finite,Exactly the listed integer tuples, and at least one of them.
IntegerSolveVerdict.LatticeFamily#
api::results::IntegerSolveVerdict variant
LatticeFamily,Every point of an affine integer lattice, unbounded in its parameters.
IntegerSolveVerdict.PellOrbits#
api::results::IntegerSolveVerdict variant
PellOrbits,Every point of finitely many orbits of under its norm-one unit.
IntegerSolveVerdict.name#
api::results::IntegerSolveVerdict method
pub fn name(&self) -> &'static strThe stable lowercase spelling shared by every binding.
PrimeFactor#
api re_export
pub use results::PrimeFactor;One prime of an integer factorization together with its exponent.
QuadraticContinuedFractionExpansion#
api re_export
pub use results::QuadraticContinuedFractionExpansion;The eventually periodic continued-fraction expansion of a quadratic irrational.
Calling forms
Type: api::results::QuadraticContinuedFractionExpansion
pub struct QuadraticContinuedFractionExpansionRootMultiplicity#
api re_export
pub use results::RootMultiplicity;One root of a polynomial together with its multiplicity.
RootMultiplicity.root#
api::results::RootMultiplicity method
pub fn root(&self) -> ExpressionThe root itself.