program SumsPwrs;                 {Display representations of a given n
                                   as a sum of s kth powers}
{$N+,E+}
uses nothy, crt;
{$I GetInput.i }

const
  MaxN = 99999999999.0;           {10^11 - 1.  If k ò 3 then we store
                                   n^(1/k) k-th powers in an array.  Each
                                   entry occupies 8 bytes.  Thus we need
                                   8n^(1/3) < 64K}
  MaxS = 75;                      {maximum number of summands}
  MaxK = 10;                      {maximum power allowed}

var
  n,                              {number being represented}
  m,                              {sum of k-th powers of the variables}
  R,                              {total number of representaions, allowing
                                   permutations of summands}
  RD,                             {number of representations displayed}
  RZ,                             {number of representations, allowing
                                   permutations of summands and negative
                                   variables}
  t, u                            {temporary variables used in calculating
                                   multiplicity of representations}
      : comp;
  s,                              {number of summands}
  k,                              {power}
  i,                              {index of the variables}
  j,                              {index of rows on the screen}
  i0,                             {index of variable being incremented}
  code,                           {error level in converting string to input}
  x0, y0,                         {coordinates of cursor for aligning}
  lengthK                         {length of k, expressed as a string}
      : integer;
  x,                              {the variables}
  y                               {y = xý}
      : array[0..MaxS] of comp;
  z                               {z = x^k}
      : array[0..4641] of comp;
  InputOk                         {command line parameters acceptable}
      : Boolean;
  Ch                              {character read from keyboard}
      : char;
  St                              {string used in forming prompts}
      : string[80];

begin
  InputOk := False;
  if ParamCount = 3
  then
    begin
      InputOk := True;
      Val(ParamStr(1), n, code);
      if (code <> 0) or (n < 1) or (n > MaxN)
      then
        begin
          InputOk := False;
          Write('The number n begin represented must be an integer, ');
          WriteLn('1 ó n ó ', MaxN:1:0, '.')
        end;
      if InputOk
      then
        begin
          Val(ParamStr(2), s, code);                                             if (code <> 0) or (s < 2) or (s > MaxS)
          then
            begin
              InputOk := False;
              Write('The number s of summands must be an integer, ');
              WriteLn('2 ó s ó ', MaxS:1, '.')
            end
        end;
      if InputOk
      then
        begin
          Val(ParamStr(3), k, code);
          if (code <> 0) or (k < 2) or (k > MaxK)
          then
            begin
              InputOk := False;
              Write('The power k must be an integer, ');
              WriteLn('2 ó k ó ', MaxK:1, '.')
            end
        end
    end;
  if not InputOk
  then
    begin
      WriteLn;
      WriteLn('Will find all representations of a given');
      WriteLn('integer n as a sum of s k-th powers . . . ');
      str(MaxN:1:0, St);
      St := '                           (1 ó n ó ' + St + ')';
      n := GetInput(WhereX, WhereY, 'Enter number to be represented, n = ',
                    St, 0, MaxN);
      Str(MaxS:1, St);
      St := '                     (2 ó s ó '+St+')';
      s := round(GetInput(WhereX, WhereY, 'Enter number of summands, s = ',
                    St, 2, MaxS));
      Str(MaxK:1, St);
      St := '        (2 ó k ó '+St+')';
      k := round(GetInput(WhereX, WhereY, 'Enter power, k = ', St, 2, MaxK))
    end;
  str(k:1, St);
  lengthK := length(St);
  WriteLn;
  R := 0;
  RD := 0;
  RZ := 0;
  y0 := WhereY;
  GoToXY(1, 25);                  {make space at bottom of screen for prompt}
  while y0 >= 24 do
    begin
      WriteLn;
      y0 := y0 - 1
    end;
  for j := y0 + 1 to 25 do        {clear lower portion of screen}
    begin
      GoToXY(1, j);
      ClrEoL
    end;
  GoToXY(20, 25);
  Write('Searching . . . press Esc to terminate . . . ');
  if k = 2
  then
    begin
      for i := 1 to s-1 do
        begin
          x[i] := 0;
          y[i] := 0
        end;
      i0 := s-1;
      repeat
        m := 0;
        for i := 1 to s-1 do m := m + y[i];
        if m + y[s-1] <= n
        then
          begin
            x[s] := sqrt(n-m);    {x[s] is the integer nearest û(n-m) }
            y[s] := sqr(x[s]);
            if m + y[s] = n       {a representation has been found}
            then
              begin
                GoToXY(1, 25);
                ClrEoL;
                GoToXY(1, y0);
                if RD = 0
                then
                  begin
                    Write(n:1:0, ' ');
                    x0 := WhereX
                  end;
                RD := RD + 1;
                t := 1;
                j := 1;
                for i := 1 to s do
                  begin
                    if (i > 1) and (x[i] = x[i-1])
                    then j := j + 1
                    else j := 1;
                    t := t*i/j
                  end;
                R := R + t;
                u := 1;
                for i := 1 to s do if x[i] > 0 then u := 2*u;
                RZ := RZ + t*u;
                GoToXY(x0, WhereY);
                Write('= ');
                for i := 1 to s do
                  begin
                    str(x[i]:1:0, St);
                    if WhereX + length(St) > 77
                    then
                      begin
                        GoToXY(WhereX-2, WhereY);
                        ClrEoL;
                        WriteLn;
                        GoToXY(x0+2, WhereY);
                        Write(' + ')
                      end;
                      Write(x[i]:1:0, 'ý');
                      if i < s
                      then Write(' + ')
                  end;
                WriteLn;
                y0 := WhereY;
                while y0 >= 24 do
                  begin
                    GoToXY(1, 25);
                    WriteLn;
                    y0 := y0 - 1
                  end;
                GoToXY(20, 25);
                Write('Searching . . . press Esc to terminate . . . ');
              end;
            x[s-1] := x[s-1] + 1;
            y[s-1] := sqr(x[s-1]);
          end
        else
          begin
            i0 := s-2;
            while (x[i0] = x[i0+1]) and (i0 >= 1) do i0 := i0 - 1;
            if KeyPressed
            then
              begin
                Ch := ReadKey;
                if Ch = #27    {Esc was pressed}
                then Halt;
              end;
            if i0 > 0
            then
              begin
                x[i0] := x[i0] + 1;
                y[i0] := sqr(x[i0]);
                for i := i0 + 1 to s-1 do
                  begin
                    x[i] := x[i0];
                    y[i] := y[i0]
                  end
              end
          end
      until i0 = 0;
      GoToXY(1, 25);
      ClrEoL;
      GoToXY(1, y0);
      if RD = 0
      then
        begin
          Write(n:1:0, ' can not be expressed as a sum of ', s:1);
          WriteLn(' squares.')
        end
      else
        begin
          WriteLn;
          WriteLn(n:1:0, ' as a sum of ', s:1, ' squares:');
          WriteLn(RD:1:0, ' representations displayed.');
          if RD = 1
          then Write('This is related to ');
          if RD > 1
          then Write('These are related to ');
          Write(R:1:0, ' ordered ');
          if s = 2
          then Write('pairs ');
          if s = 3
          then Write('triples ');
          if s >= 4
          then Write(s:1, '-tuples ');
          WriteLn('of non-negative integers,');
          Write('or to ', RZ:1:0, ' ordered ');
          if s = 2
          then Write('pairs ');
          if s = 3
          then Write('triples ');
          if s >= 4
          then Write(s:1, '-tuples ');
          WriteLn('of integers.')
        end
    end
  else
    begin
      z[0] := 0;
      for i := 1 to round(exp(ln(n)/k))
      do z[i] := exp(k*ln(i));   {construct table of k-th powers}
      for i := 1 to s-1 do x[i] := 0;
      i0 := s-1;
      repeat
        m := 0;
        for i := 1 to s-1 do m := m + z[round(x[i])];
        if m + z[round(x[s-1])] <= n
        then
          begin
            x[s] := exp(ln(n-m)/k);
            if m + z[round(x[s])] = n  {a representation has been found}
            then
              begin
                GoToXY(1, 25);
                ClrEoL;
                GoToXY(1, y0);
                WriteLn;
                if RD = 0
                then
                  begin
                    Write(n:1:0, ' ');
                    x0 := WhereX
                  end;
                RD := RD + 1;
                t := 1;
                j := 1;
                for i := 1 to s do
                  begin
                    if (i > 1) and (x[i] = x[i-1])
                    then j := j + 1
                    else j := 1;
                    t := t*i/j
                  end;
                R := R + t;
                GoToXY(x0, WhereY);
                Write('= ');
                for i := 1 to s do
                  begin
                    str(x[i]:1:0, St);
                    if WhereX + length(St) + lengthK > 75
                    then
                      begin
                        GoToXY(WhereX-2, WhereY);
                        ClrEoL;
                        WriteLn;
                        WriteLn;
                        WriteLn;
                        GoToXY(x0+2, WhereY);
                        Write(' + ')
                      end;
                    Write(x[i]:1:0);
                    GoToXY(WhereX, WhereY-1);
                    Write(k:1);
                    GoToXY(WhereX, WhereY+1);
                    if i < s
                    then Write(' + ')
                  end;
                WriteLn;
                WriteLn;
                y0 := WhereY;
                GoToXY(1, 25);
                while y0 >= 24 do
                  begin
                    WriteLn;
                    y0 := y0 - 1
                  end;
                GoToXY(20, 25);
                Write('Searching . . . press Esc to terminate . . . ');
              end;
            x[s-1] := x[s-1] + 1
          end
        else
          begin
            i0 := s-2;
            while (x[i0] = x[i0+1]) and (i0 >= 1) do i0 := i0 - 1;
            if KeyPressed
            then
              begin
                Ch := ReadKey;
                if Ch = #27    {Esc was pressed}
                then Halt;
              end;
            if i0 > 0
            then
              begin
                x[i0] := x[i0] + 1;
                for i := i0 + 1 to s-1 do x[i] := x[i0]
              end
          end
      until i0 = 0;
      GoToXY(1, 25);
      ClrEoL;
      GoToXY(1, y0-1);
      if RD = 0
      then
        begin
          WriteLn;
          Write(n:1:0, ' can not be expressed as a sum of ', s:1);
          if k=3
          then WriteLn(' cubes.')
          else WriteLn(' ', k:1, '-th powers.')
        end
      else
        begin
          WriteLn;
          Write(n:1:0, ' as a sum of ', s:1);
          if k = 3
          then WriteLn(' cubes:')
          else WriteLn(' ', k:1, '-th powers:');
          WriteLn(RD:1:0, ' representations displayed.');
          if RD = 1
          then Write('This is related to ');
          if RD > 1
          then Write('These are related to ');
          Write(R:1:0, ' ordered ');
          if s = 2
          then Write('pairs of ');
          if s = 3
          then Write('triples of ');
          if s > 3
          then Write(k:1, '-tuples of ');
          WriteLn('non-negative integers.')
        end
  end
end.