nice interface, etc.

4 files changed, 106 insertions, 63 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 89a6f00..a5a6de5 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -3,43 +3,14 @@
 version = 3
 
 [[package]]
-name = "autocfg"
-version = "1.3.0"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "0c4b4d0bd25bd0b74681c0ad21497610ce1b7c91b1022cd21c80c6fbdd9476b0"
-
-[[package]]
 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-integer"
-version = "0.1.46"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "7969661fd2958a5cb096e56c8e1ad0444ac2bbcd0061bd28660485a44879858f"
-dependencies = [
- "num-traits",
-]
-
-[[package]]
-name = "num-traits"
-version = "0.2.19"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "071dfc062690e90b734c0b2273ce72ad0ffa95f0c74596bc250dcfd960262841"
-dependencies = [
- "autocfg",
-]
 
 [[package]]
 name = "pascal"
 version = "0.1.0"
 dependencies = [
  "bnum",
- "num-integer",
 ]
diff --git a/Cargo.toml b/Cargo.toml
index fe1bd10..492faf6 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -4,5 +4,4 @@ version = "0.1.0"
 edition = "2021"
 
 [dependencies]
-bnum = { version = "0.11.0", features = ["num-integer", "numtraits"] }
-num-integer = "0.1.46"
+bnum = "0.11.0"
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..6d504d4
--- /dev/null
+++ b/README.md
@@ -0,0 +1,47 @@
+# Repeated numbers in Pascal's Triangle
+
+Every number ${n \choose k}, 1<k<n-1$ appears at least four times in Pascal's triangle:
+$${n\choose k} = {n\choose n-k} = {{n\choose k}\choose 1}={{n\choose k}\choose {n\choose k}}$$
+This gives rise to the natural question of which numbers appear more than four times. Or, taking
+out the symmetry and trivial case of ${n\choose 1}$, what are the solutions to
+$${n\choose k}={m\choose l},$$
+for $1<k\leq \frac n2$, $k<l\leq \frac m2$.
+
+According to ["A Note on the Diophantine equation (x 4)=(y 2)"](https://www.researchgate.net/publication/235418296_A_Note_on_the_Diophantine_equation_x_4y_2)
+(Ákos Pintér, 1995),
+the cases of $(k,l)=(2,3)$ and $(k,l)=(2,4)$ have been solved completely,
+and from ["Equal binomial coefficients: some elementary considerations"](https://repub.eur.nl/pub/1356/1356_ps.pdf)
+(Benjamin M.M. de Weger, 1995), we also know that there are no solutions with $(k,l)=(3,4)$; so here is the full list of
+solutions with $l \leq 4$.
+
+<table>
+<tr><th>k</th><th>l</th><th>n</th><th>m</th><th>n choose k = m choose l</th></tr>
+<tr><td>2</td><td>3</td><td>16</td><td>10</td><td>120</td></tr>
+<tr><td>2</td><td>3</td><td>56</td><td>22</td><td>1540</td></tr>
+<tr><td>2</td><td>3</td><td>120</td><td>36</td><td>7140</td></tr>
+<tr><td>2</td><td>4</td><td>21</td><td>10</td><td>210</td></tr>
+</table>
+
+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}
+$$
+
+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^{41}$ are the ones found by de Weger: namely, the ones in the infinite
+family above,
+$$ {15 \choose 5} = {14 \choose 6} = 3003 = {78 \choose 2}$$
+$$ {104 \choose 39} = {103 \choose 40} = 61218182743304701891431482520$$
+And the “sporadic” solutions:
+$$ {153 \choose 2} ={19\choose 5} = 11628$$
+$$ {221\choose 2}={17 \choose 8}=24310$$
+
+This program searches up to $10^X$, when given the argument $X$.
+The search works by putting all ${n\choose k}<10^X$ with $5\leq k\leq \frac n 2$ into
+an array and sorting it. Then we check for adjacent elements which are equal,
+and use a binary search to check whether elements in the array are ${n\choose 2},{n\choose 3},{n\choose 4}$.
+This finds all solutions with $l>4$ (since the solutions with $l\leq 4$ are known).
+
+Unfortunately searching to $10^{41}$ with this method already requires 13 GB of memory.
diff --git a/src/main.rs b/src/main.rs
index 5f3a3b5..8be934d 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -1,3 +1,8 @@
+use std::ffi::OsString;
+use std::process::ExitCode;
+
+// bnum seems to be slightly faster than ruint,
+// and 3x faster than uint.
 type UInt = bnum::types::U256;
 
 fn is_choose_r(mut k: UInt, r: u32) -> bool {
@@ -30,16 +35,64 @@ fn is_choose_r(mut k: UInt, r: u32) -> bool {
 	false
 }
 
-fn main() {
+fn superscript(number: &str) -> String {
+	number
+		.chars()
+		.map(|c| match c {
+			'0' => '⁰',
+			'1' => '¹',
+			'2' => '²',
+			'3' => '³',
+			'4' => '⁴',
+			'5' => '⁵',
+			'6' => '⁶',
+			'7' => '⁷',
+			'8' => '⁸',
+			'9' => '⁹',
+			_ => c,
+		})
+		.collect()
+}
+
+fn main() -> ExitCode {
+	let args: Vec<OsString> = 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;
+	}
+	let power_of_10: Option<usize> = 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::<UInt>() * 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;
+	}
+
 	let mut pascal_row = [UInt::from(0u8); 500];
 	let mut range = pascal_row.len();
-	let limit = UInt::from(10u8).pow(40);
+	println!(
+		"searching up to 10{}",
+		superscript(&format!("{power_of_10}"))
+	);
+	let limit = UInt::from(10u8).pow(power_of_10 as u32);
 	let mut numbers: Vec<UInt> = Vec::new();
 	pascal_row[0] = UInt::from(1u8);
-	for row in 1.. {
+	for row in 1u128.. {
 		for i in (1..range).rev() {
 			pascal_row[i] += pascal_row[i - 1];
-			if i > 4 && i <= row / 2 {
+			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]);
+				}
 				numbers.push(pascal_row[i]);
 			}
 			if pascal_row[i] > limit {
@@ -61,15 +114,6 @@ fn main() {
 		if n == prev {
 			occurrences += 1;
 		} else if occurrences > 0 {
-			if is_choose_r(prev, 2) {
-				occurrences += 1;
-			}
-			if is_choose_r(prev, 3) {
-				occurrences += 1;
-			}
-			if is_choose_r(prev, 4) {
-				occurrences += 1;
-			}
 			if occurrences > 1 {
 				println!("{prev}: {occurrences}");
 			}
@@ -77,23 +121,5 @@ fn main() {
 		}
 		prev = n;
 	}
-	//sufficiently_small();
-}
-
-#[allow(unused)]
-fn sufficiently_small() {
-	for r in 2u128..100 {
-		let fact: f64 = (1..=r).map(|x| x as f64).product();
-		println!(
-			"r = {r}, largest counterexample = {:?}",
-			(r..10000)
-				.filter(|&x| {
-					2 * x - r + 1
-						!= (((x - r + 1..=x).map(|x| x as f64).product::<f64>())
-							.powf(1.0 / r as f64) * 2.0)
-							.ceil() as u128
-				})
-				.max()
-		);
-	}
+	ExitCode::SUCCESS
 }