From bae0f2a2a7e6f87a550fee773e0ef9444d03d028 Mon Sep 17 00:00:00 2001
From: pommicket <pommicket@gmail.com>
Date: Fri, 6 Sep 2024 18:06:08 -0400
Subject: More efficient detection of n choose 2

---
 Cargo.lock  |  5 +++++
 Cargo.toml  |  3 ++-
 README.md   |  5 +++--
 src/main.rs | 32 ++++++++++++++++++++++++++------
 4 files changed, 36 insertions(+), 9 deletions(-)

diff --git a/Cargo.lock b/Cargo.lock
index 3f25e85..c0bc298 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -13,6 +13,10 @@ name = "bnum"
 version = "0.11.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "3e31ea183f6ee62ac8b8a8cf7feddd766317adfb13ff469de57ce033efd6a790"
+dependencies = [
+ "num-integer",
+ "num-traits",
+]
 
 [[package]]
 name = "num-bigint"
@@ -48,4 +52,5 @@ version = "0.1.0"
 dependencies = [
  "bnum",
  "num-bigint",
+ "num-integer",
 ]
diff --git a/Cargo.toml b/Cargo.toml
index da15ea0..1e1a837 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -4,5 +4,6 @@ version = "0.1.0"
 edition = "2021"
 
 [dependencies]
-bnum = "0.11.0"
+bnum = { version = "0.11.0", features = ["numtraits"] }
 num-bigint = "0.4.6"
+num-integer = "0.1.46"
diff --git a/README.md b/README.md
index 0f0dcfe..3fd4ab6 100644
--- a/README.md
+++ b/README.md
@@ -69,5 +69,6 @@ Again we run into a memory bottleneck — searching this far required 14 GB of m
 We can sidestep the large memory requirements almost entirely if we assume that sporadic solutions have
 very small values of $k$ (this is motivated by the two known sporadic solutions having $k=2$). Then we just
 go through each entry in the triangle, only storing one row in memory at a time, and do a binary search to check if
-the entry is ${n\choose k}$ for some small $k$. Using this method we can verify quickly and with just a few megabytes of memory
-that no more solutions exist with ${n\choose k}<10^{64}, n,m < 3\times 10^6, k \leq 10$ (arguments `col-limit 10`).
+the entry is ${n\choose k}$ for some small $k$. Using this method we can verify with just a few hours and megabytes of memory
+that no more solutions exist with ${n\choose k}<10^{123}, m < 3\times 10^6, k \leq 30$ (arguments `col-limit 30` after
+modifying `UInt` to be 512-bit) or with ${n\choose k}<10^{152}, m < 10^7, k = 2$.
diff --git a/src/main.rs b/src/main.rs
index 67840ab..3500847 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -1,13 +1,25 @@
 // LICENSE: WTFPL
 use num_bigint::BigUint;
+use num_integer::{Integer, Roots};
+use std::cmp::min;
 use std::ffi::OsString;
 use std::process::ExitCode;
-use std::cmp::min;
 
 // bnum seems to be slightly faster than ruint,
 // and 3x faster than uint.
 type UInt = bnum::types::U256;
 
+fn is_square(n: UInt) -> bool {
+	let sq = n.sqrt();
+	sq * sq == n
+}
+
+fn is_choose2(mut n: UInt) -> bool {
+	n <<= 1;
+	n.inc();
+	is_square(n)
+}
+
 fn find_choose_r(mut k: UInt, r: u32) -> Option<UInt> {
 	// multiply k by r! to avoid future divisions
 	for i in 1..=r {
@@ -18,11 +30,11 @@ fn find_choose_r(mut k: UInt, r: u32) -> Option<UInt> {
 	let mut hi = UInt::from(1u8) << (log / r + 2);
 	let mut lo = UInt::from(r + 1);
 	'outer: while lo < hi {
-		let mid: UInt = (lo + hi) / UInt::from(2u8);
+		let mid: UInt = (lo + hi) >> 1;
 		let mut i = mid;
 		let mut mid_falling_r = mid;
 		for _ in 1..r {
-			i -= UInt::from(1u8);
+			i.dec();
 			mid_falling_r *= i;
 			if mid_falling_r > k {
 				hi = mid;
@@ -30,7 +42,8 @@ fn find_choose_r(mut k: UInt, r: u32) -> Option<UInt> {
 			}
 		}
 		if mid_falling_r < k {
-			lo = mid + UInt::from(1u8);
+			lo = mid;
+			lo.inc();
 		} else {
 			return Some(mid);
 		}
@@ -174,7 +187,11 @@ fn search_row_limit(row_limit: u32) {
 	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);
-			entries.push(PascalEntry::new(pascal_row[row as usize / 2], row, (row / 2) as u16));
+			entries.push(PascalEntry::new(
+				pascal_row[row as usize / 2],
+				row,
+				(row / 2) as u16,
+			));
 		}
 		for col in (2..=(std::cmp::max(3, row) - 1) / 2).rev() {
 			pascal_row[col as usize] =
@@ -221,7 +238,10 @@ fn search_col_limit(col_limit: u16) {
 				// we already know the solutions with both columns ≤ 4
 				continue;
 			}
-			for col2 in 2..min(col, col_limit as usize + 1) {
+			if is_choose2(pascal_row[col]) {
+				println!("({row} choose {col}) = (something choose 2)");
+			}
+			for col2 in 3..min(col, col_limit as usize + 1) {
 				if let Some(x) = find_choose_r(pascal_row[col], col2 as u32) {
 					println!("({row} choose {col}) = ({x} choose {col2})");
 				}
-- 
cgit v1.2.3