EWD249 - 83

on this level of description one can ignore that the transition from one solution to the next takes place via a sequence of trial solutions that turn out to be failures.

I owe to Joe Weizenbaum the second example. Make a program that, for given positive integer n, determines the smallest number s that can be decomposed into the sum of two n-th powers in at least two non-trivially different ways.

(for n = 1      s = 2 = 0^1 + 2^1 = 1^1 + 1^1
     n = 2      s = 25 = 0^2 + 5^2 = 3^2 + 4^2
     n = 3      s = 1729 = 1^3 + 12^3 = 9^3 + 10^3
     n = 4      s = 635318657 = 59^4 + 158^4 = 133^4 + 134^4 )

When I first used this example in an oral examination, it took the student twenty minutes to get somewhat familiar with the problem and he then sketched a searching algorithm which -when patched up- could indeed find a number that allowed multiple decompositions into sums of two n-th powers, but he could not prove that when his algorithm produced a value s that it would be the minimum value. (As a matter of fact he had, up till then, ignored that part of the problem statement.)

He then regrouped his forces and made a program of the following form:

"integer s, k;
s:= 1;
repeat s:= s + 1;
       k:= "the number of ways in which s can be decomposed as the sum
             of two n-th powers"
until k > 1

thus arriving at a hopelessly inefficient algorithm. The error he made was the decision at too early a stage to investigate the natural numbers in succession, the overwhelming majority of which are not decomposable at all. Reasoning that the value we are looking for is the smallest decomposable number satisfying an additional property, one comes to an algorithm whose first sketch could be