Project euler , problem 9

help
1 
fn main() {
	let mut counter = 0 ;

	for d in 1..1001 {
		println!("d is {}",d);
		for e in d..1001 {

			println!("{}",e);

			let base = d as f64;
			let height = e as f64; 
			let hp = (d+e) as f64 ;
			if (base.powi(2)+height.powi(2))==hp.powi(2) {	
				counter+=1;
				println!("{}",counter);
			}
   		}
	}
 println!("triplets are #{} in number",counter);
}

the task is to find all Pythagorean triplets under 1000 and I came up with the above solution
that looks logically sound to me, but the condition is never true and no triplet is found, whereas several exists for real, where am I wrong?

2

Try this playground. I guess it has to do with precision.

1 Like
3

First of all using == with floating number is generally not a good idea because of precision. You can keep integer, using a*a + b*b == c*c in the if condition.

But the major problem I see is why hp = d+e ?
If I read the statement at #9 Special Pythagorean triplet - Project Euler correctly we want a+b+c=1000.

If you really want every Pythagorean triplets then you must add a 3rd for loop for your hp.

A clever way would be to only generate triplet were their sum is 1000 and then test for the Pythagorean property.

1 Like
4

A soluation is here. Is it possible to lower counter ?

1 Like
5

I think you have to exclude not coprime triplets

6

You can because a < b < c, see here

a must be lower to 334 because if not it violate the inequality.
and b must be greater than a and lower than half of the remaining amount to 1000.

And if you trust the statement, you can break when you found the first solution, as it say there is only one.

2 Likes
7

I got the idea (you need to press share then permalink).
It got faster, here.

1 Like
8

thanks

9

thanks mate

10

Just ported my solution. I hope it is not too much of a spoiler: just generating all partitions and then filtering out the triplets, that's all. You might want to speed it up and get rid of memory allocations.

fn partitions(n: u32, k: u32, max: u32) -> Vec<Vec<u32>> {
    if n == 0 {
        return vec![vec![]];
    } else if n > k * max {
        return vec![];
    } else if n == k * max {
        return vec![vec![max; k as usize]];
    } else if k == 1 {
        return vec![vec![n]];
    } else {
        let mut a: Vec<Vec<u32>> = vec![];
        for x in 1..max.min(n - 1) + 1 {
            for mut t in partitions(n - x, k - 1, x) {
                t.push(x);
                a.push(t);
            }
        }
        return a;
    }
}

fn triplets(n: u32) -> Vec<Vec<u32>> {
    partitions(n, 3, n)
        .into_iter()
        .filter(|t| t[0] * t[0] + t[1] * t[1] == t[2] * t[2])
        .collect()
}

fn main() {
    println!("{:?}", triplets(1000));
}
11