function [ a, b, c, d, e, count ] = four_fifths ( n )

%*****************************************************************************80
%
%% four_fifths() searches for a solution to the four fifths problem.
%
%  Discussion:
%
%    Euler conjectured that a fifth power cannot be represented as
%    the sum of less than 5 fifth powers.
%
%    The correct equation is:
%
%      27^5 + 84^5 + 110^5 + 133^5 = 144^5 = 61917364224
%
%    This function returns the smallest positive integers ((a,b,c,d),e),
%    with 0 <= e < n, such that
%      a^5 + b^5 + c^5 + d^5 = e^5; 
%    If no such tuple exists, the string 'Failed' is returned.
%
%  Licensing:
%
%    This code is distributed under the MIT license. 
%
%  Modified:
%
%    20 September 2022
%
%  Author:
%
%    Brian Hayes
%
%  Reference:
%
%    Brian Hayes,
%    Four Fifths = A Fifth
%    https://bit-player.org/
%    Posted on 03 December 2014.
%
%  Input:
%
%    integer N, the upper limit for the range of integers to search.
%

%
%  Count starts at 1.
%
  i = 1 : n;
%
%  List the fifth powers from 1^5 to (n-1)^5.
%
  fifths = i.^5;
%
%  Create a way of generating all combinations with replacement of
%  any four integers between 1 and n.  
%
%  Consider every combination from (1,1,1,1) up.
%  If a^5+b^5+c^5+d^5 is an element of the fifths array, we have succeeded.
%
  count = 0;

  while ( true )

    if ( count == 0 )
      v = ones ( 4, 1 );
      w = v - 1;
    else
      w = vector_sumlex_next ( w );
      v = w + 1;
      if ( n < sum ( v ) )
        fprintf ( 1, '\n' );
        fprintf ( 1, 'four_fifths() - Fatal error!\n' );
        fprintf ( 1, '  Failed to find a solution.\n' );  
        fprintf ( 1, '  Exponent sum a+b+c+d = %d\n', n );
        error ( 'four_fifths() - Fatal error!\n' );
      end
    end

    count = count + 1;

    v_sum = sum ( fifths(v) );

    e = find ( fifths == v_sum );

    if ( length ( e ) == 1 )
      a = v(1);
      b = v(2);
      c = v(3);
      d = v(4);
      e = e - 1;
      return
    end

  end

  return
end

