home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / modula2 / library / modula1 / sumofcub.mod < prev    next >
Text File  |  1987-06-11  |  2KB  |  50 lines
  1. (* Find the cmallest positive integer that can be represented
  2.    as the sum of two cubes (integers raised to the third power)
  3.    in two different ways. *)
  4.  
  5. MODULE sumofcubes;
  6.  
  7. FROM  InOut IMPORT WriteString, WriteCard, WriteLn;
  8.  
  9. VAR i,ih,il,min,a,b,k: CARDINAL;
  10.     j,sum,pwr: ARRAY [1..200] OF CARDINAL;
  11.         (* pwr[k] = power of k, sum[k] = p[k] + p[j[k]],
  12.            j[k] = columnindex of last considered candidate in row k,
  13.            ih = rowindex of highest considered fow,
  14.            il = rowindex of least still relevant row *)
  15.  
  16. BEGIN
  17.   i := 1; il := 1; ih := 2;
  18.   j[1] := 1; j[2] := 1;
  19.   pwr[1] := 1; pwr[2] := 8;
  20.   sum[1] := 2; sum[2] := 9;
  21.   REPEAT
  22.     min := sum[i];
  23.     a := i; b := j[i];
  24.       (* now get the sum in rw i *)
  25.     IF j[i] = i THEN
  26.       INC(il);
  27.     ELSE
  28.       IF j[i] = 1 THEN
  29.           (* the new min was from the first column, now add
  30.             a new row before taking the new sum from the old row *)
  31.         INC(ih);
  32.         pwr[ih] := ih*ih*ih;
  33.         j[ih] := 1;
  34.         sum[ih] := pwr[ih] + 1
  35.       END;
  36.       j[i] := j[i] + 1;
  37.       sum[i] := pwr[i] + pwr[j[i]]
  38.     END;
  39.       (* now find minimal candidate in rows ol..ih *)
  40.     i := il; k := i+1;
  41.     WHILE k <= ih DO
  42.       IF sum[k] < sum[i] THEN i := k END;
  43.       INC(k)
  44.     END
  45.   UNTIL sum[i] = min;
  46.   WriteCard(min,6); WriteCard(a,6);
  47.   WriteCard(b,6); WriteCard(i,6);
  48.   WriteCard(j[i],6); WriteLn
  49. END sumofcubes.
  50.