84 lines
2.4 KiB
Text
84 lines
2.4 KiB
Text
use std::convert::TryInto;
|
|
|
|
/// Gets all divisors of a number, including itself
|
|
fn get_divisors(n: u32) -> Vec<u32> {
|
|
let mut results = Vec::new();
|
|
|
|
for i in 1..(n / 2 + 1) {
|
|
if n % i == 0 {
|
|
results.push(i);
|
|
}
|
|
}
|
|
results.push(n);
|
|
results
|
|
}
|
|
|
|
/// Calculates whether the divisors can be partitioned into two disjoint
|
|
/// sets that sum to the same value
|
|
fn is_summable(x: i32, divisors: &[u32]) -> bool {
|
|
if !divisors.is_empty() {
|
|
if divisors.contains(&(x as u32)) {
|
|
return true;
|
|
} else if let Some((first, t)) = divisors.split_first() {
|
|
return is_summable(x - *first as i32, &t) || is_summable(x, &t);
|
|
}
|
|
}
|
|
false
|
|
}
|
|
|
|
/// Calculates whether the number is a Zumkeller number
|
|
/// Zumkeller numbers are the set of numbers whose divisors can be partitioned
|
|
/// into two disjoint sets that sum to the same value. Each sum must contain
|
|
/// divisor values that are not in the other sum, and all of the divisors must
|
|
/// be in one or the other.
|
|
fn is_zumkeller_number(number: u32) -> bool {
|
|
if number % 18 == 6 || number % 18 == 12 {
|
|
return true;
|
|
}
|
|
|
|
let div = get_divisors(number);
|
|
let divisor_sum: u32 = div.iter().sum();
|
|
if divisor_sum == 0 {
|
|
return false;
|
|
}
|
|
if divisor_sum % 2 == 1 {
|
|
return false;
|
|
}
|
|
|
|
// numbers where n is odd and the abundance is even are Zumkeller numbers
|
|
let abundance = divisor_sum as i32 - 2 * number as i32;
|
|
if number % 2 == 1 && abundance > 0 && abundance % 2 == 0 {
|
|
return true;
|
|
}
|
|
|
|
let half = divisor_sum / 2;
|
|
return div.contains(&half)
|
|
|| (div.iter().filter(|&&d| d < half).count() > 0
|
|
&& is_summable(half.try_into().unwrap(), &div));
|
|
}
|
|
|
|
fn main() {
|
|
println!("\nFirst 220 Zumkeller numbers:");
|
|
let mut counter: u32 = 0;
|
|
let mut i: u32 = 0;
|
|
while counter < 220 {
|
|
if is_zumkeller_number(i) {
|
|
print!("{:>3}", i);
|
|
counter += 1;
|
|
print!("{}", if counter % 20 == 0 { "\n" } else { "," });
|
|
}
|
|
i += 1;
|
|
}
|
|
|
|
println!("\nFirst 40 odd Zumkeller numbers:");
|
|
let mut counter: u32 = 0;
|
|
let mut i: u32 = 3;
|
|
while counter < 40 {
|
|
if is_zumkeller_number(i) {
|
|
print!("{:>5}", i);
|
|
counter += 1;
|
|
print!("{}", if counter % 20 == 0 { "\n" } else { "," });
|
|
}
|
|
i += 2;
|
|
}
|
|
}
|