diff options
| -rw-r--r-- | Cargo.lock | 5 | ||||
| -rw-r--r-- | Cargo.toml | 3 | ||||
| -rw-r--r-- | README.md | 5 | ||||
| -rw-r--r-- | src/main.rs | 32 |
4 files changed, 36 insertions, 9 deletions
@@ -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", ] @@ -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" @@ -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})"); } |