Problem 62 "Cubic permutations"

The cube, 41063625 (3453), can be permuted to produce two other cubes: 56623104 (3843) and 66430125 (4053). In fact, 41063625 is the smallest cube which has exactly three permutations of its digits which are also cube.

Find the smallest cube for which exactly five permutations of its digits are cube.

問 62 「立方数置換」

立方数 41063625 (3453) は, 桁の順番を入れ替えると2つの立方数になる: 56623104 (3843) と 66430125 (4053) である. 41063625は, 立方数になるような桁の置換をちょうど3つもつ最小の立方数である.

立方数になるような桁の置換をちょうど5つもつ最小の立方数を求めよ.

use std::collections::HashMap;

fn freq(mut n: u64) -> u64 {
    let mut freq = 0u64;
    while n > 0 {
        freq += 0b000001 << ((n % 10) * 6);
        n /= 10;
    }
    freq
}

fn min(counts: &HashMap<u64, (u8, u16)>, count: u8) -> Option<&u16> {
    counts
        .iter()
        .filter(|(_, (c, _))| *c == count)
        .map(|(_, (_, n))| n)
        .min()
}

fn cubic_permutations(permutation: u8) -> u64 {
    assert!(permutation > 2);
    let mut counts: HashMap<u64, (u8, u16)> = HashMap::new();
    let mut digits = 1u64;
    while digits < 100u64.pow(3) {
        digits *= 10;
    }
    for n in 100u16.. {
        let cube = (n as u64).pow(3);
        if digits as f32 / cube as f32 <= 1f32 {
            if let Some(&n) = min(&counts, permutation) {
                return (n as u64).pow(3);
            }
            counts.clear();
            digits *= 10;
        }
        let freq = freq(cube);
        if let Some((cnt, _)) = counts.get_mut(&freq) {
            *cnt += 1;
            continue;
        }
        counts.insert(freq, (1, n));
    }
    unreachable!();
}

fn main() {
    {
        let ans = cubic_permutations(3);
        println!("{}", ans);
        assert_eq!(ans, 41063625);
    }
    {
        let ans = cubic_permutations(4);
        println!("{}", ans);
        assert_eq!(ans, 1006012008);
    }
    {
        let ans = cubic_permutations(5);
        println!("{}", ans);
        assert_eq!(ans, 127035954683);
    }
    {
        let ans = cubic_permutations(6);
        println!("{}", ans);
        assert_eq!(ans, 1000600120008);
    }
}