diff options
| -rw-r--r-- | README.md | 5 | ||||
| -rw-r--r-- | src/main.rs | 44 |
2 files changed, 49 insertions, 0 deletions
@@ -28,6 +28,8 @@ Also an infinite family of other solutions is known $${F_{2i+2} F_{2i+3}\choose F_{2i}F_{2i+3}} = {F_{2i+2} F_{2i+3} -1 \choose F_{2i}F_{2i+3} +1}$$ +where $F_i$ is the $i$th Fibonacci number. + De Weger did a computer search up to ${n\choose k} < 10^{30}$ in 1995. Now that we have faster computers we can go higher — and we can say for certain that the only solutions up to ${n\choose k}<10^{42}$ are the ones found by de Weger: namely, the ones in the infinite @@ -64,3 +66,6 @@ $${33551 \choose 12816} = {33552 \choose 12815} \approx 6.0 \times 10^{9687}$$ Again we run into a memory bottleneck — searching this far required 14 GB of memory. +We might suspect that other sporadic solutions (if they exist) have small values of $l$, seeing +as the two known sporadic solutions have $l=5,8$. Searching with $l\leq 30, n,m < 3\times 10^7$ (arguments `col-limit 30000000 30`) +uses 13GB of memory and yields no more solutions; and the same is true of searching with $l\leq 10, n,m < 10^8$. diff --git a/src/main.rs b/src/main.rs index bd83485..f7b4053 100644 --- a/src/main.rs +++ b/src/main.rs @@ -2,6 +2,7 @@ use num_bigint::BigUint; use std::ffi::OsString; use std::process::ExitCode; +use std::cmp::{min, max}; // bnum seems to be slightly faster than ruint, // and 3x faster than uint. @@ -161,6 +162,7 @@ fn search_entry_limit(power_of_10: usize) { } fn search_row_limit(row_limit: u32) { + println!("Searching up to row {row_limit}"); let row_limit = u64::from(row_limit); let mut pascal_row = vec![0u64; row_limit as usize / 2 + 1]; pascal_row[0] = 1; @@ -183,6 +185,29 @@ fn search_row_limit(row_limit: u32) { find_duplicates_in(&mut entries); } +fn search_col_limit(row_limit: u64, col_limit: u16) { + println!("Searching up to column {col_limit} in rows up to {row_limit}"); + let mut pascal_row = vec![0u64; row_limit as usize / 2 + 1]; + pascal_row[0] = 1; + let mut entries: Vec<PascalEntry> = 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..=min(u64::from(col_limit), (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::<PascalEntry>()) >> 20 + ); + find_duplicates_in(&mut entries); +} + fn main() -> ExitCode { let args: Vec<OsString> = std::env::args_os().collect(); if args.len() < 2 { @@ -223,6 +248,25 @@ fn main() -> ExitCode { } search_row_limit(row_limit); } + Some("col-limit") => { + let row_limit: Option<u64> = match args.get(2) { + Some(s) => s.clone().into_string().ok().and_then(|x| x.parse().ok()), + None => Some(100_000), + }; + let col_limit: Option<u16> = match args.get(3) { + Some(s) => s.clone().into_string().ok().and_then(|x| x.parse().ok()), + None => Some(30), + }; + let Some(row_limit) = row_limit else { + eprintln!("row limit must be a nonnegative integer"); + return ExitCode::FAILURE; + }; + let Some(col_limit) = col_limit else { + eprintln!("column limit must be a nonnegative integer < 65536"); + return ExitCode::FAILURE; + }; + search_col_limit(row_limit, col_limit); + } _ => { eprintln!("Bad command: {:?}", args[1]); } |