lib.rs

1//! The sequence registry: every measure of every design as a sequence, the curated records, and the page they render.2#![deny(missing_docs)]34/// The markdown page the ledger renders.5pub mod markdown;6/// The measures and their cost classes.7pub mod measure;8/// The curated OEIS records and the identification against them.9pub mod records;10/// The term generators and the closed forms.11pub mod terms;1213pub use markdown::markdown;14pub use measure::{Cost, Measure};15pub use records::{identify, Record, RECORDS};16pub use terms::{closed, fill_polynomial, terms};1718use mrlyrs::core::error::{value_error, Result};19use mrlyrs::math::bang::baseq;20use mrlyrs::math::name::{Bang, Named, Sequence as SequenceName};21use std::collections::BTreeMap;22use std::sync::{Mutex, OnceLock};2324type Walked = BTreeMap<(usize, usize), &'static [u128]>;2526/// The dimension and base pairs the ledger walks.27pub const SPACES: [(usize, usize); 9] = [28    (1, 2),29    (2, 2),30    (3, 2),31    (4, 2),32    (1, 3),33    (2, 3),34    (1, 4),35    (2, 4),36    (1, 5),37];3839/// The cells a catalog row may render for one term.40pub const BUDGET: u128 = 500_000;4142/// The terms a catalog row holds.43pub const TERMS: usize = 8;4445/// The index a sequence runs along.46#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]47pub enum Axis {48    /// The fractal level from 1, at side `max(base, 3)`.49    Level,50    /// The odd side `2k - 1` from `k = 2`, at level 1.51    Side,52}5354impl Axis {55    /// Both axes, level first.56    pub const ALL: [Axis; 2] = [Axis::Level, Axis::Side];57    /// Returns the axis's one-word name.58    pub fn slug(self) -> &'static str {59        match self {60            Axis::Level => "level",61            Axis::Side => "side",62        }63    }64    /// Parses a one-word name back into its axis, or an error for any other word.65    pub fn parse(slug: &str) -> Result<Axis> {66        match slug {67            "level" => Ok(Axis::Level),68            "side" => Ok(Axis::Side),69            other => value_error(format!("unknown axis {other:?}.")),70        }71    }72    /// Returns the ledger index of the first term: the level 1 or the `k` of side 3.73    pub fn start(self) -> i32 {74        match self {75            Axis::Level => 1,76            Axis::Side => 2,77        }78    }79    /// Returns the side number and level of the term at the index.80    pub fn place(self, index: usize, number: usize) -> (usize, u32) {81        match self {82            Axis::Level => (number, index as u32 + 1),83            Axis::Side => (2 * index + 3, 1),84        }85    }86}8788/// The status a claim carries.89#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]90pub enum Tag {91    /// Proved on this tree.92    Proved,93    /// Checked against a record or a second generator.94    Verified,95    /// Stated and not yet checked.96    Conjecture,97    /// Checked and found false.98    Refuted,99}100101impl Tag {102    /// Returns the tag's capitalised word.103    pub fn text(self) -> &'static str {104        match self {105            Tag::Proved => "Proved",106            Tag::Verified => "Verified",107            Tag::Conjecture => "Conjecture",108            Tag::Refuted => "Refuted",109        }110    }111}112113/// A design sequence's address: the design, the measure and the axis.114#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]115pub struct Key {116    /// The design's code.117    pub code: u128,118    /// The design's dimension.119    pub dimension: usize,120    /// The numeral base of the corners.121    pub base: usize,122    /// The reading taken.123    pub measure: Measure,124    /// The index the reading runs along.125    pub axis: Axis,126}127128impl Key {129    /// Pins a design sequence to its address.130    pub const fn new(131        code: u128,132        dimension: usize,133        base: usize,134        measure: Measure,135        axis: Axis,136    ) -> Key {137        Key {138            code,139            dimension,140            base,141            measure,142            axis,143        }144    }145    /// Returns the sequence name this key addresses.146    pub fn named(&self) -> SequenceName {147        SequenceName::new(148            self.code,149            self.dimension,150            self.base,151            self.measure.slug(),152            self.axis.slug(),153        )154    }155    /// Returns the sequence's file name.156    ///157    /// ```158    /// use ledger::{Axis, Key, Measure};159    /// let key = Key::new(23, 3, 2, Measure::Surface, Axis::Level);160    /// assert_eq!(key.name(), "sequence_dim=3_code=23_measure=surface_axis=level");161    /// assert_eq!(key.id(), "753b6b49");162    /// ```163    pub fn name(&self) -> String {164        self.named().to_file().unwrap_or_default()165    }166    /// Returns the first eight hex digits of the sha256 of the sequence's canonical JSON.167    pub fn id(&self) -> String {168        self.named().to_id()169    }170    /// Returns the design pinned to its dimension and base.171    pub fn design(&self) -> Bang {172        Bang::new(self.code, self.dimension, self.base)173    }174    /// Returns the side number the level axis runs at.175    pub fn number(&self) -> usize {176        self.base.max(3)177    }178}179180/// A closed form of a sequence.181#[derive(Clone, Debug, PartialEq, Eq)]182pub enum Closed {183    /// `fill^level`.184    Power(u128),185    /// `cells^level - fill^level`.186    Difference(u128, u128),187    /// A polynomial in `k` by rising power, at side `2k - 1`.188    Polynomial(Vec<i128>),189    /// `a(level) = c[0] a(level-1) + c[1] a(level-2) + ...`.190    Recurrence(Vec<i128>),191}192193fn signed(text: &mut String, coefficient: i128, first: bool) {194    if first {195        if coefficient < 0 {196            text.push('-');197        }198    } else {199        text.push_str(if coefficient < 0 { " - " } else { " + " });200    }201}202203impl Closed {204    /// Spells the closed form.205    pub fn text(&self) -> String {206        match self {207            Closed::Power(f) => format!("{f}^level"),208            Closed::Difference(g, f) => format!("{g}^level - {f}^level"),209            Closed::Polynomial(coefficients) => {210                let mut text = String::new();211                for (power, &c) in coefficients.iter().enumerate().rev() {212                    if c == 0 {213                        continue;214                    }215                    let first = text.is_empty();216                    signed(&mut text, c, first);217                    if c.abs() != 1 || power == 0 {218                        text.push_str(&c.abs().to_string());219                    }220                    match power {221                        0 => {}222                        1 => text.push('k'),223                        _ => text.push_str(&format!("k^{power}")),224                    }225                }226                if text.is_empty() {227                    text.push('0');228                }229                text230            }231            Closed::Recurrence(coefficients) => {232                let mut text = String::new();233                for (back, &c) in coefficients.iter().enumerate() {234                    if c == 0 {235                        continue;236                    }237                    let first = text.is_empty();238                    signed(&mut text, c, first);239                    if c.abs() != 1 {240                        text.push_str(&c.abs().to_string());241                        text.push(' ');242                    }243                    text.push_str(&format!("a(level-{})", back + 1));244                }245                if text.is_empty() {246                    text.push('0');247                }248                format!("a(level) = {text}")249            }250        }251    }252}253254/// A cost tier of the catalog.255#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]256pub enum Tier {257    /// The closed measures on both axes.258    Closed,259    /// The profile measures on both axes.260    Convolved,261    /// The grid measures on the side axis.262    SideGrid,263    /// The grid measures on the level axis.264    LevelGrid,265}266267impl Tier {268    /// Every tier, cheapest first.269    pub const ALL: [Tier; 4] = [270        Tier::Closed,271        Tier::Convolved,272        Tier::SideGrid,273        Tier::LevelGrid,274    ];275    /// Returns the tier's one-word name.276    pub fn slug(self) -> &'static str {277        match self {278            Tier::Closed => "closed",279            Tier::Convolved => "convolved",280            Tier::SideGrid => "side",281            Tier::LevelGrid => "level",282        }283    }284    /// Parses a one-word name back into its tier, or an error for any other word.285    pub fn parse(slug: &str) -> Result<Tier> {286        Tier::ALL287            .into_iter()288            .find(|tier| tier.slug() == slug)289            .map_or_else(|| value_error(format!("unknown tier {slug:?}.")), Ok)290    }291    fn cost(self) -> Cost {292        match self {293            Tier::Closed => Cost::Closed,294            Tier::Convolved => Cost::Convolved,295            _ => Cost::Grid,296        }297    }298    fn axes(self) -> &'static [Axis] {299        match self {300            Tier::SideGrid => &[Axis::Side],301            Tier::LevelGrid => &[Axis::Level],302            _ => &Axis::ALL,303        }304    }305}306307/// One row of the catalog: a design sequence with its terms, its closed form and its record.308#[derive(Clone, Debug, PartialEq, Eq)]309pub struct Sequence {310    /// The sequence's address.311    pub key: Key,312    /// The first terms.313    pub terms: Vec<i128>,314    /// Whether the cell budget or a u128 stopped the terms short.315    pub capped: bool,316    /// The closed form, when one is known.317    pub closed: Option<Closed>,318    /// The record the terms match, with the record's index less the ledger's.319    pub record: Option<(&'static Record, i32)>,320    /// The status of the match: the record's when the record names this key, else a collision to explain.321    pub tag: Option<Tag>,322}323324impl Sequence {325    fn mentions(&self, needle: &str) -> bool {326        self.key.name().contains(needle)327            || self.record.is_some_and(|(record, _)| {328                record.id.to_lowercase().contains(needle)329                    || record.name.to_lowercase().contains(needle)330            })331    }332}333334/// Returns the designs of a dimension and base, the least code of every orbit, walked once and cached, or an error past the walk limit.335///336/// ```337/// assert_eq!(ledger::designs(2, 2).unwrap(), [0, 1, 3, 6, 7, 15]);338/// assert_eq!(ledger::designs(2, 3).unwrap().len(), 26);339/// ```340pub fn designs(dimension: usize, base: usize) -> Result<&'static [u128]> {341    static CACHE: OnceLock<Mutex<Walked>> = OnceLock::new();342    let cache = CACHE.get_or_init(|| Mutex::new(BTreeMap::new()));343    let mut guard = cache.lock().expect("the design cache is not poisoned");344    if let Some(codes) = guard.get(&(dimension, base)) {345        return Ok(codes);346    }347    let codes: Vec<u128> = baseq::representatives(base, dimension)?348        .into_iter()349        .map(|(code, _)| code.get())350        .collect();351    let leaked: &'static [u128] = Box::leak(codes.into_boxed_slice());352    guard.insert((dimension, base), leaked);353    Ok(leaked)354}355356/// Lists every key of a tier: the designs of every space, the measures of the tier's cost that apply, on the tier's axes.357pub fn keys(tier: Tier) -> Vec<Key> {358    let mut out = Vec::new();359    for (dimension, base) in SPACES {360        let codes = designs(dimension, base).expect("the ledger spaces are walkable");361        for &code in codes {362            for measure in Measure::ALL {363                if measure.cost() != tier.cost() || !measure.applies(dimension, base) {364                    continue;365                }366                for &axis in tier.axes() {367                    out.push(Key::new(code, dimension, base, measure, axis));368                }369            }370        }371    }372    out373}374375fn attach(key: &Key, terms: &[i128]) -> Option<(&'static Record, i32)> {376    if terms.len() < 4 || terms.iter().all(|&term| term == terms[0]) {377        return None;378    }379    let found = identify(terms);380    found381        .iter()382        .find(|(record, _)| record.key == Some(*key))383        .or(found.first())384        .map(|&(record, shift)| (record, shift - key.axis.start()))385}386387/// Reads one design sequence: its terms within the budget, its closed form and the record it matches.388pub fn sequence(key: &Key, count: usize, cells: u128) -> Result<Sequence> {389    let (terms, capped) = terms(key, count, cells)?;390    let closed = closed(key)?;391    let record = attach(key, &terms);392    let tag = record.map(|(record, _)| {393        if record.key == Some(*key) {394            record.status395        } else {396            Tag::Conjecture397        }398    });399    Ok(Sequence {400        key: *key,401        terms,402        capped,403        closed,404        record,405        tag,406    })407}408409/// Reads every sequence of a tier at the count of terms, within the standing cell budget.410pub fn catalog(tier: Tier, count: usize) -> Vec<Sequence> {411    keys(tier)412        .iter()413        .filter_map(|key| sequence(key, count, BUDGET).ok())414        .collect()415}416417/// Parses integers separated by commas or spaces, or none when a token is not one.418pub fn numbers(text: &str) -> Option<Vec<i128>> {419    let tokens: Vec<&str> = text420        .split(|c: char| c == ',' || c.is_whitespace())421        .filter(|token| !token.is_empty())422        .collect();423    if tokens.is_empty() {424        return None;425    }426    tokens.iter().map(|token| token.parse().ok()).collect()427}428429/// Finds the catalog rows a query names: the rows holding the typed terms as a window, or the rows whose name or record holds the typed fragment.430pub fn search(catalog: &[Sequence], query: &str) -> Vec<usize> {431    let query = query.trim();432    if query.is_empty() {433        return (0..catalog.len()).collect();434    }435    if let Some(window) = numbers(query) {436        return catalog437            .iter()438            .enumerate()439            .filter(|(_, row)| {440                row.terms441                    .windows(window.len())442                    .any(|w| w == window.as_slice())443            })444            .map(|(index, _)| index)445            .collect();446    }447    let needle = query.to_lowercase();448    catalog449        .iter()450        .enumerate()451        .filter(|(_, row)| row.mentions(&needle))452        .map(|(index, _)| index)453        .collect()454}455456#[cfg(test)]457mod tests {458    use super::*;459460    #[test]461    fn the_classics_read_their_records() {462        let carpet = sequence(&Key::new(7, 2, 2, Measure::Fills, Axis::Side), 4, BUDGET).unwrap();463        assert_eq!(carpet.terms, [8, 21, 40, 65]);464        assert_eq!(carpet.record.map(|(r, s)| (r.id, s)), Some(("A000567", 0)));465        assert_eq!(carpet.tag, Some(Tag::Proved));466        assert_eq!(carpet.closed.unwrap().text(), "3k^2 - 2k");467        let tree = sequence(&Key::new(3, 2, 2, Measure::Fills, Axis::Side), 4, BUDGET).unwrap();468        assert_eq!(tree.terms[..3], [6, 15, 28]);469        assert_eq!(tree.record.map(|(r, s)| (r.id, s)), Some(("A000384", 0)));470        let sponge = sequence(471            &Key::new(23, 3, 2, Measure::Surface, Axis::Level),472            3,473            BUDGET,474        )475        .unwrap();476        assert_eq!(sponge.terms, [72, 1056, 18048]);477        assert_eq!(478            sponge.closed.unwrap().text(),479            "a(level) = 28 a(level-1) - 160 a(level-2)"480        );481        let slice = sequence(482            &Key::new(23, 3, 2, Measure::Triangles, Axis::Level),483            8,484            BUDGET,485        )486        .unwrap();487        assert_eq!(slice.terms, [42, 306, 2250, 16578]);488        assert!(slice.capped);489        assert_eq!(slice.record.map(|(r, s)| (r.id, s)), Some(("A299916", 1)));490        let void = sequence(&Key::new(9, 2, 2, Measure::Voids, Axis::Side), 3, BUDGET).unwrap();491        assert_eq!(void.closed.unwrap().text(), "2k^2 - 2k");492        assert_eq!(void.terms, [4, 12, 24]);493    }494495    #[test]496    fn the_keys_of_the_closed_tier_cover_every_space() {497        let closed = keys(Tier::Closed);498        assert_eq!(closed.len(), 1282 * 3 * 2);499        assert_eq!(keys(Tier::Convolved).len(), (1282 - 3 - 4 - 6 - 8) * 2 * 2);500        assert!(closed.iter().all(|key| key.measure.cost() == Cost::Closed));501        assert!(designs(3, 3).is_err());502    }503504    #[test]505    fn the_search_finds_terms_and_names() {506        let rows: Vec<Sequence> = [507            Key::new(7, 2, 2, Measure::Fills, Axis::Level),508            Key::new(7, 2, 2, Measure::Surface, Axis::Level),509            Key::new(23, 3, 2, Measure::Fills, Axis::Level),510        ]511        .iter()512        .map(|key| sequence(key, 5, BUDGET).unwrap())513        .collect();514        assert_eq!(search(&rows, "64, 512"), [0]);515        assert_eq!(search(&rows, "80 496"), [1]);516        assert_eq!(search(&rows, "dim=3_code=23"), [2]);517        assert_eq!(search(&rows, "A381517"), [1]);518        assert_eq!(search(&rows, "surface"), [1]);519        assert_eq!(search(&rows, ""), [0, 1, 2]);520        assert!(search(&rows, "5, 6, 7").is_empty());521        assert_eq!(numbers("1, 2 3"), Some(vec![1, 2, 3]));522        assert_eq!(numbers("1, x"), None);523    }524525    #[test]526    fn the_closed_forms_spell_themselves() {527        assert_eq!(Closed::Power(8).text(), "8^level");528        assert_eq!(Closed::Difference(9, 8).text(), "9^level - 8^level");529        assert_eq!(Closed::Polynomial(vec![1, -2, 2]).text(), "2k^2 - 2k + 1");530        assert_eq!(Closed::Polynomial(vec![0, 0, 1]).text(), "k^2");531        assert_eq!(Closed::Polynomial(vec![-1, 0, -1]).text(), "-k^2 - 1");532        assert_eq!(Closed::Polynomial(vec![0]).text(), "0");533        assert_eq!(534            Closed::Recurrence(vec![11, -24]).text(),535            "a(level) = 11 a(level-1) - 24 a(level-2)"536        );537        assert_eq!(Closed::Recurrence(vec![1]).text(), "a(level) = a(level-1)");538        assert_eq!(Closed::Recurrence(vec![0]).text(), "a(level) = 0");539        assert_eq!(Axis::Side.place(0, 3), (3, 1));540        assert_eq!(Axis::Level.place(2, 3), (3, 3));541        assert_eq!(Tier::parse("side").unwrap(), Tier::SideGrid);542        assert!(Axis::parse("depth").is_err());543    }544}