97 lines
3.3 KiB
Text
97 lines
3.3 KiB
Text
const ARRAY_MAX: usize = 25_000;
|
|
const LUDIC_MAX: usize = 2100;
|
|
|
|
/// Calculates and returns the first `LUDIC_MAX` Ludic numbers.
|
|
///
|
|
/// Needs a sufficiently large `ARRAY_MAX`.
|
|
fn ludic_numbers() -> Vec<usize> {
|
|
// The first two Ludic numbers
|
|
let mut numbers = vec![1, 2];
|
|
// We start the array with an immediate first removal to reduce memory usage by
|
|
// collecting only odd numbers.
|
|
numbers.extend((3..ARRAY_MAX).step_by(2));
|
|
|
|
// We keep the correct Ludic numbers in place, removing the incorrect ones.
|
|
for ludic_idx in 2..LUDIC_MAX {
|
|
let next_ludic = numbers[ludic_idx];
|
|
|
|
// We remove incorrect numbers by counting the indices after the correct numbers.
|
|
// We start from zero and keep until we reach the potentially incorrect numbers.
|
|
// Then we keep only those not divisible by the `next_ludic`.
|
|
let mut idx = 0;
|
|
numbers.retain(|_| {
|
|
let keep = idx <= ludic_idx || (idx - ludic_idx) % next_ludic != 0;
|
|
idx += 1;
|
|
keep
|
|
});
|
|
}
|
|
|
|
numbers
|
|
}
|
|
|
|
fn main() {
|
|
let ludic_numbers = ludic_numbers();
|
|
|
|
print!("First 25: ");
|
|
print_n_ludics(&ludic_numbers, 25);
|
|
println!();
|
|
print!("Number of Ludics below 1000: ");
|
|
print_num_ludics_upto(&ludic_numbers, 1000);
|
|
println!();
|
|
print!("Ludics from 2000 to 2005: ");
|
|
print_ludics_from_to(&ludic_numbers, 2000, 2005);
|
|
println!();
|
|
println!("Triplets below 250: ");
|
|
print_triplets_until(&ludic_numbers, 250);
|
|
}
|
|
|
|
/// Prints the first `n` Ludic numbers.
|
|
fn print_n_ludics(x: &[usize], n: usize) {
|
|
println!("{:?}", &x[..n]);
|
|
}
|
|
|
|
/// Calculates how many Ludic numbers are below `max_num`.
|
|
fn print_num_ludics_upto(x: &[usize], max_num: usize) {
|
|
let num = x.iter().take_while(|&&i| i < max_num).count();
|
|
println!("{}", num);
|
|
}
|
|
|
|
/// Prints Ludic numbers between two numbers.
|
|
fn print_ludics_from_to(x: &[usize], from: usize, to: usize) {
|
|
println!("{:?}", &x[from - 1..to - 1]);
|
|
}
|
|
|
|
/// Calculates triplets until a certain Ludic number.
|
|
fn triplets_below(ludics: &[usize], limit: usize) -> Vec<(usize, usize, usize)> {
|
|
ludics
|
|
.iter()
|
|
.enumerate()
|
|
.take_while(|&(_, &num)| num < limit)
|
|
.filter_map(|(idx, &number)| {
|
|
let triplet_2 = number + 2;
|
|
let triplet_3 = number + 6;
|
|
|
|
// Search for the other two triplet numbers. We know they are larger than
|
|
// `number` so we can give the searches lower bounds of `idx + 1` and
|
|
// `idx + 2`. We also know that the `n + 2` number can only ever be two
|
|
// numbers away from the previous and the `n + 6` number can only be four
|
|
// away (because we removed some in between). Short circuiting and doing
|
|
// the check more likely to fail first are also useful.
|
|
let is_triplet = ludics[idx + 1..idx + 3].binary_search(&triplet_2).is_ok()
|
|
&& ludics[idx + 2..idx + 5].binary_search(&triplet_3).is_ok();
|
|
|
|
if is_triplet {
|
|
Some((number, triplet_2, triplet_3))
|
|
} else {
|
|
None
|
|
}
|
|
})
|
|
.collect()
|
|
}
|
|
|
|
/// Prints triplets until a certain Ludic number.
|
|
fn print_triplets_until(ludics: &[usize], limit: usize) {
|
|
for (number, triplet_2, triplet_3) in triplets_below(ludics, limit) {
|
|
println!("{} {} {}", number, triplet_2, triplet_3);
|
|
}
|
|
}
|