1
\$\begingroup\$

Question:

Special Pythagorean triplet, Euler Problem 9

A Pythagorean triplet is a set of three natural numbers, \$a<b<c\$, for which, $$a^2+b^2=c^2$$ For example, \$3^2+4^2=9+16=25=5^2\$.

There exists exactly one Pythagorean triplet for which \$a+b+c=1000\$.

Find the product \$abc\$.

I got the code to work using algebraic simplifications shown below.

Given:

\$num=1000\$

\$a+b+c=1000\$

\$a^2+b^2+c^2+2ab+2bc+2ca=num^2\$

\$a^2+b^2=c^2\$

Thus:

$$2c^2+2ab+2bc+2ca=num^2$$ $$c(c+b)+a(b+c)=\frac{num^2}{2}=500num$$ $$(a+c)(b+c)=500num$$ $$(num-b)(num-a)=500num$$ $$num-b=\frac{500num}{num-a}$$ $$b=num-\frac{500num}{num-a}$$

So, I scan through \$a\$ and if I receive an integer value for \$b\$ we have found \$b\$, and thus \$c\$ can be found through the equation \$c=num-a-b\$.

The upper limit of \$a\$ is found by assuming that \$a\$ is the smallest among the three integers, \$a\$, \$b\$, and \$c\$ such that \$a<b<c\$. Following this assumption, let's find the max condition by rewriting \$b\$ and \$c\$ in terms of \$a\$. So, \$b = a+n\$ and \$c = a+k\$ where \$n<k\$, so that \$a<b<c\$ remains true.

Now:

$$a+b+c=num$$ $$a+(a+n)+(a+k)=num$$ $$3a+n+k=num$$ $$3a=num-(n+k)$$ $$a=\frac{num-(n + k)}{3}$$

Now, the max acceptable value of \$a\$ according to the equation could be when \$n=1\$, and \$k=2\$ since \$a<b<c\$. In other words, the difference between the values is 1.

Therefore we loop \$a\$ up to \$\frac{num}{3} - 1\$

My code manages a runtime of ~0.166526 ms:

public class Java {

public static void main(String[] args) {


    double num = 1000.0;
    double b = 0;

    for(int a = 2 ; a <= (num/3 - 1); a++){
          b = ( num - ( 500*num / (num-a)));

          if(b == (int)b){
              System.out.println((int)(a*b*(num-a-b)));
              break;
          }

    }


}

Any suggestions for setting a lower limit for \$a\$ and probably speeding up the algorithm? The upper limit seems odd since I just used \$a+b+c=1000\$ when finding it instead of the Pythagorean Theorem.

\$\endgroup\$
  • 1
    \$\begingroup\$ Why bother with the \$number\$ variable? It just adds confusion in the calculations when you could simply say 1000. You even outright state that \$number\$ is equal to 1000 in your maths when you simplify \${num^2\over 2} = 500num\$. By doing this you're also forcing the computer to recompute operations with constants each time you loop. \$\endgroup\$ – Zenohm Aug 22 '15 at 16:21
  • \$\begingroup\$ yea... you are right..... i didn't knew that this would cause any problem with computations.... ok ... so that's one edit i could do .... thnx. \$\endgroup\$ – Altamash Khan Aug 22 '15 at 16:35
  • \$\begingroup\$ @holroy Would you rather him feed us magic maths? \$\endgroup\$ – Zenohm Aug 23 '15 at 0:24
  • \$\begingroup\$ well... whats there in sharing some knowledge.... if you guys know something .... please do share..... :) and ofcourse i need a code review too...... this code can always be made better... right..... One more help guys..... can you plz plz tell how do you find the time complexity of any given code just by looking at the code... any site tutorials... plz..... \$\endgroup\$ – Altamash Khan Aug 23 '15 at 5:10
  • 1
    \$\begingroup\$ By the way - since this is a repeating theme in Euler problems. The key reduction is that (num - a) must be a divisor of (num * num/2) - in that case there are only 42 if I am not mistaken. So a much smaller number of cases to check once you constructed them. \$\endgroup\$ – bdecaf Aug 25 '15 at 9:07
3
\$\begingroup\$

Any suggestions for setting a lower limit for a and probably speeding up the algorithm? The upper limit seems odd since I just used a+b+c=1000 when finding it instead of the Pythagorean Theorem.

A better upper limit for a

$$a < b \Rightarrow a^2 < b^2 \Rightarrow 2a^2 < a^2+b^2 \Rightarrow 2a^2 < c^2 \Rightarrow 2a^2 < c^2 \Rightarrow \sqrt{2} a < c$$ $$a + a + \sqrt{2} a < a + b + c$$ $$a < \frac{(a + b + c)}{2 + \sqrt{2}}$$

Other points

@Holroy's anwer has good points. I have some additions below:

  • As for variable naming, a variable's name should indicate what it is. Instead of num, use something more like sum.

  • 500 is a magic number. If you changed num = 1000 to num = 2000 you program becomes broken. You should write your programs such that you should be able to freely change the parameters.

  • Use explanatory variables, especially in conditionals. Think of these as the parameters mentioned above. When you need to change the method you use to test if b is integer you will know where to look. You may want to extract more complex calculations as functions.

    Instead of:

    for(int a = 2 ; a <= (num/3 - 1); a++){
         ...
         if(b == (int)b) ...
    

    Say:

    int aMax = num/3 - 1;
    for(int a = 2 ; a <= aMax; a++){
         ...
         boolean bIsInteger = b == (int)b;
         if(bIsInteger) ...
    
\$\endgroup\$
  • \$\begingroup\$ thnks a lot... with a defined upper limit... i can definitely start looping from the upper loop.. instead of looping from 2 ..... that would save a bunch of time.. \$\endgroup\$ – Altamash Khan Aug 27 '15 at 9:39
  • \$\begingroup\$ thnks a lot... with a defined upper limit... i can definitely start looping from the upper loop.. instead of looping from 2 ..... that would save a bunch of time.. \$\endgroup\$ – Altamash Khan Aug 27 '15 at 9:40
4
\$\begingroup\$

There isn't much code, so that leaves little to be reviewed. I have not considered the mathematical side of this. This is also a code stub, so when reviewed out of context it is hard to do a good review.

  • Comment it – As a code stub it is hard to understand what you are trying to achieve, and as such I would problably leave a comment stating what you actually wanted to achieve. Maybe just a reference to "Special Pythagorean triplet, Euler Problem 9", or similar. And possibly some of the justification of your formulas
  • Do standard indentation – The class and the method is at the same level, which is confusing. Do indent, but keep it a standard width, like 2 or 4 spaces. The same applies for how many lines you use between statements, ending braces, methods. Keep it clean(er)
  • Keep computation in loop conditions to a minimum – In your case it will most likely be optimised by the compiler, but having computational stuff in the loop conditions, like (num/3 - 1), should be avoided. Do the calculation once in front of the loop, and make it a simple comparision in the loop condition
  • Take care when using parenthesis – You have some unneccessary parenthesis, and some which is kind of strange, I would have written it: b = num - (500*num) / (num-a) which emphasizes that the denominator and the dividend are calculated before the actual division
  • Comparing doubles and int is dangerous – In most languages a double variable is usually not checked directly for equality as the imprecision in the storage format could leave to interesting effects. See Spot the defect: rounding, part two. However this might not apply to you as you are mainly interested in a whole number and the decimal parts of it...
  • Variable naming – Nothing indicates that num is a constant, neither in the naming nor in the declaration (i.e. you could use final). And what does num mean? Is it a number, is it a constant?
  • Consider using a function – In the problem description it indicates that for other numbers you could find other pythagorean triples, which could be extended into making a method like findPythagoreanTriplet(number) which could either return the first triplet, or a list of triplets. Using a function would allow for extending the code stub into maybe doing something more useful like finding other triplets matching some criteria, or similar
  • Computation vs presentation – An alternative view on creating a function, is that you could then split the computation from the presentation, which usually is a good thing to do. This also according to the principle of single concern for a method
  • Jammed if conditions – The last few days I've seen a lot of if(someCondition){, which in my view would like nicer as if (someCondition) {. Having a little space here and there increases readability, asOpposedToNotHavingSpaces...

Do be aware that this code review is making some assumptions, and might be a little overkill for something which you might just have thrown together to solve an immediate problem you had. However, becoming a robust and good programmer, starts by doing it right from the smallest through to the largest projects.

\$\endgroup\$
  • \$\begingroup\$ ah.... Thanks a lot for sharing this... Usually i follow most the above said "principles" .... but i was in quite a hurry.. by the way.... you mentioned that it is unadvised to compare integers and doubles.... then is there any other simple method to check that the result is an integer or not ? \$\endgroup\$ – Altamash Khan Aug 23 '15 at 14:46
1
\$\begingroup\$

I just gave Euler #9 a shot myself and stumbled on this question. Since it's recent(a couple weeks ago), I'll try to add a few bits of information.

For starters, the suggestion by holroy to use modulo arithmetic would look like this:

boolean isInteger = b % 1 == 0;

Normally when there is a lot of math involved, you would include the steps you've performed, either in a comment or in the documentation in some way. So your whole thing showing

$$b=num-\frac{500num}{num-a}$$

would be visible to someone working on the code. My point here is that we can make the code look a little easier to read if we make the numerator and denominator variables themselves. Eg:

double x = Math.pow(sum, 2) / 2;
double y = sum - a;
double b = sum - (x / y);

First note that I used the idea to name num as sum. I also didn't use the $$500num$$ I used $$\frac{num^2}{2}$$ I see this as a little bit simpler, and it removes the 500 magic number. It also makes your code work should you change num to a different value.

Now, x and y aren't really meaningful names, but an actual meaningful name would be something like "bCalculationNumerator" and "bCalculationDenominator". The point of their existence is to make the code easier to read, and those names are too cumbersome to help readability. Since the above calculation would be present, a programmer who comes along to maintain the code would have no trouble understanding what you're doing. At the very least, someone reading the code would understand that these are intermediate calculations, and nothing more.

In one job I've had, we had a system for marking math. The code would have a comment giving a document number and page number for the calculation, and the document was maintained just like any other business document. Putting it all together this would look something like:

// See document 900100404 Rev D Page 32.
// b = sum - ((sum^2 / 2) / (sum - a))
double x = Math.pow(sum, 2) / 2;
double y = sum - a;
double b = sum - (x / y);

But using this kind of system also requires meticulous maintenance of the comments as well, which is possible, but it has to be part of your culture and processes; it doesn't happen magically.

In one of your comments you ask:

can you plz plz tell how do you find the time complexity of any given code just by looking at the code

This is the kind of thing that fills an entire semester at college, but for a simple system like this, the gist of it is to find the individual complexities of the loops involved, and then multiply nested loops' complexities by each other. You only have one loop, which iterates roughly a times, so the complexity of that loop is O(a). So we call that linear.

Inside of the loop is some math, but since it all uses Java's primitive types, we can consider these operations to be constant-time: O(1). So we have O(a) * O(1) which is just O(a).

However, if you were to use Java's BigInteger for larger values of sum where a, b, and c could be expected to go higher than Integer.MAX, then that's no longer the case. You would have to take the time complexities of multiplication, division, and even addition and subtraction into consideration. It would take a loooong answer to cover this complexity thoroughly, so I'll just say "it's complicated".

\$\endgroup\$
  • \$\begingroup\$ Thanks a lot for spending time and providing valuable answers.... Well. algorithms and time complexities are baffling concepts and require steady progress... Thanks for the insight on time complexity logic... :) \$\endgroup\$ – Altamash Khan Sep 15 '15 at 8:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.