euler002.pro

% Problem 2: Even Fibonacci numbers
% ---------------------------------
% Each new term in the Fibonacci sequence is generated by adding the previous
%   two terms. By starting with 1 and 2, the first 10 terms will be 1, 2, 3,
%   5, 8, 13, 21, 34, 55, 89, ...
% By considering the terms in the Fibonacci sequence whose values do not
%   exceed four million, find the sum of the even-valued terms.
%
% =============================================================================
%
% Quite similar to problem 1, but this took me way less time since I used the
%   same approach. I did not hardcode the "even-valued" condition, so you can
%   change it to "divisible-by-X" by passing a different number instead of 2.
%
% Implementation notes:
% - Writing a Fibonacci generator that has more than linear complexity should
%   be considered illegal;
% - I am actually glad that the problem text explicitly said to start with 1
%   and 2, sparing me the bother of handling the special case;
% - Without that once/1 Prolog will probably surprise you by saying there are
%   multiple solutions for this problem: genfib/4 will indeed backtrack to a
%   previous solution considering fewer Fibonacci numbers. Even if the
%   problem does not explicitly ask to consider ALL terms in the sequence
%   below the threshold, I assume it means so;
% - Lambdas rock, but in Prolog their syntax is a disgusting curse.

/** <examples>
?- euler002(4000000,2,S).
*/

:- use_module(library(clpfd)).
:- use_module(library(yall)).
:- use_module(library(apply),[include/3]).
:- use_module(library(lists),[sum_list/2]).
:- use_module(library(statistics),[time/1]).

test:-
    writeln(euler002(4000000,2,4613732)),
    time(euler002(4000000,2,4613732)).

euler002(B,M,S):-
    [B,M] ins 1..sup,
    once(genfib(0,1,B,LF)),
    include({M}/[X]>> #=(mod(X,M),0),LF,LN),
    sum_list(LN,S).

genfib(N1,N2,B,[N|LF]):-
    N #= N1+N2,
    N #=< B,
    genfib(N2,N,B,LF).
genfib(_,_,_,[]).