Adventures In Prolog - ProjectEuler20

Continuing with the Euler Quest, a simple and straight-forward solution to Project Euler's problem 20 is presented.

The problem statement reads:

Find the sum of the digits in the number 100!

Where ! denotes the faculty operator.

One (simple) way to solve the problem goes as follows:

Firstly, calculate the value of 100!. Secondly, convert the value into a list of digits. Thirdly, sum each digit. Lastly, output the cumulative result.

A translation of this solution may read like:

euler_20_1(F, Out) :-
  fac(F, Fac),
  string_to_list(Fac, CList),
  euler_20_1_t(CList, 0, Out), !.

euler_20_1_t([], Current, Current).

euler_20_1_t([X|Y], Current, Out) :-
  number_chars(N, [X]),
  NewCurrent is Current + N,
  euler_20_1_t(Y, NewCurrent, Out).

The fac predicate computes the faculty of some positive integer number. string_to_list is a built-in predicate converting a string into its character list representation and number chars converts between ascii character code and number. Building only on these relatively few predicates the code should be straight-forward.

Please note, that this solution is not the most efficient, in fact it may not work for very large numbers. To reduce the complexity of the faculty operation, we might additional knowledge like:

multiplying a number n by a multiply of 10 (n mod 10 = 0), does not change the value of the sum of the digits of the result. For example

3*4*10 = 120 but sum_digit(3*4*10) = sum_digit(3*4*100) = sum_digit(3*4) = 3

Now building on such knowledge, one might cut all numbers that multiplied together yield a multiply of 10 from the faculty operation. This approach will be covered in a future post.

On a different side node, a Prolog implementation of the Porter stemming algorithm can be found here.