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.

Nice problem. Firstly try to get rid of exponential recursion; it will kill your code. Try to use accumulators for that. — liori, May 09 '10 at 19:08

ony · Answer 1 · 2010-05-11T20:12:59.893

5

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).

edited May 11 '10 at 20:12

answered May 11 '10 at 19:58

ony

12,457
1
33
41

@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"? – ony Jun 20 '14 at 07:57
@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. – ony Jun 20 '14 at 10:46
@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 – ony Jun 30 '14 at 18:49
@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. – ony Jul 02 '14 at 07:01

starblue · Answer 2 · 2010-05-12T06:00:02.287

1

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

edited May 12 '10 at 06:00

answered May 10 '10 at 19:43

starblue

55,348
14
97
151

score 0 · Answer 3 · answered May 09 '10 at 18:47

0

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)..

answered May 09 '10 at 18:47

Jivings

22,834
6
60
101

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. – Christophe Herreman May 09 '10 at 18:51
Okay, I'll have another look :) – Jivings May 09 '10 at 18:56

score 0 · Answer 4 · answered May 10 '10 at 08:34

0

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.

answered May 10 '10 at 08:34

Michael

121
1

score 0 · Answer 5 · answered May 11 '10 at 19:01

0

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).

answered May 11 '10 at 19:01

ony

12,457
1
33
41

score 0 · Answer 6 · answered May 14 '10 at 19:38

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.

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. — , Jun 19 '14 at 20:05

Generalizing Fibonacci sequence with SICStus Prolog

6 Answers6

Linked