7
$\begingroup$

I'm working on project euler 9 and I've solved it various ways. I'm using these problems to learn functional programing techniques. I'm now attempting to mimic my friend Chris recursive elixir solution:

defmodule PythagoreanTriplet do
  def find_triplet(a \\ 1, b \\ 2) do
    c = :math.pow(a, 2) + :math.pow(b, 2) |> :math.sqrt
    cond do
      a + b + c == 1000.0 -> IO.puts "#{a} * #{b} * #{c} = #{a * b * c}"
      b < 500 -> find_triplet(a, b + 1)
      a < 500 -> find_triplet(a + 1, a + 2)
      true -> IO.puts "I don't know"
    end
  end
end

PythagoreanTriplet.find_triplet

Here is my attempt in Mathematica:

Clear[findTriple]
findTriple[a0_, b0_] := findTriple[a0, b0] =
  Module[
   {a = a0, b = b0, c = Sqrt[a0^2 + b0^2]},
   Which[a + b + c == 1000, Print[a*b*c],
    b < 500, findTriple[a, b + 1],
    a < 500, findTriple[a + 1, a + 2]
    ]
   ]
findTriple[1, 2]

I'm getting $RecursionLimit: Recursion depth of 1024 exceeded during evaluation errors. I've read through related posts and I'm over my head. Thank you.

$\endgroup$
2
  • 1
    $\begingroup$ No recursion needed: FindInstance[a^2 + b^2 == c^2 ∧ a + b + c == 1000 ∧ a < b < c ∧ {a, b, c} ∈ Integers ∧ {a, b, c} > 0, {a, b, c}, 1] $\endgroup$
    – Edmund
    Nov 13, 2016 at 17:04
  • $\begingroup$ Thanks =) I'm using this problem as a way to understand recursion. $\endgroup$
    – Matt Green
    Nov 14, 2016 at 17:07

2 Answers 2

7
$\begingroup$

It can be done with a recursive function that uses Which, but that function won't be able to compute the answer for large values of the sum. Here is how such a recursive function is properly written.

Clear[findTriple]
findTriple[sum_, a_: 1, b_: 2] :=
  Block[{$RecursionLimit = 100000, c = Sqrt[a^2 + b^2]},
    Which[
      a + b + c == sum, {a, b, c},
      b <= sum/2, findTriple[sum, a, b + 1],
      a <= sum/2, findTriple[sum, a + 1, a + 2],
      True, Failed[a, b, c]]]

With this definition

findTriple[420]

{28, 195, 197}

works on my computer, but

findTriple[421]

doesn't complete because it runs out of memory.

So does this mean Mathematica can't solve the problem recursively. No, it doesn't. It means we must be more careful about how we write the recursion; we must make it tail-recursive, like so:

Clear[helper]
helper[sum_, a_, b_] /; a + b + Sqrt[a^2 + b^2] == sum := {a, b, Sqrt[a^2 + b^2]}
helper[sum_, a_, b_] /; b <= sum/2 := helper[sum, a, b + 1]
helper[sum_, a_, b_] /; a <= sum/2 := helper[sum, a + 1, a + 2]
helper[_, a_, b_] := Failed[a, b, Sqrt[a^2 + b^2]]

Clear[findTriple]
findTriple[sum_] :=
  Block[{$IterationLimit = 100000}, helper[sum, 1, 2]]

findTriple[1000]

{200, 375, 425}

Since all the real work is done when the righthand side of helper is evaluated, this version is both fast and uses little memory.

$\endgroup$
1
  • $\begingroup$ Thank you! This is the help I needed to better understand how recursion works here. $\endgroup$
    – Matt Green
    Nov 14, 2016 at 17:09
6
$\begingroup$

To avoid the Recursion error you can instead use NestWhile, which effectively implement the same logic in a more efficient manner:

NestWhile[
 Which[
   #[[2]] < 500, {#[[1]], #[[2]] + 1},
   #[[1]] < 500, {#[[1]] + 1, #[[1]] + 2},
   True, Abort[]
   ] &,
 {1, 2},
 (Total@# + Norm@# != 1000) &
 ]
(* Out[1]= {200, 375} *)

An easy way to solve the problem without using recursion is to instead just use SelectFirst, as in:

SelectFirst[
 Subsets[Range@500, {2}],
 Norm@# + Total@# == 1000 &
 ]

Also, for a much faster solution, you should have a look at Mr.Wizard's function to generate Pythagorean triples. Using his function and SelectFirst, the solution of the problem is obtained immediately with:

SelectFirst[
 genPTunder[500],
 Total@# == 1000 &
 ]
$\endgroup$
1
  • $\begingroup$ Thank you. I love the use of the pure functions. That's on my list to mess with also. $\endgroup$
    – Matt Green
    Nov 14, 2016 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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