records.rs

1use super::{Axis, Key, Measure, Tag};2use std::sync::OnceLock;34/// One OEIS entry the tree cites, with the design sequence it names when it names one.5#[derive(Clone, Copy, Debug, PartialEq, Eq)]6pub struct Record {7    /// The OEIS id.8    pub id: &'static str,9    /// The entry's name.10    pub name: &'static str,11    /// The index of the first listed term.12    pub offset: i32,13    /// The record's index less the ledger's, where a key names the sequence.14    pub shift: i32,15    /// The first terms, as text.16    pub terms: &'static str,17    /// The status of the identification.18    pub status: Tag,19    /// The design sequence the entry names, when it names one.20    pub key: Option<Key>,21    /// The formula, or none.22    pub formula: &'static str,23    /// The generator or page that witnesses the entry.24    pub witness: &'static str,25}2627const fn record(28    id: &'static str,29    name: &'static str,30    offset: i32,31    terms: &'static str,32    status: Tag,33    formula: &'static str,34    witness: &'static str,35) -> Record {36    Record {37        id,38        name,39        offset,40        shift: 0,41        terms,42        status,43        key: None,44        formula,45        witness,46    }47}4849impl Record {50    const fn keyed(51        self,52        code: u128,53        dimension: usize,54        measure: Measure,55        axis: Axis,56        shift: i32,57    ) -> Record {58        Record {59            shift,60            key: Some(Key::new(code, dimension, 2, measure, axis)),61            ..self62        }63    }64}6566const FILLS: &str = "mrlymath::formulas::fill";67const SIDES: &str = "mrlylab::ledger::terms, the odd-side law";68const EXPOSURE: &str = "mrlymath::formulas::exposure";6970/// Every OEIS entry the tree cites, by id.71pub static RECORDS: &[Record] = &[72    record("A000029", "Number of necklaces with n beads of 2 colors, allowing turning over (bracelets)", 0, "1, 2, 3, 4, 6, 8, 13, 18, 30, 46, 78, 126", Tag::Verified, "none", "mrlymath::bang::baseq::bracelets, the base line at dim 1"),73    record("A000070", "a(n) = Sum_{k=0..n} p(k) where p(k) = number of partitions of k", 0, "1, 2, 4, 7, 12, 19, 30, 45, 67, 97, 139, 195", Tag::Verified, "none", "REFS.md"),74    record("A000244", "Powers of 3: a(n) = 3^n", 0, "1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147", Tag::Proved, "3^level", "mrlymath::three::diagonal, every admissible cut of bang dim 3, code 126 at side 2"),75    record("A000290", "The squares: a(n) = n^2", 0, "0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121", Tag::Proved, "k^2", SIDES).keyed(1, 2, Measure::Fills, Axis::Side, 0),76    record("A000351", "Powers of 5: a(n) = 5^n", 0, "1, 5, 25, 125, 625, 3125, 15625, 78125, 390625, 1953125, 9765625, 48828125", Tag::Proved, "5^level", FILLS).keyed(9, 2, Measure::Fills, Axis::Level, 0),77    record("A000370", "Number of NPN-equivalence classes of Boolean functions of n or fewer variables", 0, "1, 2, 4, 14, 222, 616126, 200253952527184", Tag::Verified, "none", "bijection.md, the NPN sibling at dim 1..4"),78    record("A000384", "Hexagonal numbers: a(n) = n*(2*n-1)", 0, "0, 1, 6, 15, 28, 45, 66, 91, 120, 153, 190, 231", Tag::Proved, "k(2k - 1)", SIDES).keyed(3, 2, Measure::Fills, Axis::Side, 0),79    record("A000420", "Powers of 7: a(n) = 7^n", 0, "1, 7, 49, 343, 2401, 16807, 117649, 823543, 5764801, 40353607, 282475249, 1977326743", Tag::Proved, "7^level", FILLS).keyed(11, 2, Measure::Fills, Axis::Level, 0),80    record("A000567", "Octagonal numbers: n*(3*n-2)", 0, "0, 1, 8, 21, 40, 65, 96, 133, 176, 225, 280, 341", Tag::Proved, "k(3k - 2)", SIDES).keyed(7, 2, Measure::Fills, Axis::Side, 0),81    record("A000578", "The cubes: a(n) = n^3", 0, "0, 1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331", Tag::Proved, "k^3", SIDES).keyed(1, 3, Measure::Fills, Axis::Side, 0),82    record("A000616", "a(-1)=1 by convention; for n >= 0, a(n) = number of irreducible Boolean functions of n variables", -1, "1, 2, 3, 6, 22, 402, 1228158, 400507806843728", Tag::Proved, "none", "mrlymath::bang::counting::sequence, bijection.md"),83    record("A001018", "Powers of 8: a(n) = 8^n", 0, "1, 8, 64, 512, 4096, 32768, 262144, 2097152, 16777216, 134217728, 1073741824, 8589934592", Tag::Proved, "8^level", FILLS).keyed(7, 2, Measure::Fills, Axis::Level, 0),84    record("A001024", "Powers of 15: a(n) = 15^n", 0, "1, 15, 225, 3375, 50625, 759375, 11390625, 170859375, 2562890625, 38443359375", Tag::Verified, "15^n", "REFS.md"),85    record("A001316", "Gould's sequence: number of odd entries in row n of Pascal's triangle", 0, "1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8", Tag::Verified, "2^wt(n)", "REFS.md"),86    record("A001481", "Numbers that are the sum of 2 squares", 1, "0, 1, 2, 4, 5, 8, 9, 10, 13, 16, 17, 18", Tag::Verified, "none", "spin.md, the ring radii of a spun square lattice"),87    record("A001844", "Centered square numbers: a(n) = 2*n*(n+1)+1", 0, "1, 5, 13, 25, 41, 61, 85, 113, 145, 181, 221, 265", Tag::Proved, "2k^2 - 2k + 1", SIDES).keyed(9, 2, Measure::Fills, Axis::Side, -1),88    record("A002407", "Cuban primes: primes which are the difference of two consecutive cubes", 1, "7, 19, 37, 61, 127, 271, 331, 397, 547, 631, 919, 1657", Tag::Verified, "none", "mrlymath::formulas::six theorems, slices.md"),89    record("A003136", "Loeschian numbers: numbers of the form x^2 + xy + y^2", 1, "0, 1, 3, 4, 7, 9, 12, 13, 16, 19, 21, 25", Tag::Verified, "none", "spin.md, the ring radii of a spun hexagonal lattice"),90    record("A003180", "Number of equivalence classes of Boolean functions of n variables under action of symmetric group", 0, "2, 4, 12, 80, 3984, 37333248, 25626412338274304", Tag::Verified, "none", "bijection.md, the axis-permutation orbits at a one-term shift"),91    record("A003215", "Hex (or centered hexagonal) numbers: 3*n*(n+1)+1", 0, "1, 7, 19, 37, 61, 91, 127, 169, 217, 271, 331, 397", Tag::Proved, "3k^2 - 3k + 1", SIDES).keyed(11, 2, Measure::Fills, Axis::Side, -1),92    record("A003463", "a(n) = (5^n - 1)/4", 0, "0, 1, 6, 31, 156, 781, 3906, 19531, 97656, 488281, 2441406, 12207031", Tag::Verified, "(5^n - 1)/4", "REFS.md"),93    record("A004016", "Theta series of planar hexagonal lattice A_2", 0, "1, 6, 0, 6, 6, 0, 0, 12, 0, 6, 0, 0", Tag::Verified, "none", "mrlydemo::ring_weights, spin.md"),94    record("A004018", "Theta series of square lattice: number of ways of writing n as a sum of 2 squares", 0, "1, 4, 4, 0, 4, 8, 0, 0, 4, 4, 8, 0", Tag::Verified, "4(d_1(n) - d_3(n))", "mrlydemo::ring_weights, spin.md"),95    record("A004662", "Powers of 3 written in base 8", 0, "1, 3, 11, 33, 121, 363, 1331, 4213, 14641, 46343, 163251, 531773", Tag::Verified, "none", "this page, a near miss of A396934 - 1"),96    record("A005418", "Number of (n-1)-bead black-white reversible strings", 1, "1, 2, 3, 6, 10, 20, 36, 72, 136, 272, 528, 1056", Tag::Verified, "none", "REFS.md"),97    record("A005728", "Number of fractions in Farey series of order n", 0, "1, 2, 3, 5, 7, 11, 13, 19, 23, 29, 33, 43", Tag::Verified, "1 + sum of phi(k) for k <= n", "mrlynum::lattice::farey, the lit nodes of the stack in farey.md"),98    record("A005898", "Centered cube numbers: n^3 + (n+1)^3", 0, "1, 9, 35, 91, 189, 341, 559, 855, 1241, 1729, 2331, 3059", Tag::Proved, "k^3 + (k - 1)^3", SIDES).keyed(129, 3, Measure::Fills, Axis::Side, -1),99    record("A009964", "Powers of 20", 0, "1, 20, 400, 8000, 160000, 3200000, 64000000, 1280000000, 25600000000, 512000000000", Tag::Proved, "20^level", FILLS).keyed(23, 3, Measure::Fills, Axis::Level, 0),100    record("A009971", "Powers of 27", 0, "1, 27, 729, 19683, 531441, 14348907, 387420489, 10460353203, 282429536481, 7625597484987", Tag::Proved, "27^level", FILLS).keyed(255, 3, Measure::Fills, Axis::Level, 0),101    record("A011934", "a(n) = abs(1^3 - 2^3 + 3^3 - 4^3 + ... + (-1)^(n+1)*n^3)", 0, "0, 1, 7, 20, 44, 81, 135, 208, 304, 425, 575, 756", Tag::Verified, "none", "this page, the parent of the bisections A103532 and A395241"),102    record("A016185", "a(n) = 9^n - 8^n", 0, "0, 1, 17, 217, 2465, 26281, 269297, 2685817, 26269505, 253202761, 2413042577, 22791125017", Tag::Proved, "9^level - 8^level", "mrlymath::formulas::void").keyed(7, 2, Measure::Voids, Axis::Level, 0),103    record("A016754", "Odd squares: a(n) = (2n+1)^2, also centered octagonal numbers", 0, "1, 9, 25, 49, 81, 121, 169, 225, 289, 361, 441, 529", Tag::Proved, "(2k - 1)^2", SIDES).keyed(15, 2, Measure::Fills, Axis::Side, -1),104    record("A016755", "Odd cubes: a(n) = (2*n + 1)^3", 0, "1, 27, 125, 343, 729, 1331, 2197, 3375, 4913, 6859, 9261, 12167", Tag::Proved, "(2k - 1)^3", SIDES).keyed(255, 3, Measure::Fills, Axis::Side, -1),105    record("A018413", "Divisors of 363", 1, "1, 3, 11, 33, 121, 363", Tag::Verified, "none", "this page, a near miss of A396934 - 1"),106    record("A034474", "a(n) = 5^n + 1", 0, "2, 6, 26, 126, 626, 3126, 15626, 78126, 390626, 1953126, 9765626, 48828126", Tag::Verified, "5^n + 1", "REFS.md"),107    record("A047999", "Sierpinski's triangle (or gasket): Pascal's triangle read by rows mod 2", 0, "1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0", Tag::Verified, "none", "coprime.md, the points i AND j = 0"),108    record("A048883", "a(n) = 3^wt(n), where wt(n) = A000120(n)", 0, "1, 3, 3, 9, 3, 9, 9, 27, 3, 9, 9, 27", Tag::Verified, "3^wt(n)", "REFS.md"),109    record("A054247", "Number of n X n binary matrices under action of dihedral group of the square D_4", 0, "1, 2, 6, 102, 8548, 4211744, 8590557312, 70368882591744, 2305843028004192256", Tag::Verified, "none", "README.md, the rigid hypercube census at dim 2"),110    record("A065473", "Decimal expansion of the strongly carefree constant: Product_{p prime} (1 - (3*p-2)/(p^3))", 0, "2, 8, 6, 7, 4, 7, 4, 2, 8, 4, 3, 4", Tag::Verified, "none", "coprime.md"),111    record("A069403", "a(n) = 2*Fibonacci(2*n+1) - 1", 0, "1, 3, 9, 25, 67, 177, 465, 1219, 3193, 8361, 21891, 57313", Tag::Verified, "2 F(2n + 1) - 1", "REFS.md"),112    record("A103532", "Number of divisors of 240^n", 0, "1, 20, 81, 208, 425, 756, 1225, 1856, 2673, 3700, 4961, 6480", Tag::Proved, "(4k - 3)k^2", SIDES).keyed(23, 3, Measure::Fills, Axis::Side, -1),113    record("A125833", "Numbers whose base-5 representation is 333333.......3", 0, "0, 3, 18, 93, 468, 2343, 11718, 58593, 292968, 1464843, 7324218, 36621093", Tag::Verified, "3(5^n - 1)/4", "REFS.md"),114    record("A128625", "Expansion of (1+3*x)/(1-5*x)", 0, "1, 8, 40, 200, 1000, 5000, 25000, 125000, 625000, 3125000, 15625000, 78125000", Tag::Verified, "8 5^(n-1) for n >= 1", "REFS.md"),115    record("A129824", "a(n) = Product_{k=0..n} (1 + binomial(n,k))", 0, "2, 4, 12, 64, 700, 17424, 1053696, 160579584, 62856336636, 63812936890000, 168895157342195152, 1169048914836855865344", Tag::Proved, "Prod_{k=0}^{n} (1 + C(n,k))", "lab/rs/design-census, the fill classes of base 2"),116    record("A141148", "Number of aperiodic ternary necklaces with n beads of each color and no adjacent beads of the same color", 1, "2, 3, 14, 65, 346, 1929, 11442, 70310, 445928, 2896239, 19186738, 129184583", Tag::Verified, "none", "REFS.md"),117    record("A154105", "a(n) = 12*n^2 + 18*n + 7", 0, "7, 37, 91, 169, 271, 397, 547, 721, 919, 1141, 1387, 1657", Tag::Verified, "12n^2 + 18n + 7", "slices.md, the centered hexagonal vertices at n = k - 1"),118    record("A192908", "Constant term in the reduction by (x^2 -> x + 1) of a polynomial family; a(n) = 2*Fibonacci(2n-2) + 1", 0, "1, 1, 3, 7, 17, 43, 111, 289, 755, 1975, 5169, 13531", Tag::Verified, "2 F(2n - 2) + 1", "REFS.md"),119    record("A229896", "Sizes of logical groups of the same integer in A229895", 1, "1, 1, 4, 1, 5, 27, 1, 7, 37, 256, 1, 9, 61, 369, 3125, 1, 11, 91, 671, 4651, 46656, 1, 13, 127, 1105, 9031, 70993, 823543, 1, 15, 169, 1695, 15961, 144495, 1273609, 16777216, 1, 17, 217, 2465, 26281, 269297, 2685817, 26269505, 387420489", Tag::Verified, "none", "this page, an interior window holding the carpet voids"),120    record("A255016", "Number of toroidal n X n binary arrays, allowing rotation and/or reflection of rows and/or columns as well as matrix transposition", 0, "1, 2, 6, 26, 805, 172112, 239123150, 1436120190288, 36028817512382026", Tag::Verified, "none", "mrlymath::bang::baseq::sequence at dim 2, bijection.md"),121    record("A268240", "Pascal's tetrahedron of trinomial coefficients read mod 2", 0, "1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1", Tag::Verified, "none", "REFS.md"),122    record("A299916", "a(n) = A299914(2n+1); the six-pointed-star holes of the Menger slice, by a comment", 0, "1, 6, 42, 306, 2250, 16578, 122202, 900882, 6641514, 48963042, 360969210, 2661166386", Tag::Verified, "a(n) = 9a(n-1) - 12a(n-2)", "mrlymath::formulas::cut_fills, slices.md").keyed(23, 3, Measure::Triangles, Axis::Level, 1),123    record("A332705", "Number of unit square faces (or surface area) of a stage-n Menger sponge", 0, "6, 72, 1056, 18048, 336384, 6531072, 129048576, 2568388608, 51267108864, 1024536870912", Tag::Proved, "2*20^level + 4*8^level", EXPOSURE).keyed(23, 3, Measure::Surface, Axis::Level, 0),124    record("A347825", "Number of ways to cut a 2 X n rectangle into rectangles with integer sides up to symmetries of the rectangle", 0, "1, 2, 6, 17, 61, 220, 883, 3597, 15232, 65130, 282294, 1229729", Tag::Verified, "none", "this page, a near miss of A396934/2"),125    record("A361870", "Array read by downward antidiagonals: nonequivalent 2-colorings of the cells of an n-dimensional hypercube with edges k cells long", 0, "2, 2, 1, 2, 2, 1, 2, 3, 2, 1, 2, 6", Tag::Verified, "none", "README.md, the rigid hypercube census"),126    record("A381517", "Perimeter of the Sierpinski carpet at iteration n", 0, "4, 16, 80, 496, 3536, 26992, 212048, 1684720, 13442768, 107437168, 859182416, 6872514544", Tag::Proved, "(4*8^level + 16*3^level)/5", EXPOSURE).keyed(7, 2, Measure::Surface, Axis::Level, 0),127    record("A395134", "Decimal expansion of the probability that the line that passes through two points selected independently and uniformly at random in a half-disk intersects the arc at two points.", 0, "4, 5, 9, 6, 2, 0, 3, 5, 3, 9, 0, 7", Tag::Verified, "1 - 16/(3 Pi^2)", "coprime.md, the complement of the A396934 density"),128    record("A395241", "a(n) = n^2*(4*n + 3)", 0, "0, 7, 44, 135, 304, 575, 972, 1519, 2240, 3159, 4300, 5687", Tag::Verified, "a(n) = n^2*(4*n + 3)", "lab/rs/oeis-terms, the b-file to n = 10000").keyed(23, 3, Measure::Voids, Axis::Side, -1),129    record("A396922", "E.g.f. A(x) satisfies A( x / A(log(A(log(A(log(A(x))))))) ) = exp(x)", 0, "1, 1, 3, 40, 1421, 87896, 7921207, 951512332, 144407735033, 26715045346048", Tag::Verified, "none", "REFS.md"),130    record("A396934", "Number of pairs (i,j) with 0 <= i,j < 2^n, i AND j = 0, and gcd(i,j) = 1", 0, "0, 2, 4, 12, 34, 122, 362, 1130, 3406, 10506, 31550, 95260", Tag::Verified, "none", "lab/rs/oeis-terms, the b-file to n = 20"),131    record("A398348", "Number of toroidal n X n X n binary arrays, allowing rotation and/or reflection of the layers along each axis as well as all permutations of the axes", 1, "2, 22, 111618, 6005363762644688, 7089215977519836239803174210135872, 10157435539019790383692007859901914095646506996125324171134976", Tag::Verified, "none", "lab/rs/oeis-terms, the b-file to n = 14"),132];133134/// Finds a record by id.135pub fn record_by_id(id: &str) -> Option<&'static Record> {136    RECORDS.iter().find(|record| record.id == id)137}138139fn parsed() -> &'static [Vec<i128>] {140    static PARSED: OnceLock<Vec<Vec<i128>>> = OnceLock::new();141    PARSED.get_or_init(|| {142        RECORDS143            .iter()144            .map(|record| {145                record146                    .terms147                    .split(',')148                    .map_while(|term| term.trim().parse().ok())149                    .collect()150            })151            .collect()152    })153}154155impl Record {156    /// Returns the listed terms that fit an i128, in order.157    pub fn parsed(&self) -> &'static [i128] {158        let at = RECORDS159            .iter()160            .position(|record| record.id == self.id)161            .expect("every record is listed");162        &parsed()[at]163    }164}165166/// Finds every record holding the terms as a window, with the record's index of the first term.167///168/// ```169/// let found = mrlylab::ledger::identify(&[6, 42, 306, 2250]);170/// assert_eq!(found.iter().map(|(r, s)| (r.id, *s)).collect::<Vec<_>>(), [("A299916", 1)]);171/// ```172pub fn identify(terms: &[i128]) -> Vec<(&'static Record, i32)> {173    if terms.is_empty() {174        return Vec::new();175    }176    let mut found: Vec<(&'static Record, i32)> = RECORDS177        .iter()178        .zip(parsed())179        .filter_map(|(record, known)| {180            known181                .windows(terms.len())182                .position(|window| window == terms)183                .map(|at| (record, record.offset + at as i32))184        })185        .collect();186    found.sort_by_key(|(record, shift)| (record.key.is_none(), shift.abs(), record.id));187    found188}189190#[cfg(test)]191mod tests {192    use super::super::{terms, BUDGET, TERMS};193    use super::*;194195    #[test]196    fn the_records_are_sorted_distinct_and_parse() {197        for pair in RECORDS.windows(2) {198            assert!(199                pair[0].id < pair[1].id,200                "{} before {}",201                pair[0].id,202                pair[1].id203            );204        }205        for record in RECORDS {206            assert!(record.parsed().len() >= 5, "{}", record.id);207            assert!(!record.name.contains('|'), "{}", record.id);208        }209        assert_eq!(RECORDS.len(), 60);210        assert_eq!(record_by_id("A398348").unwrap().parsed().len(), 5);211    }212213    #[test]214    fn every_keyed_record_reads_its_generator_at_its_shift() {215        let mut keyed = 0;216        for record in RECORDS.iter().filter(|record| record.key.is_some()) {217            let key = record.key.unwrap();218            let (got, _) = terms(&key, TERMS, BUDGET).unwrap();219            let known = record.parsed();220            let mut compared = 0;221            for (index, &term) in got.iter().enumerate() {222                let at = key.axis.start() + index as i32 + record.shift - record.offset;223                if let Some(&expected) = usize::try_from(at).ok().and_then(|at| known.get(at)) {224                    assert_eq!(term, expected, "{} at {index}", record.id);225                    compared += 1;226                }227            }228            assert!(compared >= 3, "{} compared {compared}", record.id);229            keyed += 1;230        }231        assert_eq!(keyed, 20);232    }233234    #[test]235    fn identify_returns_the_shift() {236        let ids = |terms: &[i128]| -> Vec<(&str, i32)> {237            identify(terms).iter().map(|(r, s)| (r.id, *s)).collect()238        };239        assert_eq!(ids(&[8, 21, 40, 65]), [("A000567", 2)]);240        assert_eq!(ids(&[6, 15, 28]), [("A000384", 2)]);241        assert_eq!(ids(&[72, 1056, 18048]), [("A332705", 1)]);242        assert_eq!(ids(&[1, 17, 217]), [("A016185", 1), ("A229896", 37)]);243        assert_eq!(ids(&[3, 6, 22, 402]), [("A000616", 1)]);244        assert_eq!(ids(&[4, 12, 80, 3984]), [("A003180", 1)]);245        assert_eq!(ids(&[5, 7, 11, 13]), [("A005728", 3)]);246        assert!(ids(&[5, 7, 11, 14]).is_empty());247        assert!(ids(&[]).is_empty());248    }249}