Problem 9

Problem

A Pythagorean triplet is a set of three natural numbers, \(a \lt b \lt 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\).

Julia

function p9()
    for a ∈ 1:999
        for b ∈ 1:999            
            c = 1000 - a - b
            c >= 1 || continue
            a^2 + b^2 == c^2 || continue                        
            return a, b, c
        end
    end
end;

p9()

(200, 375, 425)

using BenchmarkTools;
@benchmark p9()

BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  91.444 μs … 152.590 μs  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     92.125 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   92.851 μs ±   6.246 μs  ┊ GC (mean ± σ):  0.00% ± 0.00%
  █ ▂                                                          ▁
  ████▄▄▃▄▄█▆▁▄▁▄▃▁▃▄▁▁▃▁▁▁▃▁▁▁▁▃▁▁▁▁▁▁▁▃▁▁▁▃▁▁▃▁▁▁▁▁▁▃▁▃▁▁▁▁▇ █
  91.4 μs       Histogram: log(frequency) by time       138 μs <
 Memory estimate: 0 bytes, allocs estimate: 0.

Julia (using JuMP)

using JuMP; using SCIP;

function p9()
  model = Model(SCIP.Optimizer)
  set_silent(model)
  @variable(model, a >= 1, Int)
  @variable(model, b >= 1, Int)
  @variable(model, c >= 1, Int)
  @objective(model, Min, a)
  @constraint(model, pitagorean, a^2 + b^2 == c^2)
  @constraint(model, sum_1000, a + b + c == 1000)  
  optimize!(model)    
  return value(a), value(b), value(c)
end;
p9()

(200.0, 375.0, 425.0)

using BenchmarkTools;
@benchmark p9()

BenchmarkTools.Trial: 56 samples with 1 evaluation.
 Range (min … max):  88.545 ms …  95.198 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     89.143 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   89.372 ms ± 983.382 μs  ┊ GC (mean ± σ):  0.00% ± 0.00%
      ▁█▃▁  ▁█     ▁   ▁                                        
  ▄▇▁▇████▄▇██▇▄▄▁▇█▇▇▁█▁▁▁▁▄▄▄▁▁▁▁▁▁▄▁▁▁▁▁▁▁▁▁▁▁▄▁▁▁▁▁▁▁▁▁▁▁▄ ▁
  88.5 ms         Histogram: frequency by time         91.8 ms <
 Memory estimate: 120.80 KiB, allocs estimate: 5135.