Problem 43 "Sub-string divisibility"

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:

  • d2d3d4=406 is divisible by 2
  • d3d4d5=063 is divisible by 3
  • d4d5d6=635 is divisible by 5
  • d5d6d7=357 is divisible by 7
  • d6d7d8=572 is divisible by 11
  • d7d8d9=728 is divisible by 13
  • d8d9d10=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

問 43 「部分文字列被整除性」

数1406357289は0から9のパンデジタル数である (0から9が1度ずつ現れるので). この数は部分文字列が面白い性質を持っている.

\( d_{1} \) を上位1桁目, \( d_{2} \)を上位2桁目の数とし, 以下順に \( d_{n} \) を定義する. この記法を用いると次のことが分かる.

  • d2d3d4=406 は 2で割り切れる
  • d3d4d5=063 は 3で割り切れる
  • d4d5d6=635 は 5で割り切れる
  • d5d6d7=357 は 7で割り切れる
  • d6d7d8=572 は 11で割り切れる
  • d7d8d9=728 は 13で割り切れる
  • d8d9d10=289 は 17で割り切れる

このような性質をもつ0から9のパンデジタル数の総和を求めよ.

fn is_divisible(n: u64, depth: u8) -> bool {
    if depth < 2 || depth == 9 {
        return true;
    }
    let p = match depth {
        2 => 17,
        3 => 13,
        4 => 11,
        5 => 7,
        6 => 5,
        7 => 3,
        8 => 2,
        _ => unreachable!(),
    };
    (n / 10u64.pow(depth as u32 - 2)) % p == 0
}

fn consume(
    usable_items: &Vec<u8>,
    accumulated_num: u64,
    drain: &mut Vec<u64>,
    depth: u8,
) {
    if usable_items.len() == 0 {
        drain.push(accumulated_num);
        return;
    }
    for i in 0..usable_items.len() {
        let mut items = usable_items.clone();
        let mut num = accumulated_num.clone();
        let n = items.remove(i);
        let weight = 10u64.pow(depth as u32);
        num += weight * n as u64;
        if !is_divisible(num, depth) {
            continue;
        }
        consume(&items, num, drain, depth + 1);
    }
}

fn permutations_with_conditions() -> Vec<u64> {
    let items = (0..=9).into_iter().collect::<Vec<u8>>();
    let mut drain = vec![];
    consume(&items, 0, &mut drain, 0);
    drain
}

fn main() {
    let sum = permutations_with_conditions()
        .iter()
        .filter(|&n| *n > 999_999_999)
        .sum::<u64>();

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

fn is_divisible(n: u64, depth: u8) -> bool {
    if depth < 3 {
        return true;
    }
    let p = match depth {
        3 => 2,
        4 => 3,
        5 => 5,
        6 => 7,
        7 => 11,
        8 => 13,
        9 => 17,
        _ => unreachable!(),
    };
    (n % 1000) % p == 0
}

fn consume(
    usable_items: &Vec<u8>,
    accumulated_num: u64,
    drain: &mut Vec<u64>,
    depth: u8,
) {
    if usable_items.len() == 0 {
        drain.push(accumulated_num);
        return;
    }
    for i in 0..usable_items.len() {
        let mut items = usable_items.clone();
        let mut num = accumulated_num.clone();
        let n = items.remove(i);
        num *= 10;
        num += n as u64;
        if !is_divisible(num, depth) {
            continue;
        }
        consume(&items, num, drain, depth + 1);
    }
}

fn permutations_with_conditions() -> Vec<u64> {
    let items = (0..=9).into_iter().collect::<Vec<u8>>();
    let mut drain = vec![];
    consume(&items, 0, &mut drain, 0);
    drain
}

fn main() {
    let sum = permutations_with_conditions()
        .iter()
        .filter(|&n| *n > 999_999_999)
        .sum::<u64>();

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