Skip to main content
Code Review

Return to Answer

correction to logic
Source Link
mascoj
mascoj
  • 431
  • 4
  • 7

Some interesting things no one have mentioned about this, but it is an improvement when looking for the smallest solution:

If the \$\gcd(a,b,c) \neq 1\$ then \$a^4\$,\$b^4\$,\$c^4\$ and \$d^4\$ are all divisible by that gcd to the 4th power, giving a smaller solution.

Therefore, at least one of \$a\$,\$b\$, and \$c\$ must be odd, since if they are all even the gcd isthey share a common divisor of 2, meaning the \$\gcd(a,b,c) \geq 2\$. By checking that they aren't all even, before performing the loop for d, you will cut your possible search set by a large amount.

Along these same lines, if \$d\$ is even, then 2 must divide \$a^4 + b^4 + c^4\$, but we already mentioned that they can't all be even to be the smallest solution. If two (or zero) out of the three variables are even then the sum of their 4th powers is going to be odd (even + even + odd = odd; odd + odd + odd = odd), thus if d is even then 1 number must be even and the other 2 are odd.

If \$d\$ is odd, then 2 cannot divide \$a^4 + b^4 + c^4\$. If only 1 of the numbers is even, then then the sum of their 4th powers is going to be even (even + odd + odd = even). By this either they are all odd or only 1 is odd.

Using this you can decide if D is odd or even based on the set of \$a,b,c\$ cutting your solution set in half by tailoring the innermost loop accordingly. In conjunction with the increasing values d>c>b>a, this should improve your processing by a large margin.

Some interesting things no one have mentioned about this, but it is an improvement when looking for the smallest solution:

If the \$\gcd(a,b,c) \neq 1\$ then \$a^4\$,\$b^4\$,\$c^4\$ and \$d^4\$ are all divisible by that gcd to the 4th power, giving a smaller solution.

Therefore, at least one of \$a\$,\$b\$, and \$c\$ must be odd, since if they are all even the gcd is 2. By checking that they aren't all even, before performing the loop for d, you will cut your possible search set by a large amount.

Along these same lines, if \$d\$ is even, then 2 must divide \$a^4 + b^4 + c^4\$, but we already mentioned that they can't all be even to be the smallest solution. If two (or zero) out of the three variables are even then the sum of their 4th powers is going to be odd (even + even + odd = odd; odd + odd + odd = odd), thus if d is even then 1 number must be even and the other 2 are odd.

If \$d\$ is odd, then 2 cannot divide \$a^4 + b^4 + c^4\$. If only 1 of the numbers is even, then then the sum of their 4th powers is going to be even (even + odd + odd = even). By this either they are all odd or only 1 is odd.

Using this you can decide if D is odd or even based on the set of \$a,b,c\$ cutting your solution set in half by tailoring the innermost loop accordingly. In conjunction with the increasing values d>c>b>a, this should improve your processing by a large margin.

Some interesting things no one have mentioned about this, but it is an improvement when looking for the smallest solution:

If the \$\gcd(a,b,c) \neq 1\$ then \$a^4\$,\$b^4\$,\$c^4\$ and \$d^4\$ are all divisible by that gcd to the 4th power, giving a smaller solution.

Therefore, at least one of \$a\$,\$b\$, and \$c\$ must be odd, since if they are all even they share a common divisor of 2, meaning the \$\gcd(a,b,c) \geq 2\$. By checking that they aren't all even, before performing the loop for d, you will cut your possible search set by a large amount.

Along these same lines, if \$d\$ is even, then 2 must divide \$a^4 + b^4 + c^4\$, but we already mentioned that they can't all be even to be the smallest solution. If two (or zero) out of the three variables are even then the sum of their 4th powers is going to be odd (even + even + odd = odd; odd + odd + odd = odd), thus if d is even then 1 number must be even and the other 2 are odd.

If \$d\$ is odd, then 2 cannot divide \$a^4 + b^4 + c^4\$. If only 1 of the numbers is even, then then the sum of their 4th powers is going to be even (even + odd + odd = even). By this either they are all odd or only 1 is odd.

Using this you can decide if D is odd or even based on the set of \$a,b,c\$ cutting your solution set in half by tailoring the innermost loop accordingly. In conjunction with the increasing values d>c>b>a, this should improve your processing by a large margin.

Source Link
mascoj
mascoj
  • 431
  • 4
  • 7

Some interesting things no one have mentioned about this, but it is an improvement when looking for the smallest solution:

If the \$\gcd(a,b,c) \neq 1\$ then \$a^4\$,\$b^4\$,\$c^4\$ and \$d^4\$ are all divisible by that gcd to the 4th power, giving a smaller solution.

Therefore, at least one of \$a\$,\$b\$, and \$c\$ must be odd, since if they are all even the gcd is 2. By checking that they aren't all even, before performing the loop for d, you will cut your possible search set by a large amount.

Along these same lines, if \$d\$ is even, then 2 must divide \$a^4 + b^4 + c^4\$, but we already mentioned that they can't all be even to be the smallest solution. If two (or zero) out of the three variables are even then the sum of their 4th powers is going to be odd (even + even + odd = odd; odd + odd + odd = odd), thus if d is even then 1 number must be even and the other 2 are odd.

If \$d\$ is odd, then 2 cannot divide \$a^4 + b^4 + c^4\$. If only 1 of the numbers is even, then then the sum of their 4th powers is going to be even (even + odd + odd = even). By this either they are all odd or only 1 is odd.

Using this you can decide if D is odd or even based on the set of \$a,b,c\$ cutting your solution set in half by tailoring the innermost loop accordingly. In conjunction with the increasing values d>c>b>a, this should improve your processing by a large margin.