125 lines
2.3 KiB
Plaintext
125 lines
2.3 KiB
Plaintext
use std::cmp::{max, min};
|
|
|
|
static TENS: [u64; 20] = [
|
|
1,
|
|
10,
|
|
100,
|
|
1000,
|
|
10000,
|
|
100000,
|
|
1000000,
|
|
10000000,
|
|
100000000,
|
|
1000000000,
|
|
10000000000,
|
|
100000000000,
|
|
1000000000000,
|
|
10000000000000,
|
|
100000000000000,
|
|
1000000000000000,
|
|
10000000000000000,
|
|
100000000000000000,
|
|
1000000000000000000,
|
|
10000000000000000000,
|
|
];
|
|
|
|
/// Get the number of digits present in x
|
|
fn ndigits(mut x: u64) -> u64 {
|
|
let mut n = 0;
|
|
|
|
while x != 0 {
|
|
n += 1;
|
|
x /= 10;
|
|
}
|
|
|
|
n
|
|
}
|
|
|
|
fn dtally(mut x: u64) -> u64 {
|
|
let mut t = 0;
|
|
|
|
while x != 0 {
|
|
t += 1 << ((x % 10) * 6);
|
|
x /= 10;
|
|
}
|
|
|
|
t
|
|
}
|
|
|
|
/// Get a list of all fangs of x. Get only the first divider of each fang. The second one can be found simply with x / fang.
|
|
fn fangs(x: u64) -> Vec<u64> {
|
|
let mut nd = ndigits(x) as usize;
|
|
|
|
let mut fangs = vec![];
|
|
|
|
if nd & 1 != 1 {
|
|
nd /= 2;
|
|
|
|
let lo = max(TENS[nd - 1], (x + TENS[nd] - 2) / (TENS[nd] - 1));
|
|
let hi = min(x / lo, (x as f64).sqrt() as u64);
|
|
|
|
let t = dtally(x);
|
|
|
|
for a in lo..(hi + 1) {
|
|
let b = x / a;
|
|
if a * b == x && ((a % 10) > 0 || b % 10 > 0) && t == dtally(a) + dtally(b) {
|
|
fangs.push(a);
|
|
}
|
|
}
|
|
}
|
|
|
|
fangs
|
|
}
|
|
|
|
/// Pretty print the fangs of x
|
|
fn print_fangs(x: u64, fangs: Vec<u64>) {
|
|
print!("{} = ", x);
|
|
|
|
if fangs.is_empty() {
|
|
print!("is not vampiric");
|
|
} else {
|
|
for fang in fangs {
|
|
print!("{} x {}, ", fang, x / fang);
|
|
}
|
|
}
|
|
print!("\n");
|
|
}
|
|
|
|
fn main() {
|
|
println!("The first 25 vampire numbers are :");
|
|
|
|
let mut nfangs = 0;
|
|
let mut x = 1;
|
|
|
|
while nfangs < 25 {
|
|
let fangs = fangs(x);
|
|
if !fangs.is_empty() {
|
|
nfangs += 1;
|
|
print_fangs(x, fangs);
|
|
}
|
|
|
|
x += 1;
|
|
}
|
|
|
|
println!("\nSpecial requests :");
|
|
|
|
print_fangs(16758243290880, fangs(16758243290880));
|
|
print_fangs(24959017348650, fangs(24959017348650));
|
|
print_fangs(14593825548650, fangs(14593825548650));
|
|
}
|
|
|
|
#[test]
|
|
fn test() {
|
|
assert_eq!(
|
|
fangs(16758243290880),
|
|
vec![1982736, 2123856, 2751840, 2817360]
|
|
);
|
|
|
|
assert_eq!(
|
|
fangs(24959017348650),
|
|
vec![2947050, 2949705, 4125870, 4129587, 4230765]
|
|
);
|
|
|
|
assert_eq!(fangs(14593825548650), vec![]);
|
|
}
|