search

4meta5 / reconocer

recognize relations from integer sequences
MIT License
0 stars 0 forks source link

catalan numbers #8

Closed 4meta5 closed 3 years ago

4meta5 commented 3 years ago

Catalan numbers are naively represented as the raw sum relation in the current code. This is much better. Need to add back the binomial_co code.

C_n = (2n-2 choose n-1) / n

by 7.6

4meta5 commented 3 years ago

I took out the relation and replaced it with the aforementioned, improved calculation. The relation code still took me a while, but, it emitted a list that was like [1,2,5,...] instead of [1,1,2,5] so the only way cat_seq worked was if I appended 1 to the output. Anyway, I took it out for now. Might add back later if I choose to represent relations as per #2 later

/*Catalan Relation
* C_n = \sum_{k=0}{n-1} C_k * C_{n-1-k}
*/
cat(_,_,[]).
cat(A,B,[H|T]) :-
    B1 is B+1,
    H is 2 * (2 * B - 1) * A / B1,
    cat(H,B1,T).
4meta5 commented 3 years ago

just added in #7 -- a tail recursive implementation of catalan numbers that doesnt require the binomial coefficient code

cat(N,R) :-
    cat(1,N,1,R).
cat(X,N,R,R) :- X>=N.
cat(X,N,N1,R) :-
    X<N,
    X1 is X+1,
    NX is ((4*X1)-2)/(X1+1),
    N2 is NX*N1,
    cat(X1,N,N2,R).