//! Opt-in exact integer queries. Standard integer syntax remains in `integers`.
mod discrete;
mod expression;
mod reports;
mod wording;
use crate::{Context, Error, Outcome, Plugin, re};
use num_bigint::BigInt;
use num_integer::Integer;
use num_traits::{One, Signed, ToPrimitive, Zero};
pub struct IntegerQueries;
impl IntegerQueries {
pub(crate) fn recognizes(input: &str) -> bool {
let s = wording::normalize(input);
if s.contains('%') || re!(r"\b(?:percent|percentage|per cent)\b").is_match(&s) {
return false;
}
discrete::recognizes(&s) || re!(r"\b(?:prime|primes|primality|prime-factorize|factorization|gcd|gcf|lcm|greatest common divisor|least common multiple|lowest common multiple|divisors|coprime|remainder|mod|modulo|residue|factorial|choose|chosen|permutation|permutations|arrangements|binary strings|divisible|subsets|hands|balls|solutions|coefficient|pseudoprime|hamming|xor|circular table|without repetition|last \w+ digits)\b|\d[cp]\d|!|<<|>>|&|\|").is_match(&s)
|| re!(r"^(?:how many 1 bits are in [-+()0-9a-fbox */^]+$|how many bits are in (?:the decimal number )?[-+()0-9 */^]+$|set the least significant 1 bit of |clear bit \d+ of |reverse the order of the \d+ bits in |interpret [01]+ as an? \d+-bit two's-complement integer|(?:convert )?.+ to \d+-bit two's-complement binary|(?:the )?\d+-bit result of |.+ rotated (?:left|right) by \d+ bits within \d+ bits|.+ in \d+-bit unsigned arithmetic|convert .+ to an? integer base-\d+ numeral without specifying a rounding rule)").is_match(&s)
|| wording::numeral_request(&s)
|| re!(r"^reduce .+ to lowest terms$").is_match(&s)
}
}
pub(super) fn err<T>(code: &str) -> Result<T, Error> {
Err(Error(code.into()))
}
pub(super) fn bounded(n: &BigInt, limit: u64) -> Result<u64, Error> {
if n.is_negative() {
return err("invalid_integer_argument");
}
n.to_u64()
.filter(|n| *n <= limit)
.ok_or_else(|| Error("integer_limit".into()))
}
pub(crate) fn value(s: &str) -> Result<BigInt, Error> {
expression::parse(s)?.eval()
}
pub(crate) fn ratio_value(s: &str) -> Result<(BigInt, BigInt), Error> {
expression::ratio(s)
}
/// Explicit variable roles reuse the same bounded exact arithmetic tree.
pub(crate) fn ratio_with_bindings(
s: &str,
bindings: &[(&str, num_rational::BigRational)],
) -> Result<num_rational::BigRational, Error> {
expression::with_bindings(s, bindings)
}
pub(crate) fn affine_value(
s: &str,
variables: &[&str],
) -> Result<(num_rational::BigRational, Vec<num_rational::BigRational>), Error> {
expression::affine(s, variables)
}
pub(crate) fn quadratic_value(
s: &str,
variable: &str,
) -> Result<[num_rational::BigRational; 3], Error> {
expression::quadratic(s, variable)
}
pub(crate) fn quadratic_variable(s: &str) -> Result<String, Error> {
expression::quadratic_variable(s)
}
/// Route only a complete bounded solution-list request with closed report goals.
pub(crate) fn finite_solution_request(input: &str) -> bool {
discrete::finite_report_request(&wording::normalize(input))
}
pub(super) fn factorial(n: &BigInt) -> Result<BigInt, Error> {
let n = bounded(n, 10_000)?;
Ok((2..=n).fold(BigInt::one(), |a, b| a * b))
}
pub(super) fn choose(n: &BigInt, k: &BigInt, permutation: bool) -> Result<BigInt, Error> {
if n.is_negative() || k.is_negative() || k > n {
return err("invalid_integer_argument");
}
let k = if permutation {
k.clone()
} else {
k.min(&(n - k)).clone()
};
let k = bounded(&k, 100_000)?;
let mut result = BigInt::one();
for i in 0..k {
result *= n - i;
if !permutation {
result /= i + 1;
}
if result.bits() > 1_000_000 {
return err("integer_limit");
}
}
Ok(result)
}
pub(crate) fn decimal(n: &BigInt) -> String {
let raw = n.to_string();
let (sign, digits) = raw
.strip_prefix('-')
.map(|s| ("-", s))
.unwrap_or(("", &raw));
let mut result = sign.to_string();
for (i, ch) in digits.chars().enumerate() {
if i > 0 && (digits.len() - i).is_multiple_of(3) {
result.push(',');
}
result.push(ch);
}
result
}
fn numeral(n: &BigInt, base: u32, width: usize) -> Result<String, Error> {
if !(2..=36).contains(&base) {
return err("invalid_base");
}
if base == 10 {
return Ok(decimal(n));
}
let digits = n.abs().to_str_radix(base).to_ascii_uppercase();
let digits = format!("{:0>width$}", digits);
let sign = if n.is_negative() { "-" } else { "" };
Ok(match base {
2 => format!("{sign}0b{digits}"),
8 => format!("{sign}0o{digits}"),
16 => format!("{sign}0x{digits}"),
_ => format!("{sign}{digits} (base {base})"),
})
}
fn prime(n: &BigInt) -> Result<bool, Error> {
if n < &BigInt::from(2) {
return Ok(false);
}
if let Some(n) = n.to_u64() {
return Ok(super::integers::prime(n));
}
let next = n + BigInt::one();
if (&next & (&next - 1u8)).is_zero() {
let p = next.bits() - 1;
if !super::integers::prime(p) {
return Ok(false);
}
// Exact Lucas–Lehmer for Mersenne numbers; bound work, never substitute a probable-prime test.
if p > 4096 {
return err("unsupported_exact_primality");
}
let mut residue = BigInt::from(4);
for _ in 0..p - 2 {
residue = (&residue * &residue - 2u8).mod_floor(n);
}
return Ok(residue.is_zero());
}
for divisor in 2..=1000u32 {
if (n % divisor).is_zero() {
return Ok(false);
}
}
err("unsupported_exact_primality")
}
fn factors(n: &BigInt) -> Result<Vec<(BigInt, u32)>, Error> {
if n < &BigInt::one() {
return err("invalid_integer_argument");
}
let mut remaining = n.clone();
let mut result = Vec::new();
let mut divisor = 2u64;
while remaining > BigInt::one() {
if remaining.to_u64().is_some_and(super::integers::prime) {
result.push((remaining, 1));
break;
}
if divisor > 1_000_000 {
return err("unsupported_factorization");
}
let mut exponent = 0;
while (&remaining % divisor).is_zero() {
remaining /= divisor;
exponent += 1;
}
if exponent > 0 {
result.push((BigInt::from(divisor), exponent));
}
divisor = if divisor == 2 { 3 } else { divisor + 2 };
}
Ok(result)
}
fn factor_display(n: &BigInt) -> Result<String, Error> {
Ok(factor_terms(&factors(n)?))
}
fn factor_terms(factors: &[(BigInt, u32)]) -> String {
if factors.is_empty() {
return "1".into();
}
factors
.iter()
.map(|(p, e)| {
if *e == 1 {
decimal(p)
} else {
format!("{}^{e}", decimal(p))
}
})
.collect::<Vec<_>>()
.join(" * ")
}
fn valuation_factorial(n: u64, p: u64) -> u64 {
let mut result = 0;
let mut divided = n;
while divided >= p {
divided /= p;
result += divided;
}
result
}
impl Plugin for IntegerQueries {
fn evaluate(&self, input: &str, _: &Context) -> Outcome {
let s = wording::normalize(input);
let numeral_request = wording::numeral_request(&s);
let integer_request = Self::recognizes(&s) && !numeral_request;
if !integer_request {
// Presentation, decimal-place rounding, and physical conversions belong
// to their existing plugins; only complete integer numeral forms claim here.
return wording::special(&s).and_then(|result| match result {
Err(e)
if matches!(
e.0.as_str(),
"integer_required" | "invalid_integer_expression"
) && !numeral_request =>
{
None
}
result => Some(result),
});
}
if re!(r"\b(?:meters?|seconds?|kilograms?|degrees celsius)\b")
.is_match(&discrete::quantity_diagnostic_input(&s))
{
return Some(err("incompatible_units"));
}
Some(self.query(&s))
}
}
impl IntegerQueries {
fn query(&self, s: &str) -> Result<String, Error> {
if let Some(result) = discrete::query(s) {
return result;
}
if let Some(report) = reports::query(s) {
return report;
}
if let Some(result) = wording::special(s) {
return result;
}
if let Some(c) = re!(r"^(?:is (.+) (?:a prime number|prime)|test (.+) for primality|check whether (.+) is prime|determine if (.+) is prime)$").captures(s) {
let raw = (1..=4).find_map(|i| c.get(i)).unwrap().as_str();
return Ok(prime(&value(raw)?)?.to_string());
}
if let Some(c) = re!(r"^(?:prime-factorize|(?:give the )?prime factorization of|factor) (.+?)(?: into primes)?$").captures(s) {
return factor_display(&value(&c[1])?);
}
if let Some(c) = re!(r"^(?:the )?distinct prime factors of (.+)$").captures(s) {
return Ok(factors(&value(&c[1])?)?
.iter()
.map(|(p, _)| decimal(p))
.collect::<Vec<_>>()
.join(", "));
}
if let Some(c) = re!(r"^(?:how many positive divisors does (.+) have|(?:the )?sum of all positive divisors of (.+))$").captures(s) {
let count = c.get(1).is_some();
let n = value(c.get(1).or_else(|| c.get(2)).unwrap().as_str())?;
let mut result = BigInt::one();
for (p, e) in factors(&n)? { result *= if count { BigInt::from(e + 1) } else { (p.pow(e + 1) - 1u8) / (p - 1u8) }; }
return Ok(decimal(&result));
}
if let Some(c) = re!(r"^gcd and lcm of (.+) and (.+)$").captures(s) {
let (a, b) = (value(&c[1])?, value(&c[2])?);
return Ok(format!(
"gcd: {}; lcm: {}",
decimal(&a.gcd(&b)),
decimal(&a.lcm(&b))
));
}
if let Some(c) =
re!(r"^reduce (.+?)(?: to lowest terms| and report the gcd used)$").captures(s)
{
let (a, b) = c[1]
.split_once('/')
.ok_or_else(|| Error("invalid_integer_expression".into()))?;
let (a, b) = (value(a)?, value(b)?);
if b.is_zero() {
return err("division_by_zero");
}
let gcd = a.gcd(&b);
let sign = b.signum();
let fraction = format!(
"{}/{}",
decimal(&(&a / &gcd * &sign)),
decimal(&(&b / &gcd * sign))
);
return Ok(if s.ends_with("gcd used") {
format!("{fraction}; gcd: {}", decimal(&gcd))
} else {
fraction
});
}
if let Some(c) = re!(r"^how many trailing zeros does (.+)! have in base (\d+)$").captures(s)
{
let n = bounded(&value(&c[1])?, u64::MAX)?;
let base = value(&c[2])?;
if base < BigInt::from(2) {
return err("invalid_base");
}
let zeroes = factors(&base)?
.into_iter()
.map(|(p, e)| {
p.to_u64()
.map(|p| valuation_factorial(n, p) / u64::from(e))
.ok_or_else(|| Error("integer_limit".into()))
})
.collect::<Result<Vec<_>, _>>()?
.into_iter()
.min()
.unwrap();
return Ok(decimal(&BigInt::from(zeroes)));
}
if let Some(c) = re!(r"^(?:(?:the )?largest power of (.+) that divides (.+)!|(?:the )?exponent of (.+) in the prime factorization of (.+)!)$").captures(s) {
let (p, n) = if c.get(1).is_some() { (value(&c[1])?, value(&c[2])?) } else { (value(&c[3])?, value(&c[4])?) };
if !prime(&p)? { return err("invalid_integer_argument"); }
let e = valuation_factorial(bounded(&n, u64::MAX)?, bounded(&p, u64::MAX)?);
return Ok(if c.get(1).is_some() { format!("{}^{e}", decimal(&p)) } else { decimal(&BigInt::from(e)) });
}
if let Some(c) =
re!(r"^how many positive integers less than (.+) are coprime to (.+)$").captures(s)
{
let (limit, n) = (value(&c[1])?, value(&c[2])?);
if limit != n || n < BigInt::from(2) {
return err("invalid_integer_argument");
}
let mut result = n.clone();
for (p, _) in factors(&n)? {
result = result / &p * (p - 1u8);
}
return Ok(decimal(&result));
}
if let Some(c) =
re!(r"^how many numbers from (.+) through (.+) are divisible by (.+) or (.+)$")
.captures(s)
{
let (start, end, a, b) = (value(&c[1])?, value(&c[2])?, value(&c[3])?, value(&c[4])?);
if start < BigInt::one() || start > end || a <= BigInt::zero() || b <= BigInt::zero() {
return err("invalid_integer_argument");
}
let lcm = a.lcm(&b);
let count = |n: BigInt| &n / &a + &n / &b - &n / &lcm;
return Ok(decimal(&(count(end) - count(start - 1u8))));
}
if let Some(c) = re!(r"^(?:the )?last (\w+) digits of (.+)$").captures(s) {
let digits = match &c[1] {
"one" => 1,
"two" => 2,
"three" => 3,
s => s
.parse::<u32>()
.map_err(|_| Error("invalid_integer_argument".into()))?,
};
if digits > 1000 {
return err("integer_limit");
}
let result = value(&format!("({}) mod {}", &c[2], BigInt::from(10).pow(digits)))?;
return Ok(format!("{:0>width$}", result, width = digits as usize));
}
if let Some(c) = re!(r"^is (.+) a fermat pseudoprime to base (.+)$").captures(s) {
let (n, a) = (value(&c[1])?, value(&c[2])?);
return Ok((n > BigInt::one()
&& !prime(&n)?
&& a.gcd(&n).is_one()
&& a.modpow(&(&n - 1u8), &n).is_one())
.to_string());
}
if let Some(c) = re!(r"^(?:(?:the )?smallest prime greater than (.+)|(?:the )?(\d+)(?:st|nd|rd|th) prime|how many primes are there between (.+) and (.+)|sum the primes less than (.+))$").captures(s) {
let (start, end, ordinal, sum) = if let Some(n) = c.get(1) { (bounded(&value(n.as_str())?, 10_000_000)? + 1, 10_000_001, None, false) }
else if let Some(n) = c.get(2) { (2, 10_000_001, Some(bounded(&value(n.as_str())?, 100_000)?), false) }
else if let Some(n) = c.get(3) { (bounded(&value(n.as_str())?, 10_000_000)?, bounded(&value(&c[4])?, 10_000_000)? + 1, None, false) }
else { (2, bounded(&value(&c[5])?, 10_000_000)?, None, true) };
let mut count = 0u64; let mut total = 0u64;
for n in start..end { if super::integers::prime(n) { count += 1; total += n; if c.get(1).is_some() || ordinal == Some(count) { return Ok(decimal(&BigInt::from(n))); } } }
if ordinal.is_some() || c.get(1).is_some() { return err("integer_limit"); }
return Ok(decimal(&BigInt::from(if sum { total } else { count })));
}
if let Some(c) = re!(r"^(.+) and (?:give its prime factorization|then take its remainder modulo (.+)|then express it in (.+))$").captures(s) {
let result = value(&wording::expression(&c[1]))?;
if c.get(2).is_some() { return Ok(decimal(&value(&format!("{result} mod {}", &c[2]))?)); }
if c.get(3).is_some() { return numeral(&result, wording::base(&c[3])?, 0); }
return factor_display(&result);
}
if let Some(c) = re!(r"^(.+), (?:then )?express it in (.+)$").captures(s) {
return numeral(
&value(&wording::expression(&c[1]))?,
wording::base(&c[2])?,
0,
);
}
if let Some(c) = re!(r"^(.+), (?:then )?take the remainder modulo (.+)$").captures(s) {
return Ok(decimal(&value(&format!(
"({}) mod ({})",
wording::expression(&c[1]),
&c[2]
))?));
}
let expression = wording::expression(s);
let result = value(&expression)?;
let base = if expression.contains(['&', '|', '<', '>']) || expression.contains("xor") {
if expression.trim_start_matches('(').starts_with("0x") {
16
} else if expression.trim_start_matches('(').starts_with("0b") {
2
} else {
10
}
} else {
10
};
numeral(&result, base, 0)
}
}