We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #9: Special Pythagorean triplet
  4. Discussions

Project Euler #9: Special Pythagorean triplet

Sort by

recency

|

170 Discussions

|

  • jordkris
     + 0 comments

    Solution in python :

    t = int(input().strip())
for _ in range(t):
    N = int(input().strip())
    max_product = -1

    for a in range(1, N // 3):
        b = (N * (N - 2 * a)) // (2 * (N - a))
        c = N - a - b
        if a < b < c and a * a + b * b == c * c:
            max_product = max(max_product, a * b * c)
    
    print(max_product)

  • yonahel
     + 0 comments

    Haskell, used Euclid's Formula

    import Control.Applicative
import Control.Monad
import System.IO
import Data.Set


py_trips :: Int -> [Int] 
py_trips max = [x * y * z * (max `div` (x+y+z))^3 | 
                            m <- [2..(max `div` 6)], n <- [1..(max `div` 12)],
                            m > n, 
                            let x = ((m*m) - (n*n)), 
                            let y = (2*m*n),
                            let z = ((m*m) + (n*n)),
                            max `mod` (x+y+z) == 0] 

py_max :: [Int] -> Int
py_max [] = -1
py_max n = maximum n 
    
main :: IO ()
main = do
    t_temp <- getLine
    let t = read t_temp :: Int
    forM_ [1..t] $ \a0  -> do
        n_temp <- getLine
        let n = read n_temp :: Int
        let trips = py_max (py_trips n)
        print (trips)

  • kamil_m_antoncz1
     + 1 comment

    We know that c = n - a - b

    But also we know that a^2 + b^2 = c^2

    So after substutions we can calculate relation between a and b given that n=const.

    So we can substitute everything into a*b*c and get some complicated function. After some more math magic on paper I've came up with neat solution. It's guaranteed that the first solution is already the best one. 

    def bound(n):
    return int(n*(1-math.sqrt(2)/2))

def calc_b(n, a):
    return n*(2*a-n)/(2*a-2*n)

def pit(n):
    for a in range(bound(n), 0, -1):
        if (f_b := calc_b(n, a)) == (b := int(f_b)):
            return a*b*(n-a-b)
    return -1

  • thomas_anthony_1
     + 0 comments

    Do they want the primitive triplet or the triplet multiplied by the factor n/(a+b+c)

  • mariusbugiulescu
     + 0 comments

    Maybe it can still be optimized:

    using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {

    static void Main(String[] args) {
        int[] products = new int[30001]; //we store repeated inputs here
        
        int t = Convert.ToInt32(Console.ReadLine());
        for(int a0 = 0; a0 < t; a0++)
        {
            int n = Convert.ToInt32(Console.ReadLine());
            int product;
            if (products[n] == 0)
            {
                products[n] = -1;
                product = -1;
                for (int c = n/3; c <= n/2; c++)
                {
                    for (int b = 1; b < c; b++)
                    {
                        int a = n - c - b;
                        if (a <= b) //we want a <= b < c
                        {
                            if (a * a + b * b == c * c)
                            {
                                if (a * b * c > product)
                                {
                                    product = a * b * c;
                                    products[n] = product;
                                }
                            }
                        }
                    }
                }
            }
            Console.WriteLine(products[n]);

        }
    }
}