checking up to 10⁴⁰

5 files changed, 142 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..ea8c4bf
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1 @@
+/target
diff --git a/Cargo.lock b/Cargo.lock
new file mode 100644
index 0000000..89a6f00
--- /dev/null
+++ b/Cargo.lock
@@ -0,0 +1,45 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+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
new file mode 100644
index 0000000..fe1bd10
--- /dev/null
+++ b/Cargo.toml
@@ -0,0 +1,8 @@
+[package]
+name = "pascal"
+version = "0.1.0"
+edition = "2021"
+
+[dependencies]
+bnum = { version = "0.11.0", features = ["num-integer", "numtraits"] }
+num-integer = "0.1.46"
diff --git a/rustfmt.toml b/rustfmt.toml
new file mode 100644
index 0000000..218e203
--- /dev/null
+++ b/rustfmt.toml
@@ -0,0 +1 @@
+hard_tabs = true
diff --git a/src/main.rs b/src/main.rs
new file mode 100644
index 0000000..c14ee2a
--- /dev/null
+++ b/src/main.rs
@@ -0,0 +1,87 @@
+type UInt = bnum::types::U256;
+
+fn is_choose_r(mut k: UInt, r: u32) -> bool {
+	// multiply k by r! to avoid future divisions
+	for i in 1..=r {
+		k *= UInt::from(i);
+	}
+	let k = k; // no morge changing k
+	let log = k.ilog2();
+	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 mut i = mid;
+		let mut mid_falling_r = mid;
+		for _ in 1..r {
+			i -= UInt::from(1u8);
+			mid_falling_r *= i;
+			if mid_falling_r > k {
+				hi = mid;
+				continue 'outer;
+			}
+		}
+		if mid_falling_r < k {
+			lo = mid + UInt::from(1u8);
+		} else {
+			return true;
+		}
+	}
+	false
+}
+
+fn main() {
+	let mut pascal_row = [UInt::from(0u8); 500];
+	let mut range = pascal_row.len();
+	let limit = UInt::from(10u8).pow(40);
+	let mut numbers: Vec<UInt> = Vec::new();
+	pascal_row[0] = UInt::from(1u8);
+	for row in 1.. {
+		for i in (1..range).rev() {
+			pascal_row[i] += pascal_row[i - 1];
+			if i > 4 && i <= row / 2 {
+				numbers.push(pascal_row[i]);
+			}
+			if pascal_row[i] > limit {
+				range = i;
+			}
+		}
+		if range <= 4 { break; }
+	}
+	println!("memory needed = {}MiB", (numbers.len() * size_of::<UInt>()) >> 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 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}");
+			}
+			occurrences = 1;
+		}
+		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()
+		);
+	}
+}