research-erdos.rs

1use figures::{ink, save, Board, Color};2use mrlyrs::core::error::Result;34const BASES: [u64; 3] = [3, 4, 5];5const LEAST: u32 = 3;6const LIMIT: u64 = 10_000_000;7const TERMS: usize = 29;8const TOTAL: usize = 24_973_824;9const FROBENIUS: usize = 4_330_731;10const MISSING: usize = 45_704;11const WIDTH: usize = 860;12const PITCH: usize = 29;13const GAP: usize = 3;14const FLOOR: f64 = 0.15;15const REACH: f64 = 0.6;1617fn powers() -> Vec<usize> {18    let mut terms: Vec<usize> = BASES19        .iter()20        .flat_map(|&b| (LEAST..).map(move |j| b.pow(j)).take_while(|&p| p <= LIMIT))21        .map(|p| p as usize)22        .collect();23    terms.sort_unstable();24    terms25}2627fn shift_or(bits: &mut [u64], a: usize, top: usize) {28    let (q, r) = (a / 64, a % 64);29    for i in (q..=top / 64).rev() {30        let mut word = bits[i - q] << r;31        if r > 0 && i > q {32            word |= bits[i - q - 1] >> (64 - r);33        }34        bits[i] |= word;35    }36}3738fn has(bits: &[u64], k: usize) -> bool {39    bits[k / 64] >> (k % 64) & 1 == 140}4142fn count(bits: &[u64], lo: usize, hi: usize) -> usize {43    if lo >= hi {44        return 0;45    }46    let (a, b) = (lo / 64, (hi - 1) / 64);47    let head = !0u64 << (lo % 64);48    let tail = !0u64 >> (63 - (hi - 1) % 64);49    if a == b {50        return (bits[a] & head & tail).count_ones() as usize;51    }52    let inner: u32 = bits[a + 1..b].iter().map(|w| w.count_ones()).sum();53    (inner + (bits[a] & head).count_ones() + (bits[b] & tail).count_ones()) as usize54}5556fn shares(bits: &[u64], total: usize) -> Vec<f64> {57    let span = total + 1;58    let mut row = vec![0.0; WIDTH];59    for c in 0..WIDTH / 2 {60        let (lo, hi) = if span >= WIDTH {61            (c * span / WIDTH, ((c + 1) * span).div_ceil(WIDTH))62        } else {63            let k = (2 * c + 1) * span / (2 * WIDTH);64            (k, k + 1)65        };66        let share = count(bits, lo, hi) as f64 / (hi - lo) as f64;67        row[c] = share;68        row[WIDTH - 1 - c] = share;69    }70    row71}7273fn tone(share: f64) -> Option<Color> {74    if share >= 1.0 {75        Some(ink::blue())76    } else if share > 0.0 {77        Some(ink::mix(ink::ground(), ink::dim(), FLOOR + REACH * share))78    } else {79        None80    }81}8283fn paint(board: &mut Board, row: &[f64], x: usize, y: usize, h: usize) {84    let mut start = 0;85    for c in 1..=row.len() {86        if c < row.len() && tone(row[c]) == tone(row[start]) {87            continue;88        }89        if let Some(tone) = tone(row[start]) {90            board.rect(91                (x + start) as f64,92                y as f64,93                (c - start) as f64,94                h as f64,95                tone,96            );97        }98        start = c;99    }100}101102fn main() -> Result<()> {103    let terms = powers();104    assert_eq!(terms.len(), TERMS);105    assert_eq!((terms[0], terms[TERMS - 1]), (27, 9_765_625));106    let mut board = Board::square();107    let x = (board.width - WIDTH) / 2;108    let top = (board.height - (TERMS * PITCH - GAP)) / 2;109    let mut bits = vec![0u64; TOTAL / 64 + 2];110    bits[0] = 1;111    let mut total = 0;112    for (n, &a) in terms.iter().enumerate() {113        total += a;114        shift_or(&mut bits, a, total);115        assert!(has(&bits, 0) && has(&bits, total));116        let row = shares(&bits, total);117        paint(&mut board, &row, x, top + n * PITCH, PITCH - GAP);118    }119    assert_eq!(total, TOTAL);120    assert!((0..=TOTAL / 2).all(|k| has(&bits, k) == has(&bits, TOTAL - k)));121    let hole = (0..=TOTAL / 2).rev().find(|&k| !has(&bits, k));122    assert_eq!(hole, Some(FROBENIUS));123    assert_eq!(FROBENIUS - count(&bits, 1, FROBENIUS + 1), MISSING);124    assert_eq!(125        count(&bits, FROBENIUS + 1, TOTAL - FROBENIUS),126        TOTAL - 2 * FROBENIUS - 1127    );128    save("research-erdos", &board)?;129    Ok(())130}