theorem.rs

1fn gcd(mut a: u64, mut b: u64) -> u64 {2    while b != 0 {3        let rest = a % b;4        a = b;5        b = rest;6    }7    a8}910fn points(q: u64, corners: &[Vec<u64>], level: u32) -> Vec<Vec<u64>> {11    let width = corners[0].len();12    let mut pts = vec![vec![0u64; width]];13    for _ in 0..level {14        let mut next = Vec::with_capacity(pts.len() * corners.len());15        for p in &pts {16            for v in corners {17                let mut x = Vec::with_capacity(width);18                for i in 0..width {19                    x.push(p[i] * q + v[i]);20                }21                next.push(x);22            }23        }24        pts = next;25    }26    pts27}2829fn common(p: &[u64]) -> u64 {30    let mut g = 0;31    for c in p {32        g = gcd(g, *c);33    }34    g35}3637fn grid(q: u64, width: usize, keep: impl Fn(&[u64]) -> bool) -> Vec<Vec<u64>> {38    let mut out = Vec::new();39    let count = (q as usize).pow(width as u32);40    for code in 0..count {41        let mut v = Vec::with_capacity(width);42        let mut rest = code as u64;43        for _ in 0..width {44            v.push(rest % q);45            rest /= q;46        }47        if keep(&v) {48            out.push(v);49        }50    }51    out52}5354#[test]55fn bracket_identity() {56    let code: u64 = 34376528265;57    let mut base6 = Vec::new();58    let mut bit = 0;59    for a in 0..6u64 {60        for b in 0..6u64 {61            if (code >> bit) & 1 == 1 {62                base6.push(vec![b, a]);63            }64            bit += 1;65        }66    }67    assert_eq!(base6.len(), 8);68    for level in 1..=6u32 {69        let q6 = points(6, &base6, level)70            .iter()71            .filter(|p| gcd(common(p), 6) == 1)72            .count() as u64;73        assert_eq!(q6, 8u64.pow(level) / 2);74    }75    let menger = grid(3, 3, |v| v.iter().filter(|d| **d == 1).count() <= 1);76    for level in 1..=4u32 {77        let q3 = points(3, &menger, level)78            .iter()79            .filter(|p| common(p) % 3 != 0)80            .count() as u64;81        assert_eq!(q3, 19 * 20u64.pow(level - 1));82    }83    let carpet = grid(3, 2, |v| v != [1, 1]);84    for level in 1..=6u32 {85        let q3 = points(3, &carpet, level)86            .iter()87            .filter(|p| common(p) % 3 != 0)88            .count() as u64;89        assert_eq!(q3, 7 * 8u64.pow(level - 1));90    }91    let vicsek = grid(3, 2, |v| v.contains(&1));92    for level in 1..=7u32 {93        let q3 = points(3, &vicsek, level)94            .iter()95            .filter(|p| common(p) % 3 != 0)96            .count() as u64;97        assert_eq!(q3, 5u64.pow(level));98    }99}100101#[test]102fn box_bound() {103    let mut designs: Vec<(u64, Vec<Vec<u64>>)> = vec![104        (2, vec![vec![0, 0], vec![0, 1], vec![1, 0]]),105        (2, vec![vec![0, 1], vec![1, 0], vec![1, 1]]),106        (3, grid(3, 2, |v| v != [1, 1])),107        (3, grid(3, 2, |v| v.contains(&1))),108        (109            3,110            grid(3, 3, |v| v.iter().filter(|d| **d == 1).count() <= 1),111        ),112        (5, vec![vec![0, 0], vec![1, 0], vec![0, 1]]),113        (9, vec![vec![0, 0], vec![1, 0], vec![0, 1]]),114        (115            6,116            vec![117                vec![0, 0],118                vec![1, 1],119                vec![2, 3],120                vec![3, 2],121                vec![4, 5],122                vec![5, 4],123                vec![1, 3],124                vec![3, 1],125            ],126        ),127    ];128    let mut state: u64 = 7;129    let mut next = || {130        state = state131            .wrapping_mul(6364136223846793005)132            .wrapping_add(1442695040888963407);133        state >> 33134    };135    while designs.len() < 48 {136        let q = 2 + next() % 9;137        let width = if next() % 3 == 2 { 3 } else { 2 };138        let cap = (q.pow(width as u32)).min(8);139        let k = 2 + next() % (cap - 1).max(1);140        let mut f: Vec<Vec<u64>> = Vec::new();141        while (f.len() as u64) < k {142            let v: Vec<u64> = (0..width).map(|_| next() % q).collect();143            if !f.contains(&v) {144                f.push(v);145            }146        }147        designs.push((q, f));148    }149    let mut checked = 0u64;150    for (q, f) in &designs {151        let k = f.len() as u64;152        let width = f[0].len() as u32;153        let mut level = 1u32;154        while k.pow(level + 1) <= 20000 && (*q as u128).pow(level + 1) < 1u128 << 60 {155            level += 1;156        }157        let pts = points(*q, f, level);158        let top = (*q as u128).pow(level).min(200) as u64;159        for m in 2..=top {160            let hits = pts.iter().filter(|p| p.iter().all(|c| c % m == 0)).count() as u128;161            let mut bound = u128::MAX;162            for h in 0..=level {163                let slab =164                    (k as u128).pow(level - h) * ((*q as u128).pow(h) / m as u128 + 1).pow(width);165                bound = bound.min(slab);166            }167            assert!(hits <= bound, "box bound violated at q={} m={}", q, m);168            checked += 1;169        }170    }171    assert!(checked > 5000);172}173174#[test]175fn cantor_dust() {176    let dust = vec![vec![0, 0], vec![0, 2], vec![2, 0], vec![2, 2]];177    for level in 1..=8u32 {178        let pts = points(3, &dust, level);179        assert_eq!(pts.iter().filter(|p| common(p) == 1).count(), 0);180        if level == 8 {181            assert_eq!(pts.iter().filter(|p| common(p) == 2).count(), 33883);182        }183    }184}