factorial_engine 0.4.2

A library for producing factorials
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

# Factorial Engine


[![Crates.io](https://img.shields.io/crates/v/factorial_engine.svg?style=flat-square)](https://crates.io/crates/factorial_engine)
[![Docs.rs](https://img.shields.io/docsrs/factorial_engine?style=flat-square)](https://docs.rs/factorial_engine)
[![License: MIT OR Apache-2.0](https://img.shields.io/badge/license-MIT%20OR%20Apache--2.0-blue?style=flat-square)](https://opensource.org/licenses/MIT)
[![Rust](https://github.com/Neil-Crago/factorial_engine/actions/workflows/rust.yml/badge.svg)](https://github.com/Neil-Crago/factorial_engine/actions/workflows/rust.yml)

A high-performance, zero-error Rust crate for computing the prime factorization of factorials (`n!`).

This engine is designed as a robust, backend computational tool. It uses **Legendre's Formula** to calculate prime exponents directly, completely avoiding the need to compute or store the immense values of `n!` itself. This ensures exceptional performance and prevents any possibility of integer overflow, even for very large `n`.

For fixed-width integer inputs, the crate also includes a deterministic primality check built directly from the symbolic factorization of `n!`. In the `u64` range, the identity

`n` is prime if and only if `n! mod n^2 != 0`

can be evaluated symbolically, with the small edge cases handled explicitly. This makes it a fast, reliable symbolic-factorial test for practical fixed-width use cases.

## Features


- **High Performance:** Employs Legendre's Formula for direct calculation of prime exponents.
- **Zero Error:** Avoids large number arithmetic entirely, making it robust and free from overflow errors.
- **Efficient Prime Generation:** Includes an optimized Sieve of Eratosthenes for on-demand prime generation and caching.
- **Symbolic Factorials:** [`SymbolicFactorial`] represents `n!` as a displayable prime factorization (e.g. `2^47 × 3^22 × 5^12 × ...`).
- **Symbolic Arithmetic:** `multiply`, `checked_divide`, and `pow` combine symbolic factorials (e.g. for binomial coefficients) without ever computing the underlying integers.
- **Deterministic Primality Testing:** `FactorialEngine::is_prime_factorial` checks primality using the symbolic representation of `n!` for `u64`-sized inputs.
- **BigUint Support:** `to_biguint`, `FactorialEngine::factorial_biguint`, and `FactorialEngine::binomial` materialize exact, arbitrary-precision results via [`num-bigint`](https://crates.io/crates/num-bigint) only when you actually need the number.
- **Reverse Factorial:** [`reverse_factorial`] recovers `n` from a candidate factorial value, e.g. `reverse_factorial(120) == Ok(5)`.
- **Clean API:** Provides a simple and clear interface for getting the full symbolic factorization of `n!`.

## Usage


Add this crate to your `Cargo.toml`:

```toml
[dependencies]
factorial_engine = "0.4" # Or the latest version
```

## Example


```Rust
use factorial_engine::{reverse_factorial, FactorialEngine};

fn main() {
    // Initialize the engine. Can optionally pre-sieve primes.
    let mut engine = FactorialEngine::new(Some(100));

    let n = 50;
    let factors = engine.symbolic_factorial(n);

    // Displays as "2^47 × 3^22 × 5^12 × ...".
    println!("Symbolic factorization of {}!: {}", n, factors);

    // Example: The exponent of 2 in 50! is 47.
    assert_eq!(factors.exponent_of(2), 47);

    // Reverse factorial: recover n such that n! == value.
    assert_eq!(reverse_factorial(120), Ok(5));
    assert!(reverse_factorial(121).is_err());

    // Exact, arbitrary-precision values via BigUint.
    println!("50! = {}", engine.factorial_biguint(50));

    // Binomial coefficients computed entirely through symbolic arithmetic.
    assert_eq!(engine.binomial(5, 2), Some(10u32.into()));
}
```

## Deterministic primality testing with symbolic factorials


This crate can also test whether a number is prime using the symbolic factorization of `n!`.

```rust
use factorial_engine::FactorialEngine;

fn main() {
    let mut engine = FactorialEngine::new(None);

    for n in 2..=20 {
        let is_prime = FactorialEngine::is_prime_factorial(n, &mut engine);
        println!("{} is prime? {}", n, is_prime);
    }

    // The primality test is deterministic for fixed-width integer inputs and uses
    // the symbolic factorial representation directly.
    let n = 13;
    let fact = engine.symbolic_factorial(n);
    let n_squared = n.checked_mul(n).unwrap();
    let is_prime_via_symbolic_factorial = fact.modulo_u64(n_squared) != 0;

    assert!(is_prime_via_symbolic_factorial);
    assert!(FactorialEngine::is_prime_factorial(13, &mut engine));
}
```

This is a specialized, deterministic primality check for `u64`-sized inputs, using the fact that `n! mod n^2 != 0` for primes `n > 4`, with the small edge cases handled explicitly. For larger values, use the symbolic divisibility primitives directly rather than treating this as a general arbitrary-precision primality API.

## Purpose


This crate serves as a foundational block for applications in number theory, combinatorics, and computational mathematics. It is designed to be a reliable, "black-box" dependency that provides factorial factorization data with maximum efficiency and correctness.

## Author


Neil Crago

## Related Crates


This crate is part of a collection of crates by the same author:
These include:-

* MOMA
* MOMA_simulation_engine
* Fractal_Algebra
* tma_engine
* fa_slow_ai