Problem 39 "Integer right triangles"

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p ≤ 1000, is the number of solutions maximised?

問 39 「整数の直角三角形」

辺の長さが \( {a,b,c} \) と整数の3つ組である直角三角形を考え, その周囲の長さを p とする. p = 120のときには3つの解が存在する:

{20,48,52}, {24,45,51}, {30,40,50}

p ≤ 1000 のとき解の数が最大になる p はいくつか?


fn gcd(mut a: usize, mut b: usize) -> usize {
    assert!(a != 0 && b != 0);
    while b != 0 {
        let r = a % b;
        a = b;
        b = r;
    }
    a
}

fn main() {
    let mut counts = [0u8; 1001];
    for p in (12..=1000).step_by(2) {
        for m in 2..=(((p - 2) / 2) as f32).sqrt() as usize {
            for n in ((if m % 2 == 0 { 1 } else { 2 })..m).step_by(2) {
                let a = m * m - n * n;
                let b = 2 * m * n;
                let c = m * m + n * n;
                if a + b + c == p && gcd(m, n) == 1 {
                    for k in (p..=1000).step_by(p) {
                        counts[k] += 1;
                    }
                }
            }
        }
    }
    let (p, _) = counts
        .iter()
        .enumerate()
        .reduce(|(ap, a), (bp, b)| if *a > *b { (ap, a) } else { (bp, b) })
        .unwrap();

    println!("{}", p);
    assert_eq!(p, 840);
}

fn main() {
    let mut counts = [0u8; 1001];
    for c in 3..=997 {
        let mut b = 2;
        while b < 1000 - c && b < c {
            let mut a = 1;
            while a <= 1000 - c - b && a < b {
                if c * c == b * b + a * a {
                    counts[c + b + a] += 1;
                }
                a += 1;
            }
            b += 1;
        }
    }
    let (p, _) = counts
        .iter()
        .enumerate()
        .reduce(|(ap, a), (bp, b)| if *a > *b { (ap, a) } else { (bp, b) })
        .unwrap();

    println!("{}", p);
    assert_eq!(p, 840);
}