Problem 36 "Double-base palindromes"

The decimal number, 585 = 10010010012 (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

問 36 「二種類の基数による回文数」

585 = 10010010012 (2進) は10進でも2進でも回文数である.

100万未満で10進でも2進でも回文数になるような数の総和を求めよ.

(注: 先頭に0を含めて回文にすることは許されない.)

fn generate_even_and_odd_palindromes(mut n: u32) -> (u32, u32) {
    let mut ep = n.clone();
    let mut op = n.clone();
    op /= 10;
    while n > 0 {
        ep *= 10;
        op *= 10;
        ep += n % 10;
        op += n % 10;
        n /= 10;
    }
    (ep, op)
}

fn is_double_based_palindrome(a: u32) -> bool {
    if a % 2 == 0 {
        return false;
    }
    let mut t = a.clone();
    let mut b = 0u32;
    while t > 0 {
        b <<= 1;
        b |= t & 1;
        t >>= 1;
    }
    a == b
}

fn main() {
    let mut sum = 0u32;
    let half = 10u32.pow(1_000_000f32.log10() as u32 / 2);
    for n in 1..half {
        let (ep, op) = generate_even_and_odd_palindromes(n);
        if is_double_based_palindrome(ep) {
            sum += ep;
        }
        if is_double_based_palindrome(op) {
            sum += op;
        }
    }

    println!("{}", sum);
    assert_eq!(sum, 872187);
}

fn is_palindrome(a: u32) -> bool {
    if a % 2 == 0 && a % 11 != 0 {
        return false;
    }
    let mut t = a.clone();
    let mut b = 0u32;
    while t > 0 {
        b *= 10;
        b += t % 10;
        t /= 10;
    }
    a == b
}

fn is_double_based_palindrome(a: u32) -> bool {
    if a % 2 == 0 {
        return false;
    }
    let mut t = a.clone();
    let mut b = 0u32;
    while t > 0 {
        b <<= 1;
        b |= t & 1;
        t >>= 1;
    }
    a == b
}

fn main() {
    let sum = (1..1_000_000)
        .step_by(2)
        .filter(|&n| is_palindrome(n))
        .filter(|&n| is_double_based_palindrome(n))
        .sum::<u32>();

    println!("{}", sum);
    assert_eq!(sum, 872187);
}