Tuesday, August 18, 2009

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.

Adventures In Prolog - Euler7 and the Nth Prime

Building on our previous prime-related posts, today's post will cover a solution to Project Euler's 7th Problem, i.e. finding the 10001st prime. Now, the solution to this problem can be easily expressed in thought and then converted to some programming language …

Starting with the lowest and first prime – 2 - , we check each subsequent number j > i, for primality. Whenever we find a j such that j is prime, we increment a prime counter c by one and continue testing numbers k > j. This is done until c reaches the number 10001.

The Prolog code below is an expression of this idea, added with some prime numbers found during the process of finding the 10001st prime. This means, given the border of some prime interval, i.e. 100th prime = i and 200th prime = j, we may start looking for the 150th prime within the number interval [i,j], instead of starting at 2 and checking each number until the prime counter reaches 150. Also, we might have defined the euler_7 predicate to be dynamic, i.e. updatable, such that whenever we find some kth prime, it will be stored in the fact database.


%EULER7 the 10001 prime
euler_7(4409, 600) :- !.

euler_7(Out, Xth) :-
Xth < 600, !,
euler_7_t(2, 1, Xth, Out).

euler_7(Out, Xth) :-
Xth < 700, !,
euler_7_t(4409, 600, Xth, Out).

euler_7(Out, Xth) :-
Xth < 1000, !,
euler_7_t(5279, 700, Xth, Out).

euler_7(Out, Xth) :-
Xth < 1100, !,
euler_7_t(7917, 1000, Xth, Out).

euler_7(Out, Xth) :-
Xth < 1200, !,
euler_7_t(8831, 1100, Xth, Out).

euler_7(Out, Xth) :-
Xth < 1500, !,
euler_7_t(9733, 1200, Xth, Out).

euler_7(Out, Xth) :-
Xth < 2000, !,
euler_7_t(12553, 1500, Xth, Out).

euler_7(Out, Xth) :-
Xth < 3000, !,
euler_7_t(17389, 2000, Xth, Out).

euler_7(Out, Xth) :-
Xth < 4000, !,
euler_7_t(27449, 3000, Xth, Out).

euler_7(Out, Xth) :-
Xth < 5000, !,
euler_7_t(37813, 4000, Xth, Out).

euler_7(Out, Xth) :-
Xth < 7000,
euler_7_t(48611, 5000, Xth, Out), !.

euler_7(Out, Xth) :-
Xth < 10001,
euler_7_t(70657, 7000, Xth, Out), !.

euler_7(Out, Xth) :-
euler_7_t(104743, 10001, Xth, Out), !.


euler_7_t(P, Xth, Xth, P) :-
is_prime(P), !.

euler_7_t(NP, Xth, Xth, P) :-
NewPrime is NP + 1,
euler_7_t(NewPrime, Xth, Xth, P), !.

euler_7_t(X, Xth, Gth, Prime) :-
is_prime(X),
Y is X + 1,
Yth is Xth + 1,
euler_7_t(Y, Yth, Gth, Prime), !.

euler_7_t(X, Xth, Gth, Prime) :-
Y is X + 1,
euler_7_t(Y, Xth, Gth, Prime).
%EULER7 the 10001 prime