Problem 44 "Pentagon numbers"

Pentagonal numbers are generated by the formula, Pn=n(3n−1)/2. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

It can be seen that P4 + P7 = 22 + 70 = 92 = P8. However, their difference, 70 − 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, Pj and Pk, for which their sum and difference are pentagonal and D = |Pk − Pj| is minimised; what is the value of D?

問 44 「五角数」

五角数は \(P_{n} = n(3n-1)/2 \) で生成される. 最初の10項は

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

である.

\( P_{4} + P_{7} = 22 + 70 = 92 = P_{8} \) である. しかし差 70 - 22 = 48 は五角数ではない.

五角数のペア \( P_{j} \) と \( P_{k} \) について, 差と和が五角数になるものを考える. 差を D = \( |P_{k} - P_{j}| \) と書く. 差 D の最小値を求めよ.

fn is_pentagonal(n: u64) -> bool {
    let expr = 24 * n + 1;
    let sqrt = (expr as f64).sqrt() as u64;
    if expr != sqrt * sqrt {
        return false;
    }
    sqrt % 6 == 5
}

fn pentagon(n: u64) -> u64 {
    n * (3 * n - 1) / 2
}

fn calc_distance(pentagons: &mut Vec<u64>) -> (u64, u64) {
    for n in 1u64.. {
        let p1 = pentagon(n);
        for &p2 in pentagons.iter().rev() {
            let d = p1 - p2;
            let s = p1 + p2;
            if is_pentagonal(d) && is_pentagonal(s) {
                return (d, n);
            }
        }
        pentagons.push(p1);
    }
    unreachable!("This function is supposed to have return but not break in the outermost loop!");
}

fn is_answer_confirmed(pentagons: &mut Vec<u64>, distance: u64, nth: u64) -> bool {
    pentagons.push(pentagon(nth));
    for n in nth + 1.. {
        let p1 = pentagon(n);
        if 3 * (n - 1) + 1 > distance {
            return true;
        }
        for &p2 in pentagons.iter().rev() {
            let d = p1 - p2;
            if d >= distance {
                break;
            }
            let s = p1 + p2;
            if is_pentagonal(d) && is_pentagonal(s) {
                return false;
            }
        }
        pentagons.push(p1);
    }
    unreachable!("This function is supposed to have return but not break in the outermost loop!");
}

fn main() {
    let mut pentagons = vec![];
    let (d, nth) = calc_distance(&mut pentagons);
    assert!(is_answer_confirmed(&mut pentagons, d, nth));

    println!("{}", d);
    assert_eq!(d, 5482660);
}