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 (minmax):  91.444 μs152.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 (minmax):  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.