From 8286a9dc4803dd0165846acfb105f28c662dceb0 Mon Sep 17 00:00:00 2001 From: pommicket Date: Fri, 6 Sep 2024 14:07:56 -0400 Subject: row-limit search --- src/main.rs | 191 ++++++++++++++++++++++++++++++++++++++++++++++-------------- 1 file changed, 148 insertions(+), 43 deletions(-) (limited to 'src') diff --git a/src/main.rs b/src/main.rs index 8be934d..2d54fc7 100644 --- a/src/main.rs +++ b/src/main.rs @@ -1,3 +1,4 @@ +use num_bigint::BigUint; use std::ffi::OsString; use std::process::ExitCode; @@ -54,27 +55,67 @@ fn superscript(number: &str) -> String { .collect() } -fn main() -> ExitCode { - let args: Vec = std::env::args_os().collect(); - if args.len() > 2 { - eprintln!("Please provide at most 1 argument (power of 10 to search up to)."); - return ExitCode::FAILURE; +#[derive(Clone, Copy)] +struct PascalEntry { + // row choose col mod 2^64 + value: u64, + row_lo: u16, + row_hi: u32, + col: u16, +} + +impl PascalEntry { + fn new(value: u64, row: u64, col: u16) -> Self { + assert!(row < (1 << 48)); + Self { + value, + row_lo: row as _, + row_hi: (row >> 16) as _, + col, + } } - let power_of_10: Option = match args.get(1) { - Some(s) => s.clone().into_string().ok().and_then(|x| x.parse().ok()), - None => Some(35), - }; - let Some(power_of_10) = power_of_10 else { - eprintln!("Argument must be a nonnegative integer"); - return ExitCode::FAILURE; - }; - if power_of_10 > usize::MAX / 4 - || (power_of_10 as f64 * f64::log2(10.0)) as usize + 10 > size_of::() * 8 - { - eprintln!("Power of 10 is too large for integer type. You will have to increase the size of UInt in the source code."); - return ExitCode::FAILURE; + fn row(self) -> u64 { + u64::from(self.row_lo) | u64::from(self.row_hi) << 16 } + fn full_value(self) -> BigUint { + let row: u64 = self.row(); + let col: u64 = self.col.into(); + let mut value = BigUint::from(1u8); + for r in row - col + 1..=row { + value *= BigUint::from(r); + } + for r in 1..=col { + value /= BigUint::from(r); + } + value + } +} + +fn find_duplicates_in(entries: &mut [PascalEntry]) { + entries.sort_by_key(|x| x.value); + for e in entries.chunk_by(|a, b| a.value == b.value) { + if e.len() == 1 { + continue; + } + for i in 0..e.len() { + for j in i + 1..e.len() { + if e[i].full_value() != e[j].full_value() { + continue; + } + println!( + "({} choose {}) = {} = ({} choose {})", + e[i].row(), + e[i].col, + e[i].full_value(), + e[j].row(), + e[j].col + ); + } + } + } +} +fn search_entry_limit(power_of_10: usize) { let mut pascal_row = [UInt::from(0u8); 500]; let mut range = pascal_row.len(); println!( @@ -82,44 +123,108 @@ fn main() -> ExitCode { superscript(&format!("{power_of_10}")) ); let limit = UInt::from(10u8).pow(power_of_10 as u32); - let mut numbers: Vec = Vec::new(); + let mut entries: Vec = vec![]; pascal_row[0] = UInt::from(1u8); - for row in 1u128.. { - for i in (1..range).rev() { - pascal_row[i] += pascal_row[i - 1]; - if i > 4 && i as u128 <= row / 2 { - if is_choose_r(pascal_row[i], 2) - || is_choose_r(pascal_row[i], 3) - || is_choose_r(pascal_row[i], 4) { - println!("{}",pascal_row[i]); + for row in 1u64.. { + for col in (1..range).rev() { + pascal_row[col] += pascal_row[col - 1]; + if col > 4 && col as u64 <= row / 2 { + if is_choose_r(pascal_row[col], 2) + || is_choose_r(pascal_row[col], 3) + || is_choose_r(pascal_row[col], 4) + { + println!("FOUND DUPLICATE {}", pascal_row[col]); } - numbers.push(pascal_row[i]); + entries.push(PascalEntry::new( + pascal_row[col].digits()[0], + row, + col.try_into().expect("needs redesign: col > 65535"), + )); } - if pascal_row[i] > limit { - range = i; + if pascal_row[col] > limit { + range = col; + if col < 10 { + println!("n choose {col} exceeds limit at row {row}"); + } } } - if range <= 4 { + if range <= 5 { break; } } println!( "memory needed = {}MiB", - (numbers.len() * size_of::()) >> 20 + (entries.len() * size_of::()) >> 20 + ); + find_duplicates_in(&mut entries); +} + +fn search_row_limit(row_limit: u32) { + let row_limit = u64::from(row_limit); + let mut pascal_row = vec![0u64; row_limit as usize / 2 + 1]; + pascal_row[0] = 1; + let mut entries: Vec = vec![]; + for row in 0..row_limit { + if row > 0 && row % 2 == 0 { + pascal_row[row as usize / 2] = pascal_row[row as usize / 2 - 1].wrapping_mul(2); + } + for col in (2..=(std::cmp::max(3, row) - 1) / 2).rev() { + pascal_row[col as usize] = + pascal_row[col as usize].wrapping_add(pascal_row[col as usize - 1]); + entries.push(PascalEntry::new(pascal_row[col as usize], row, col as u16)); + } + pascal_row[1] = row; + } + println!( + "memory needed = {}MiB", + (entries.len() * size_of::()) >> 20 ); - numbers.sort(); - let mut prev = UInt::from(0u8); - let mut occurrences = 0; - for n in numbers { - if n == prev { - occurrences += 1; - } else if occurrences > 0 { - if occurrences > 1 { - println!("{prev}: {occurrences}"); + find_duplicates_in(&mut entries); +} + +fn main() -> ExitCode { + let args: Vec = std::env::args_os().collect(); + if args.len() < 2 { + eprintln!(" Usage: pascal entry-limit

— search all entries up to 10^p"); + eprintln!(" pascal row-limit — search all entries up to the nth row"); + return ExitCode::FAILURE; + } + match args[1].as_os_str().to_str() { + Some("entry-limit") => { + let power_of_10: Option = match args.get(2) { + Some(s) => s.clone().into_string().ok().and_then(|x| x.parse().ok()), + None => Some(35), + }; + let Some(power_of_10) = power_of_10 else { + eprintln!("Argument must be a nonnegative integer"); + return ExitCode::FAILURE; + }; + if power_of_10 > usize::MAX / 4 + || (power_of_10 as f64 * f64::log2(10.0)) as usize + 10 > size_of::() * 8 + { + eprintln!("Power of 10 is too large for integer type. You will have to increase the size of UInt in the source code."); + return ExitCode::FAILURE; + } + search_entry_limit(power_of_10); + } + Some("row-limit") => { + let row_limit: Option = match args.get(2) { + Some(s) => s.clone().into_string().ok().and_then(|x| x.parse().ok()), + None => Some(1000), + }; + let Some(row_limit) = row_limit else { + eprintln!("Argument must be a nonnegative integer"); + return ExitCode::FAILURE; + }; + if row_limit > 0xffff * 2 { + eprintln!("row limit too large (need to change PascalEntry type)"); + return ExitCode::FAILURE; } - occurrences = 1; + search_row_limit(row_limit); + } + _ => { + eprintln!("Bad command: {:?}", args[1]); } - prev = n; } ExitCode::SUCCESS } -- cgit v1.2.3