Generalizing Fibonacci sequence with SICStus Prolog

Question

I'm trying to find a solution for a query on a generalized Fibonacci sequence (GFS). The query is: are there any GFS that have 885 as their 12th number? The initial 2 numbers may be restricted between 1 and 10.

I already found the solution to find the Nth number in a sequence that starts at (1, 1) in which I explicitly define the initial numbers. Here is what I have for this:

fib(1, 1).
fib(2, 1).

fib(N, X) :-
    N #> 1,
    Nmin1 #= N - 1,
    Nmin2 #= N - 2,
    fib(Nmin1, Xmin1),
    fib(Nmin2, Xmin2),
    X #= Xmin1 + Xmin2.

For the query mentioned I thought the following would do the trick, in which I reuse the fib method without defining the initial numbers explicitly since this now needs to be done dynamically:

fib(N, X) :-
    N #> 1,
    Nmin1 #= N - 1,
    Nmin2 #= N - 2,
    fib(Nmin1, Xmin1),
    fib(Nmin2, Xmin2),
    X #= Xmin1 + Xmin2.

fib2 :-
    X1 in 1..10,
    X2 in 1..10,
    fib(1, X1),
    fib(2, X2),
    fib(12, 885).

... but this does not seem to work.

Is it not possible this way to define the initial numbers, or am I doing something terribly wrong? I'm not asking for the solution, but any advice that could help me solve this would be greatly appreciated.

Sahaptin

Nice problem. Firstly try to get rid of exponential recursion; it will kill your code. Try to use accumulators for that. – Pena

Answer 1

Under SWI-Prolog:

:- use_module(library(clpfd)).

fib(A,B,N,X):-
    N #> 0,
    N0 #= N-1,
    C #= A+B,
    fib(B,C,N0,X).
fib(A,B,0,A).

task(A,B):-
    A in 1..10,
    B in 1..10,
    fib(A,B,11,885).

Saleh

@CookieMonster, prolog tends to represent some searches in a more natural way than some other languages (ex max(X, L):- member(X, L), not((member(Y, L), Y > X)).). What you mean under "labeling"? – Saleh

@CookieMonster, ahh... that's specific of SICSTUS Prolog. I never used that one. Prefer YAP and for samples SWI. In both all free placeholders are printed. – Saleh

@CookieMonster, I use Yap 6.2.2. On query ?- (X=2;X=3),Y is X*2. it gives me X = 2, Y = 4. I can press ; and get alternative. I use interactive mode (i.e. run yap without any additional options). Maybe that's the difference – Saleh

@CookieMonster, yes you are right to get solution you need to call task(A,B), label([A,B]). In both SWI-Prolog and YAP. Without that it just prints constraints. BTW, in Curry you can simply write C=A+B and it will be suspended/postponed (co-routines-like) until A and B bound to something. – Saleh

Answer 2

Define a predicate gfs(X0, X1, N, F) where X0 and X1 are the values for the base cases 0 and 1.

Egoism

Answer 3

I'd say you're doing something terribly wrong... When you call fib(1, X1), the variable X1 is the number that the function fib will return, in this case, it will be 1, because of the base case fib(1, 1)..

Disaccharide

The base case is not defined when I call fib2. fib is defined, but without the explicit initial numbers. This is probably confusing in my question, I'll update it. – Sahaptin

Okay, I'll have another look :) – Disaccharide

Answer 4

Without the base cases, fib/2 has no solution; no matter how you call it in fib2. Note: if you use recursion, you need at least one base case.

Highwrought

Answer 5

Consider fib(N,F1,F2) so you'll be able to replace fib(Nmin1, Xmin1) and fib(Nmin2, Xmin2) with simple fib(Nmin2, Xmin2, Xmin1).

Saleh

Answer 6

Maybe not a solution in the strict sense but I will share it never the less. Probably the only gain is to show, that this does neither need a computer nor a calculator to be solved. If you know the trick it can be done on a bearmat.

If F_n ist the n-th Term of the ordinary Fibo-sequence, starting with F_1=F_2=1, then the n-th Term of the generalized sequence will be G_n = F_{n-2}*a+F_{n-1}*b. Define F_{-1}=1, F_0 = 0

(Indeed, by induction

• G_1 = F_{-1}*a+F_0*b = 1*a+0*b=a
• G_2 = F_0 * a + F_1 * b = 0*a + 1*b = b
• G_{n+1} = F_{n-1}a + F_nb = (F_{n-3} + F_{n-2} )a + (F_{n-2} + F_{n-1})*b = G_n + G_{n-1}

)

Thus G_12 = F_10 * a + F_11 * b = 55a + 89b.

Now you can either search for solutions to the equation 55a + 89b = 885 with your computer

OR

do the math:

Residues mod 11 (explanation):

55a + 89b = 0 + 88b + b = b; 885 = 880 + 5 = 80*11 + 5 = 5

So b = 5 mod 11, but since 1 <= b <= 10, b really is 5. 89 * 5 = 445 and 885-445 = 440. Now, divide by 55 and get a=8.

Seymore

CLP(FD) is probably not good at the algebra and inductive proof you did. But CLP(FD) would be good in finding solutions to equations such as 55*A+89*B #= 885. – Silvers