Anonymous user
Calkin-Wilf sequence: Difference between revisions
no edit summary
No edit summary |
No edit summary |
||
Line 1,535:
83116/51639 is the 123,456,789th term of the sequence.
</pre>
=={{header|Prolog}}==
<lang prolog>
% John Devou: 26-Nov-2021
% g(N,X):- consecutively generate in X the first N elements of the Calkin-Wilf sequence
g(N,[A/B|_]-_,A/B):- N > 0.
g(N,[A/B|Ls]-[A/C,C/B|Ys],X):- N > 1, M is N-1, C is A+B, g(M,Ls-Ys,X).
g(N,X):- g(N,[1/1|Ls]-Ls,X).
% t(A/B,X):- generate in X the index of A/B in the Calkin-Wilf sequence
t(A/1,S,C,X):- X is C*(2**(A-1+S)-S).
t(A/B,S,C,X):- B > 1, divmod(A,B,M,N), T is 1-S, D is C*2**M, t(B/N,T,D,Y), X is Y + S*C*(2**M-1).
t(A/B,X):- t(A/B,1,1,X), !.
</lang>
{{out}}
<pre>
?- findall(X, g(20,X), L), write(L).
[1/1,1/2,2/1,1/3,3/2,2/3,3/1,1/4,4/3,3/5,5/2,2/5,5/3,3/4,4/1,1/5,5/4,4/7,7/3,3/8]
L = [1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, 1/4, ... / ...|...].
?- t(83116/51639,X).
X = 123456789.
</pre>
| |||