98 lines
1.7 KiB
Rust
98 lines
1.7 KiB
Rust
fn gcd(mut a: i32, mut b: i32) -> i32 {
|
|
while b != 0 {
|
|
let temp = b;
|
|
b = a % b;
|
|
a = temp;
|
|
}
|
|
a
|
|
}
|
|
|
|
fn duffinian(n: i32) -> bool {
|
|
if n == 2 {
|
|
return false;
|
|
}
|
|
|
|
let mut total = 1;
|
|
let mut power = 2;
|
|
let m = n;
|
|
let mut n = n;
|
|
|
|
// Handle powers of 2
|
|
while (n & 1) == 0 {
|
|
total += power;
|
|
power <<= 1;
|
|
n >>= 1;
|
|
}
|
|
|
|
// Handle odd prime factors
|
|
let mut p = 3;
|
|
while p * p <= n {
|
|
let mut sum = 1;
|
|
power = p;
|
|
while n % p == 0 {
|
|
sum += power;
|
|
power *= p;
|
|
n /= p;
|
|
}
|
|
total *= sum;
|
|
p += 2;
|
|
}
|
|
|
|
// Check if n is composite
|
|
if m == n {
|
|
return false;
|
|
}
|
|
|
|
// Handle remaining prime factor
|
|
if n > 1 {
|
|
total *= n + 1;
|
|
}
|
|
|
|
gcd(total, m) == 1
|
|
}
|
|
|
|
fn main() {
|
|
println!("First 50 Duffinian numbers:");
|
|
let mut count = 0;
|
|
let mut n = 1;
|
|
|
|
while count < 50 {
|
|
if duffinian(n) {
|
|
print!("{:3}", n);
|
|
count += 1;
|
|
if count % 10 == 0 {
|
|
println!();
|
|
} else {
|
|
print!(" ");
|
|
}
|
|
}
|
|
n += 1;
|
|
}
|
|
|
|
println!("\nFirst 50 Duffinian triplets:");
|
|
let mut n = 1;
|
|
let mut m = 0;
|
|
let mut count = 0;
|
|
|
|
while count < 50 {
|
|
if duffinian(n) {
|
|
m += 1;
|
|
} else {
|
|
m = 0;
|
|
}
|
|
|
|
if m == 3 {
|
|
let triplet = format!("({}, {}, {})", n - 2, n - 1, n);
|
|
print!("{:<24}", triplet);
|
|
count += 1;
|
|
if count % 3 == 0 {
|
|
println!();
|
|
} else {
|
|
print!(" ");
|
|
}
|
|
}
|
|
n += 1;
|
|
}
|
|
println!();
|
|
}
|