hunt.rs
19.2 kB · rust · 663 lines
1use crate::census::{self, Census, CHAMPIONS};2use crate::rows::{Row, Sheet, Stop, CAP, CEILING, DEEP};3use mrlylab::ledger::Tier;45pub const BANDS: [i128; 5] = [10, 100, 1_000, 10_000, CEILING];6pub const TAIL: i128 = 30_000;7pub const MODULI: i128 = 64;8pub const SMALL: i128 = 1_000;910fn fold<'a>(sets: impl Iterator<Item = &'a Vec<i128>>) -> Vec<u32> {11 let mut counts = vec![0u32; CEILING as usize + 1];12 for set in sets {13 for &term in set {14 counts[term as usize] += 1;15 }16 }17 counts18}1920fn seen(counts: &[u32]) -> usize {21 counts[1..].iter().filter(|&&count| count > 0).count()22}2324fn gap(counts: &[u32]) -> usize {25 counts[1..]26 .iter()27 .position(|&count| count == 0)28 .map_or(0, |index| index + 1)29}3031fn longest(counts: &[u32]) -> usize {32 let mut best = 0;33 let mut here = 0;34 for &count in &counts[1..] {35 here = if count > 0 { here + 1 } else { 0 };36 best = best.max(here);37 }38 best39}4041fn inside(window: &[i128]) -> Vec<i128> {42 let mut out: Vec<i128> = window43 .iter()44 .copied()45 .filter(|term| (1..=CEILING).contains(term))46 .collect();47 out.sort_unstable();48 out.dedup();49 out50}5152fn edge(terms: &[i128]) -> Option<usize> {53 let mut previous: Option<i128> = None;54 for (index, &term) in terms.iter().enumerate() {55 if previous.is_some_and(|last| term <= last) {56 return None;57 }58 if term > CEILING {59 return Some(index);60 }61 previous = Some(term);62 }63 None64}6566pub fn degree(head: &[i128]) -> Option<usize> {67 let mut layer = head.to_vec();68 for order in 0..head.len() {69 if layer.len() < 2 {70 return None;71 }72 if layer.iter().all(|&value| value == layer[0]) {73 return Some(order);74 }75 layer = layer.windows(2).map(|pair| pair[1] - pair[0]).collect();76 }77 None78}7980pub fn extend(head: &[i128], length: usize) -> Option<Vec<i128>> {81 let order = degree(head)?;82 let mut table = vec![head.to_vec()];83 for _ in 0..order {84 let last: Vec<i128> = table85 .last()?86 .windows(2)87 .map(|pair| pair[1] - pair[0])88 .collect();89 table.push(last);90 }91 let mut ends: Vec<i128> = table92 .iter()93 .map(|layer| *layer.last().expect("a difference layer is nonempty"))94 .collect();95 let mut out = head.to_vec();96 while out.len() < length {97 for index in (0..order).rev() {98 ends[index] = ends[index].checked_add(ends[index + 1])?;99 }100 out.push(ends[0]);101 }102 out.truncate(length);103 Some(out)104}105106pub fn rebuild(row: &Row) -> Option<Vec<i128>> {107 let terms = extend(&row.head, CAP)?;108 let window = match row.stop {109 Stop::Cap => terms,110 Stop::Ceiling => terms[..=edge(&terms)?].to_vec(),111 Stop::Budget => return None,112 };113 Some(inside(&window))114}115116fn factors() -> (Vec<u32>, Vec<u32>, Vec<i128>) {117 let size = CEILING as usize + 1;118 let mut great = vec![0u32; size];119 let mut divisors = vec![0u32; size];120 for step in 1..size {121 for slot in (step..size).step_by(step) {122 divisors[slot] += 1;123 }124 }125 for value in 2..size {126 if great[value] == 0 {127 for slot in (value..size).step_by(value) {128 great[slot] = value as u32;129 }130 }131 }132 let primes = (2..size)133 .filter(|&value| great[value] == value as u32)134 .map(|value| value as i128)135 .collect();136 (great, divisors, primes)137}138139fn perfect() -> Vec<i128> {140 let mut out = Vec::new();141 let mut base = 2i128;142 while base * base <= CEILING {143 let mut value = base * base;144 while value <= CEILING {145 out.push(value);146 value *= base;147 }148 base += 1;149 }150 out.sort_unstable();151 out.dedup();152 out153}154155fn mean(counts: &[u32], values: &[i128]) -> f64 {156 values157 .iter()158 .map(|&value| counts[value as usize] as f64)159 .sum::<f64>()160 / values.len() as f64161}162163fn family(power: u32) -> Vec<i128> {164 let mut out = Vec::new();165 let mut root = 1i128;166 while root.pow(power) <= CEILING {167 out.push(root.pow(power));168 root += 1;169 }170 out171}172173fn depth(sheet: &Sheet, book: &Census) {174 println!("DEPTH");175 let heads: Vec<Vec<i128>> = sheet.rows.iter().map(|row| inside(&row.head)).collect();176 let short = fold(heads.iter());177 let shallow = fold(sheet.rows.iter().map(|row| &row.shallow));178 let dropped = fold(sheet.rows.iter().map(|row| &row.tail));179 for (name, counts) in [("8", &short), ("32", &shallow), ("48", &book.counts)] {180 println!(181 "depth window {name} written {} missed {} first miss {}",182 seen(counts),183 CEILING as usize - seen(counts),184 gap(counts)185 );186 }187 let full = seen(&book.counts);188 println!(189 "depth reached only past term 8 {} only past term 32 {}",190 full - seen(&short),191 full - seen(&shallow)192 );193 let carried: u64 = dropped.iter().map(|&count| count as u64).sum();194 println!(195 "depth without each row's first term incidences {carried} of {} lost {} written {} never {}",196 book.incidences,197 book.incidences - carried,198 seen(&dropped),199 census::WINDOWS200 .iter()201 .map(|&window| dropped[1..=window].iter().filter(|&&count| count == 0).count().to_string())202 .collect::<Vec<_>>()203 .join(" ")204 );205 let book = Census {206 counts: dropped,207 incidences: 0,208 repeats: 0,209 low: 0,210 };211 println!(212 "depth without each row's first term leaders {}",213 census::champions(&book, 4)214 .iter()215 .map(|(value, count)| format!("{value} {count}"))216 .collect::<Vec<_>>()217 .join(" ")218 );219}220221fn model(sheet: &Sheet) {222 println!("MODEL");223 let mut orders = [0usize; 7];224 for row in &sheet.rows {225 if let Some(order) = degree(&row.head) {226 orders[order] += 1;227 }228 }229 println!(230 "model rows with a head degree at most 6 {} by degree {}",231 orders.iter().sum::<usize>(),232 orders233 .iter()234 .map(|count| count.to_string())235 .collect::<Vec<_>>()236 .join(" ")237 );238 for stop in [Stop::Cap, Stop::Ceiling, Stop::Budget] {239 let batch: Vec<&Row> = sheet240 .rows241 .iter()242 .filter(|row| row.stop == stop && degree(&row.head).is_some())243 .collect();244 let built: Vec<Option<Vec<i128>>> = batch.iter().map(|row| rebuild(row)).collect();245 let tested = built.iter().filter(|slot| slot.is_some()).count();246 let pass = batch247 .iter()248 .zip(&built)249 .filter(|(row, slot)| slot.as_ref().is_some_and(|terms| *terms == row.written))250 .count();251 let mut failed: Vec<usize> = batch252 .iter()253 .zip(&built)254 .filter(|(row, slot)| slot.as_ref().is_some_and(|terms| *terms != row.written))255 .filter_map(|(row, _)| degree(&row.head))256 .collect();257 failed.sort_unstable();258 failed.dedup();259 println!(260 "model rebuild stop {} rows {} tested {tested} pass {pass} fail {} failing degrees {}",261 stop.slug(),262 batch.len(),263 tested - pass,264 failed265 .iter()266 .map(|order| order.to_string())267 .collect::<Vec<_>>()268 .join(" ")269 );270 }271}272273fn deeper(sheet: &Sheet, book: &Census) {274 println!("DEEPER");275 let mut counts = book.counts.clone();276 let mut checked = 0;277 let mut used = 0;278 for row in &sheet.rows {279 if row.stop != Stop::Cap {280 continue;281 }282 let Some(built) = rebuild(row) else {283 continue;284 };285 checked += 1;286 if built != row.written {287 continue;288 }289 let Some(terms) = extend(&row.head, DEEP) else {290 continue;291 };292 used += 1;293 for term in inside(&terms[CAP..]) {294 counts[term as usize] += 1;295 }296 }297 println!(298 "deeper cap rows rebuilt {checked} extended {used} of {}",299 sheet300 .rows301 .iter()302 .filter(|row| row.stop == Stop::Cap)303 .count()304 );305 println!(306 "deeper window {DEEP} written at least {} first miss {} longest written run at least {}",307 seen(&counts),308 gap(&counts),309 longest(&counts)310 );311 let squares = family(2);312 println!(313 "deeper squares at least {} of {} first missed square {}",314 squares315 .iter()316 .filter(|&&value| counts[value as usize] > 0)317 .count(),318 squares.len(),319 squares320 .iter()321 .find(|&&value| counts[value as usize] == 0)322 .copied()323 .unwrap_or(0)324 );325}326327fn arithmetic(sheet: &Sheet, book: &Census) {328 println!("ARITHMETIC");329 let counts = &book.counts;330 for power in 2u32..=6 {331 let batch = family(power);332 let written: Vec<i128> = batch333 .iter()334 .copied()335 .filter(|&value| counts[value as usize] > 0)336 .collect();337 println!(338 "arith power {power} written {} of {} first missed {} largest written {}",339 written.len(),340 batch.len(),341 batch342 .iter()343 .find(|&&value| counts[value as usize] == 0)344 .copied()345 .unwrap_or(0),346 written.last().copied().unwrap_or(0)347 );348 }349 let powers = perfect();350 let carried: u64 = powers351 .iter()352 .map(|&value| counts[value as usize] as u64)353 .sum();354 let share = carried as f64 / book.incidences as f64;355 let density = powers.len() as f64 / CEILING as f64;356 println!(357 "arith perfect powers {} incidences {carried} share {share:.4} against a density {density:.6} ratio {:.2}",358 powers.len(),359 share / density360 );361 let squares = family(2);362 let top = squares363 .iter()364 .copied()365 .filter(|&value| counts[value as usize] > 0)366 .next_back()367 .unwrap_or(0);368 let writers = census::writers(sheet, top);369 println!(370 "arith largest written square {top} rows {} {}",371 writers.len(),372 writers373 .iter()374 .map(|row| row.name.as_str())375 .collect::<Vec<_>>()376 .join(" ")377 );378 println!(379 "arith square frontier {}",380 (96i128..=100)381 .map(|root| format!("{root} rows {}", counts[(root * root) as usize]))382 .collect::<Vec<_>>()383 .join(" ")384 );385 let (great, divisors, primes) = factors();386 let written: Vec<i128> = primes387 .iter()388 .copied()389 .filter(|&value| counts[value as usize] > 0)390 .collect();391 println!(392 "arith primes written {} of {} first missed {} above 10000 {} of {}",393 written.len(),394 primes.len(),395 primes396 .iter()397 .find(|&&value| counts[value as usize] == 0)398 .copied()399 .unwrap_or(0),400 written.iter().filter(|&&value| value > 10_000).count(),401 primes.iter().filter(|&&value| value > 10_000).count()402 );403 let mut classes = 0;404 let mut empty = 0;405 for modulus in 2..=MODULI {406 for residue in 0..modulus {407 classes += 1;408 let first = 10_000 + (residue - 10_000).rem_euclid(modulus);409 if !(first..=CEILING)410 .step_by(modulus as usize)411 .any(|value| counts[value as usize] > 0)412 {413 empty += 1;414 }415 }416 }417 println!("arith residue classes mod 2..{MODULI} on 10000..{CEILING} {classes} with no written integer {empty}");418 for modulus in [6i128, 12] {419 let mut tally = vec![0usize; modulus as usize];420 for value in 10_000..=CEILING {421 if counts[value as usize] > 0 {422 tally[(value % modulus) as usize] += 1;423 }424 }425 let high = tally426 .iter()427 .max()428 .copied()429 .expect("a residue tally is nonempty");430 let low = tally431 .iter()432 .min()433 .copied()434 .expect("a residue tally is nonempty");435 println!(436 "arith mod {modulus} written by residue {} high {high} low {low} ratio {:.2}",437 tally438 .iter()439 .map(|count| count.to_string())440 .collect::<Vec<_>>()441 .join(" "),442 high as f64 / low as f64443 );444 }445 let mut floor = 1i128;446 for &roof in &BANDS {447 let band: Vec<i128> = (10_000..=CEILING)448 .filter(|&value| {449 i128::from(great[value as usize]) > floor450 && i128::from(great[value as usize]) <= roof451 })452 .collect();453 println!(454 "arith greatest prime factor in {floor}..{roof} size {} written share {:.4}",455 band.len(),456 band.iter()457 .filter(|&&value| counts[value as usize] > 0)458 .count() as f64459 / band.len() as f64460 );461 floor = roof;462 }463 let all: Vec<i128> = (1..=SMALL).collect();464 let square: Vec<i128> = squares465 .iter()466 .copied()467 .filter(|&value| value <= SMALL)468 .collect();469 let rich: Vec<i128> = all470 .iter()471 .copied()472 .filter(|&value| divisors[value as usize] >= 8)473 .collect();474 let power: Vec<i128> = powers475 .iter()476 .copied()477 .filter(|&value| value <= SMALL)478 .collect();479 println!(480 "arith mean rows on 1..{SMALL} all {:.2} squares {:.2} at least eight divisors {:.2} perfect powers {:.2}",481 mean(counts, &all),482 mean(counts, &square),483 mean(counts, &rich),484 mean(counts, &power)485 );486}487488fn spectrum(sheet: &Sheet, book: &Census) {489 println!("SPECTRUM");490 let counts = &book.counts;491 let mut heights: Vec<u32> = counts[1..]492 .iter()493 .copied()494 .filter(|&count| count > 0)495 .collect();496 heights.sort_unstable();497 heights.dedup();498 println!(499 "spectrum distinct multiplicities {} max {}",500 heights.len(),501 heights.last().copied().unwrap_or(0)502 );503 let champions = census::champions(book, CHAMPIONS);504 let carried: u64 = champions.iter().map(|&(_, count)| count as u64).sum();505 let mut set: Vec<usize> = champions.iter().map(|&(value, _)| value).collect();506 set.sort_unstable();507 println!(508 "spectrum top {CHAMPIONS} incidences {carried} of {} share {:.4} largest champion {}",509 book.incidences,510 carried as f64 / book.incidences as f64,511 set.last().copied().unwrap_or(0)512 );513 println!(514 "spectrum champion set ascending {}",515 set.iter()516 .map(|value| value.to_string())517 .collect::<Vec<_>>()518 .join(" ")519 );520 let above = |level: u32| counts[1..].iter().filter(|&&count| count >= level).count();521 let ratio = above(2) as f64 / above(1) as f64;522 println!(523 "spectrum S(1) {} S(2) {} ratio {ratio:.4} geometric S(64) {:.3e} observed {}",524 above(1),525 above(2),526 above(1) as f64 * ratio.powi(63),527 above(64)528 );529 let whole: Vec<i128> = (1..=CEILING)530 .filter(|&value| counts[value as usize] > 0)531 .collect();532 let high: Vec<i128> = whole533 .iter()534 .copied()535 .filter(|&value| value >= TAIL)536 .collect();537 println!(538 "spectrum written {} above {TAIL} {}",539 whole.len(),540 high.len()541 );542 for tier in Tier::ALL {543 let mine = fold(544 sheet545 .rows546 .iter()547 .filter(|row| row.tier == tier)548 .map(|row| &row.written),549 );550 let rest = fold(551 sheet552 .rows553 .iter()554 .filter(|row| row.tier != tier)555 .map(|row| &row.written),556 );557 println!(558 "spectrum tier {} covers {} exclusive {} above {TAIL} {}",559 tier.slug(),560 seen(&mine),561 whole562 .iter()563 .filter(|&&value| mine[value as usize] > 0 && rest[value as usize] == 0)564 .count(),565 high.iter()566 .filter(|&&value| mine[value as usize] > 0)567 .count()568 );569 }570 let mut families: Vec<Vec<i128>> = sheet571 .rows572 .iter()573 .map(|row| {574 row.written575 .iter()576 .copied()577 .filter(|&value| value >= TAIL)578 .collect::<Vec<i128>>()579 })580 .filter(|set| !set.is_empty())581 .collect();582 families.sort();583 families.dedup();584 let mut owners = vec![0u32; CEILING as usize + 1];585 for set in &families {586 for &value in set {587 owners[value as usize] += 1;588 }589 }590 println!(591 "spectrum written sets above {TAIL} {} owning a tail integer alone {} covering {} of {}",592 families.len(),593 families594 .iter()595 .filter(|set| set.iter().any(|&value| owners[value as usize] == 1))596 .count(),597 high.iter()598 .filter(|&&value| owners[value as usize] == 1)599 .count(),600 high.len()601 );602 for (column, value) in [603 ("euler.side", 1i128),604 ("peak.side", 12),605 ("heights.side", 9),606 ("heights.side", 33),607 ] {608 let batch: Vec<&Row> = sheet609 .rows610 .iter()611 .filter(|row| row.name.ends_with(column))612 .collect();613 println!(614 "spectrum column {column} writes {value} in {} of {} rows",615 batch616 .iter()617 .filter(|row| row.written.binary_search(&value).is_ok())618 .count(),619 batch.len()620 );621 }622 let batch: Vec<&Row> = sheet623 .rows624 .iter()625 .filter(|row| row.name.ends_with("heights.side"))626 .collect();627 let mut tally: Vec<(i128, usize)> = (1..=100i128)628 .map(|value| {629 (630 value,631 batch632 .iter()633 .filter(|row| row.written.binary_search(&value).is_ok())634 .count(),635 )636 })637 .collect();638 tally.sort_by(|left, right| right.1.cmp(&left.1).then(left.0.cmp(&right.0)));639 tally.truncate(8);640 let mut leaders: Vec<i128> = tally.iter().map(|&(value, _)| value).collect();641 leaders.sort_unstable();642 println!(643 "spectrum heights.side leaders to 100 {} every one a multiple of eight plus one {}",644 leaders645 .iter()646 .map(|value| value.to_string())647 .collect::<Vec<_>>()648 .join(" "),649 leaders.iter().all(|value| (value - 1) % 8 == 0)650 );651}652653pub fn report(sheet: &Sheet, book: &Census) {654 depth(sheet, book);655 println!();656 model(sheet);657 println!();658 deeper(sheet, book);659 println!();660 arithmetic(sheet, book);661 println!();662 spectrum(sheet, book);663}