From 1427ad4a028813a677407198dd0e297a3211572b Mon Sep 17 00:00:00 2001
From: pommicket <pommicket@gmail.com>
Date: Fri, 6 Sep 2024 14:25:06 -0400
Subject: col-limit

---
 README.md   |  5 +++++
 src/main.rs | 44 ++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 49 insertions(+)

diff --git a/README.md b/README.md
index bb6fb17..63b2fc3 100644
--- a/README.md
+++ b/README.md
@@ -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]);
 		}
-- 
cgit v1.2.3