Rare numbers: Difference between revisions
Content added Content deleted
(Add Rust implementation) |
|||
Line 4,479: | Line 4,479: | ||
4: 2,022,652,202 |
4: 2,022,652,202 |
||
5: 2,042,832,002</pre> |
5: 2,042,832,002</pre> |
||
=={{header|Rust}}== |
|||
A naive and an advanced version based on Nigel Galloway |
|||
<lang rust> |
|||
use itertools::Itertools; |
|||
use std::collections::HashMap; |
|||
use std::convert::TryInto; |
|||
use std::fmt; |
|||
use std::time::Instant; |
|||
#[derive(Debug)] |
|||
struct RareResults { |
|||
digits: u8, |
|||
time_to_find: u128, |
|||
counter: u32, |
|||
number: u64, |
|||
} |
|||
impl fmt::Display for RareResults { |
|||
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { |
|||
write!( |
|||
f, |
|||
"{:>6} {:>6} ms {:>2}. {}", |
|||
self.digits, self.time_to_find, self.counter, self.number |
|||
) |
|||
} |
|||
} |
|||
fn print_results(results: Vec<RareResults>) { |
|||
if results.len() != 0 { |
|||
// println!("Results:"); |
|||
println!("digits time #. Rare number"); |
|||
for r in results { |
|||
println!("{}", r); |
|||
} |
|||
} |
|||
} |
|||
fn isqrt(n: u64) -> u64 { |
|||
let mut s = (n as f64).sqrt() as u64; |
|||
s = (s + n / s) >> 1; |
|||
if s * s > n { |
|||
s - 1 |
|||
} else { |
|||
s |
|||
} |
|||
} |
|||
fn is_square(n: u64) -> bool { |
|||
match n & 0xf { |
|||
0 | 1 | 4 | 9 => { |
|||
let t = isqrt(n); |
|||
t * t == n |
|||
} |
|||
_ => false, |
|||
} |
|||
} |
|||
fn get_reverse(number: &u64) -> u64 { |
|||
number |
|||
.to_string() |
|||
.chars() |
|||
.map(|c| c.to_digit(10).unwrap()) |
|||
.enumerate() |
|||
.fold(0_u64, |a, (i, d)| a + 10_u64.pow(i as u32) * d as u64) |
|||
} |
|||
fn is_rare(number: u64) -> bool { |
|||
let reverse = get_reverse(&number); |
|||
reverse != number |
|||
&& number > reverse |
|||
&& is_square(number + reverse) |
|||
&& is_square(number - reverse) |
|||
} |
|||
/// This method is a very simple naive search, using brute-force to check a high amount of numbers |
|||
/// for satisfying the rare number criterias. As such it is rather slow, and above 10 digits it's |
|||
/// not really performant, release version takes ~30 secs to find the first 5 (max 10 digits) |
|||
fn naive(digit: u8) -> Vec<RareResults> { |
|||
let bp_equal = (0_u8..=9).zip(0_u8..=9).collect::<Vec<(u8, u8)>>(); |
|||
let bp_zero_or_even = (0_u8..=9) |
|||
.cartesian_product(0_u8..=9) |
|||
.filter(|pair| (pair.0 == pair.1) || (pair.0 as i32 - pair.1 as i32).abs() % 2 == 0) |
|||
.collect::<Vec<(u8, u8)>>(); |
|||
let bp_odd = (0_u8..=9) |
|||
.cartesian_product(0_u8..=9) |
|||
.filter(|pair| (pair.0 as i32 - pair.1 as i32).abs() % 2 == 1) |
|||
.collect::<Vec<(u8, u8)>>(); |
|||
let bp_9 = (0_u8..=9) |
|||
.cartesian_product(0_u8..=9) |
|||
.filter(|pair| pair.0 + pair.1 == 9) |
|||
.collect::<Vec<(u8, u8)>>(); |
|||
let bp_73 = (0_u8..=9) |
|||
.cartesian_product(0_u8..=9) |
|||
.filter(|pair| [7, 3].contains(&(pair.0 as i8 - pair.1 as i8))) |
|||
.collect::<Vec<(u8, u8)>>(); |
|||
let bp_11 = (0_u8..=9) |
|||
.cartesian_product(0_u8..=9) |
|||
.filter(|pair| pair.0 + pair.1 == 11 || pair.1 + pair.0 == 1) |
|||
.collect::<Vec<(u8, u8)>>(); |
|||
let aq_bp_setup: Vec<((u8, u8), &Vec<(u8, u8)>)> = vec![ |
|||
((2, 2), &bp_equal), |
|||
((4, 0), &bp_zero_or_even), |
|||
((6, 0), &bp_odd), |
|||
((6, 5), &bp_odd), |
|||
((8, 2), &bp_9), |
|||
((8, 3), &bp_73), |
|||
((8, 7), &bp_11), |
|||
((8, 8), &bp_equal), |
|||
]; |
|||
//generate AB-PQ combinations |
|||
let aq_bp = aq_bp_setup |
|||
.iter() |
|||
.map(|e| { |
|||
e.1.iter().fold(vec![], |mut out, b| { |
|||
out.push(vec![e.0 .0, b.0, b.1, e.0 .1]); |
|||
out |
|||
}) |
|||
}) |
|||
.flatten() |
|||
.collect::<Vec<_>>(); |
|||
let mut results: Vec<RareResults> = Vec::new(); |
|||
let mut counter = 0_u32; |
|||
let start_time = Instant::now(); |
|||
let d = digit; |
|||
print!("Digits: {} ", d); |
|||
if d < 4 { |
|||
for n in 10_u64.pow((d - 1).into())..10_u64.pow(d.into()) { |
|||
if is_rare(n) { |
|||
counter += 1; |
|||
results.push(RareResults { |
|||
digits: d, |
|||
time_to_find: start_time.elapsed().as_millis(), |
|||
counter, |
|||
number: n, |
|||
}); |
|||
} |
|||
} |
|||
} else { |
|||
aq_bp.iter().for_each(|abqp| { |
|||
let start = abqp[0] as u64 * 10_u64.pow((d - 1).into()) |
|||
+ abqp[1] as u64 * 10_u64.pow((d - 2).into()) |
|||
+ 10_u64 * abqp[2] as u64 |
|||
+ abqp[3] as u64; |
|||
// brute-force checking all numbers which matches the pattern AB...PQ |
|||
// very slow |
|||
for n in (start..start + 10_u64.pow((d - 2).into())).step_by(100) { |
|||
if is_rare(n) { |
|||
counter += 1; |
|||
results.push(RareResults { |
|||
digits: d, |
|||
time_to_find: start_time.elapsed().as_millis(), |
|||
counter, |
|||
number: n, |
|||
}); |
|||
} |
|||
} |
|||
}); |
|||
} |
|||
println!( |
|||
"Digits: {} done - Elapsed time(ms): {}", |
|||
d, |
|||
start_time.elapsed().as_millis() |
|||
); |
|||
results |
|||
} |
|||
/// This algorithm uses an advanced search strategy based on Nigel Galloway's approach, |
|||
/// and can find the first 40 rare numers (16 digits) within reasonable |
|||
/// time in release version |
|||
fn advanced(digit: u8) -> Vec<RareResults> { |
|||
// setup |
|||
let mut results: Vec<RareResults> = Vec::new(); |
|||
let mut counter = 0_u32; |
|||
let start_time = Instant::now(); |
|||
let numeric_digits = (0..=9).map(|x| [x, 0]).collect::<Vec<_>>(); |
|||
let diffs1: Vec<i8> = vec![0, 1, 4, 5, 6]; |
|||
// all possible digits pairs to calaculate potential diffs |
|||
let pairs = (0_i8..=9) |
|||
.cartesian_product(0_i8..=9) |
|||
.map(|x| [x.0, x.1]) |
|||
.collect::<Vec<_>>(); |
|||
let all_diffs = (-9i8..=9).collect::<Vec<_>>(); |
|||
// lookup table for the first diff |
|||
let lookup_1 = vec![ |
|||
vec![[2, 2], [8, 8]], //Diff = 0 |
|||
vec![[8, 7], [6, 5]], //Diff = 1 |
|||
vec![], |
|||
vec![], |
|||
vec![[4, 0]], // Diff = 4 |
|||
vec![[8, 3]], // Diff = 5 |
|||
vec![[6, 0], [8, 2]], // Diff = 6 |
|||
]; |
|||
// lookup table for all the remaining diffs |
|||
let lookup_n: HashMap<i8, Vec<_>> = pairs.into_iter().into_group_map_by(|elt| elt[0] - elt[1]); |
|||
let d = digit; |
|||
// powers like 1, 10, 100, 1000.... |
|||
let powers = (0..d).map(|x| 10_u64.pow(x.into())).collect::<Vec<u64>>(); |
|||
// for n-r (aka L) the required terms, like 9/ 99 / 999 & 90 / 99999 & 9999 & 900 etc |
|||
let terms = powers |
|||
.iter() |
|||
.zip(powers.iter().rev()) |
|||
.map(|(a, b)| b.checked_sub(*a).unwrap_or(0)) |
|||
.filter(|x| *x != 0) |
|||
.collect::<Vec<u64>>(); |
|||
// create a cartesian product for all potetential diff numbers |
|||
// for the first use the very short one, for all other the complete 19 element |
|||
let diff_list_iter = (0_u8..(d / 2)) |
|||
.map(|i| match i { |
|||
0 => diffs1.iter(), |
|||
_ => all_diffs.iter(), |
|||
}) |
|||
.multi_cartesian_product() |
|||
// remove invalid first diff/second diff combinations - custom iterator would be probably better |
|||
.filter(|x| { |
|||
if x.len() == 1 { |
|||
return true; |
|||
} |
|||
match (*x[0], *x[1]) { |
|||
(a, b) if (a == 0 && b != 0) => false, |
|||
(a, b) if (a == 1 && ![-7, -5, -3, -1, 1, 3, 5, 7].contains(&b)) => false, |
|||
(a, b) if (a == 4 && ![-8, -6, -4, -2, 0, 2, 4, 6, 8].contains(&b)) => false, |
|||
(a, b) if (a == 5 && ![7, -3].contains(&b)) => false, |
|||
(a, b) if (a == 6 && ![-9 - 7, -5, -3, -1, 1, 3, 5, 7, 9].contains(&b)) => { |
|||
false |
|||
} |
|||
_ => true, |
|||
} |
|||
}); |
|||
#[cfg(debug_assertions)] |
|||
{ |
|||
println!(" powers: {:?}", powers); |
|||
println!(" terms: {:?}", terms); |
|||
} |
|||
diff_list_iter.for_each(|diffs| { |
|||
// calculate difference of original n and its reverse (aka L = n-r) |
|||
// which must be a perfect square |
|||
let l: i64 = diffs |
|||
.iter() |
|||
.zip(terms.iter()) |
|||
.map(|(diff, term)| **diff as i64 * *term as i64) |
|||
.sum(); |
|||
if l > 0 && is_square(l.try_into().unwrap()) { |
|||
// potential candiate, at least L is a perfect square |
|||
#[cfg(debug_assertions)] |
|||
println!(" square L: {}, diffs: {:?}", l, diffs); |
|||
// placeholder for the digits |
|||
let mut dig: Vec<i8> = vec![0_i8; d.into()]; |
|||
// generate a cartesian product for each identified diff using the lookup tables |
|||
let c_iter = (0..(diffs.len() + d as usize % 2)) |
|||
.map(|i| match i { |
|||
0 => lookup_1[*diffs[0] as usize].iter(), |
|||
_ if i != diffs.len() => lookup_n.get(diffs[i]).unwrap().iter(), |
|||
_ => numeric_digits.iter(), // for the middle digits |
|||
}) |
|||
.multi_cartesian_product(); |
|||
// check each H (n+r) by using digit combination |
|||
c_iter.for_each(|elt| { |
|||
// print!(" digits combinations: {:?}", elt); |
|||
for (i, digit_pair) in elt.iter().enumerate() { |
|||
// print!(" digit pairs: {:?}, len: {}", digit_pair, l.len()); |
|||
dig[i] = digit_pair[0]; |
|||
dig[d as usize - 1 - i] = digit_pair[1] |
|||
} |
|||
// for numbers with odd # digits restore the middle digit |
|||
// which has been overwritten at the end of the previous cycle |
|||
if d % 2 == 1 { |
|||
dig[(d as usize - 1) / 2] = elt[elt.len() - 1][0]; |
|||
} |
|||
let num = dig |
|||
.iter() |
|||
.rev() |
|||
.enumerate() |
|||
.fold(0_u64, |acc, (i, d)| acc + 10_u64.pow(i as u32) * *d as u64); |
|||
let reverse = dig |
|||
.iter() |
|||
.enumerate() |
|||
.fold(0_u64, |acc, (i, d)| acc + 10_u64.pow(i as u32) * *d as u64); |
|||
if num > reverse && is_square(num + reverse) { |
|||
println!(" FOUND: {}, reverse: {}", num, reverse); |
|||
counter += 1; |
|||
results.push(RareResults { |
|||
digits: d, |
|||
time_to_find: start_time.elapsed().as_millis(), |
|||
counter, |
|||
number: num, |
|||
}); |
|||
} |
|||
}); |
|||
} |
|||
}); |
|||
println!( |
|||
"Digits: {} done - Elapsed time(ms): {}", |
|||
d, |
|||
start_time.elapsed().as_millis() |
|||
); |
|||
results |
|||
} |
|||
fn main() { |
|||
println!("Run this program in release mode for measuring performance"); |
|||
println!("Naive version:"); |
|||
(1..=10).for_each(|x| print_results(naive(x))); |
|||
println!("Advanced version:"); |
|||
(1..=15).for_each(|x| print_results(advanced(x))); |
|||
} |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
Run this program in release mode for measuring performance |
|||
Naive version: |
|||
Digits: 1 Digits: 1 done - Elapsed time(ms): 0 |
|||
Digits: 2 Digits: 2 done - Elapsed time(ms): 0 |
|||
digits time #. Rare number |
|||
2 0 ms 1. 65 |
|||
Digits: 3 Digits: 3 done - Elapsed time(ms): 0 |
|||
Digits: 4 Digits: 4 done - Elapsed time(ms): 0 |
|||
Digits: 5 Digits: 5 done - Elapsed time(ms): 0 |
|||
Digits: 6 Digits: 6 done - Elapsed time(ms): 11 |
|||
digits time #. Rare number |
|||
6 3 ms 1. 621770 |
|||
Digits: 7 Digits: 7 done - Elapsed time(ms): 76 |
|||
Digits: 8 Digits: 8 done - Elapsed time(ms): 641 |
|||
Digits: 9 Digits: 9 done - Elapsed time(ms): 6375 |
|||
digits time #. Rare number |
|||
9 232 ms 1. 281089082 |
|||
Digits: 10 Digits: 10 done - Elapsed time(ms): 37598 |
|||
digits time #. Rare number |
|||
10 44 ms 1. 2022652202 |
|||
10 82 ms 2. 2042832002 |
|||
Advanced version: |
|||
Digits: 1 done - Elapsed time(ms): 6 |
|||
FOUND: 65, reverse: 56 |
|||
Digits: 2 done - Elapsed time(ms): 0 |
|||
digits time #. Rare number |
|||
2 0 ms 1. 65 |
|||
Digits: 3 done - Elapsed time(ms): 0 |
|||
Digits: 4 done - Elapsed time(ms): 0 |
|||
Digits: 5 done - Elapsed time(ms): 0 |
|||
FOUND: 621770, reverse: 77126 |
|||
Digits: 6 done - Elapsed time(ms): 0 |
|||
digits time #. Rare number |
|||
6 0 ms 1. 621770 |
|||
Digits: 7 done - Elapsed time(ms): 0 |
|||
Digits: 8 done - Elapsed time(ms): 5 |
|||
FOUND: 281089082, reverse: 280980182 |
|||
Digits: 9 done - Elapsed time(ms): 5 |
|||
digits time #. Rare number |
|||
9 0 ms 1. 281089082 |
|||
FOUND: 2022652202, reverse: 2022562202 |
|||
FOUND: 2042832002, reverse: 2002382402 |
|||
Digits: 10 done - Elapsed time(ms): 107 |
|||
digits time #. Rare number |
|||
10 6 ms 1. 2022652202 |
|||
10 22 ms 2. 2042832002 |
|||
Digits: 11 done - Elapsed time(ms): 161 |
|||
FOUND: 872546974178, reverse: 871479645278 |
|||
FOUND: 872568754178, reverse: 871457865278 |
|||
FOUND: 868591084757, reverse: 757480195868 |
|||
Digits: 12 done - Elapsed time(ms): 1707 |
|||
digits time #. Rare number |
|||
12 319 ms 1. 872546974178 |
|||
12 342 ms 2. 872568754178 |
|||
12 846 ms 3. 868591084757 |
|||
FOUND: 6979302951885, reverse: 5881592039796 |
|||
Digits: 13 done - Elapsed time(ms): 2409 |
|||
digits time #. Rare number |
|||
13 540 ms 1. 6979302951885 |
|||
FOUND: 20313693904202, reverse: 20240939631302 |
|||
FOUND: 20313839704202, reverse: 20240793831302 |
|||
FOUND: 20331657922202, reverse: 20222975613302 |
|||
FOUND: 20331875722202, reverse: 20222757813302 |
|||
FOUND: 20333875702202, reverse: 20220757833302 |
|||
FOUND: 40313893704200, reverse: 240739831304 |
|||
FOUND: 40351893720200, reverse: 202739815304 |
|||
Digits: 14 done - Elapsed time(ms): 41440 |
|||
digits time #. Rare number |
|||
14 6568 ms 1. 20313693904202 |
|||
14 6642 ms 2. 20313839704202 |
|||
14 7727 ms 3. 20331657922202 |
|||
14 7881 ms 4. 20331875722202 |
|||
14 8287 ms 5. 20333875702202 |
|||
14 25737 ms 6. 40313893704200 |
|||
14 25845 ms 7. 40351893720200 |
|||
FOUND: 200142385731002, reverse: 200137583241002 |
|||
FOUND: 221462345754122, reverse: 221457543264122 |
|||
FOUND: 816984566129618, reverse: 816921665489618 |
|||
FOUND: 245518996076442, reverse: 244670699815542 |
|||
FOUND: 204238494066002, reverse: 200660494832402 |
|||
FOUND: 248359494187442, reverse: 244781494953842 |
|||
FOUND: 244062891224042, reverse: 240422198260442 |
|||
FOUND: 403058392434500, reverse: 5434293850304 |
|||
FOUND: 441054594034340, reverse: 43430495450144 |
|||
Digits: 15 done - Elapsed time(ms): 42591 |
|||
digits time #. Rare number |
|||
15 2788 ms 1. 200142385731002 |
|||
15 2970 ms 2. 221462345754122 |
|||
15 5616 ms 3. 816984566129618 |
|||
15 6999 ms 4. 245518996076442 |
|||
15 7229 ms 5. 204238494066002 |
|||
15 7291 ms 6. 248359494187442 |
|||
15 7547 ms 7. 244062891224042 |
|||
15 23704 ms 8. 403058392434500 |
|||
15 23883 ms 9. 441054594034340 |
|||
</pre> |
|||
=={{header|Visual Basic .NET}}== |
=={{header|Visual Basic .NET}}== |