Calkin-Wilf sequence: Difference between revisions
m
→{{header|EasyLang}}
m (Correcting minor formatting error.) |
|||
| (9 intermediate revisions by 5 users not shown) | |||
Line 29:
* Find the position of the number <big>'''<sup>83116</sup>'''<big>'''/'''</big>'''<sub>51639</sub>'''</big> in the Calkin-Wilf sequence.
;Related tasks:
:* [[Fusc sequence]].
;See also:
Line 524 ⟶ 526:
83116/51639 is the 123456789th term of the sequence.
</pre>
=={{header|EasyLang}}==
{{trans|Nim}}
<syntaxhighlight>
subr first
n = 1 ; d = 1
.
proc next . .
n = 2 * (n div d) * d + d - n
swap n d
.
print "The first 20 terms of the Calkwin-Wilf sequence are:"
first
for i to 20
write n & "/" & d & " "
next
.
print ""
#
first
i = 1
while n <> 83116 or d <> 51639
next
i += 1
.
print "83116/51639 is at position " & i
</syntaxhighlight>
{{out}}
<pre>
The first 20 terms of the Calkwin-Wilf sequence are:
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
83116/51639 is at position 123456789
</pre>
=={{header|EDSAC order code}}==
===Find first n terms===
Line 751 ⟶ 786:
83116/51639 IS AT 123456789
</pre>
=={{header|F_Sharp|F#}}==
===The Function===
Line 1,770 ⟶ 1,806:
<pre>{1, 1/2, 2, 1/3, 3/2, 2/3, 3, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4, 1/5, 5/4, 4/7, 7/3, 3/8}
123456789</pre>
=={{header|Maxima}}==
<syntaxhighlight lang="maxima">
/* The function fusc is related to Calkin-Wilf sequence */
fusc(n):=block(
[k:n,a:1,b:0],
while k>0 do (if evenp(k) then (k:k/2,a:a+b) else (k:(k-1)/2,b:a+b)),
b)$
/* Calkin-Wilf function using fusc */
calkin_wilf(n):=fusc(n)/fusc(n+1)$
/* Function that given a nonnegative rational returns its position in the Calkin-Wilf sequence */
cf_bin(fracti):=block(
cf_list:cf(fracti),
cf_len:length(cf_list),
if oddp(cf_len) then cf_list:reverse(cf_list) else cf_list:reverse(append(at(cf_list,[cf_list[cf_len]=cf_list[cf_len]-1]),[1])),
makelist(lambda([x],if oddp(x) then makelist(1,j,1,cf_list[x]) else makelist(0,j,1,cf_list[x]))(i),i,1,length(cf_list)), /* decoding part begins here */
apply(append,%%),
apply("+",makelist(2^i,i,0,length(%%)-1)*reverse(%%)))$
/* Test cases */
/* 20 first terms of the sequence */
makelist(calkin_wilf(i),i,1,20);
/* Position of 83116/51639 in Calkin-Wilf sequence */
83116/51639$
cf_bin(%);
</syntaxhighlight>
{{out}}
<pre>
[1,1/2,2,1/3,3/2,2/3,3,1/4,4/3,3/5,5/2,2/5,5/3,3/4,4,1/5,5/4,4/7,7/3,3/8]
123456789
</pre>
=={{header|Nim}}==
We ignored the standard module “rationals” which is slow and have rather defined a fraction as a tuple of two 32 bits unsigned integers (slightly faster than 64 bits signed integers and sufficient for this task). Moreover, we didn’t do operations on fractions and computed directly the numerator and denominator values at each step. The fractions built this way are irreducible (which avoids to compute a GCD which is a slow operation).
Line 1,815 ⟶ 1,887:
The element 83116/51639 is at position 123456789 in the sequence.</pre>
=={{header|PARI/GP}}==
{{trans|Mathematica_/_Wolfram_Language}}
<syntaxhighlight lang="PARI/GP">
\\ This function assumes the existence of a global variable 'an' for 'a[n]'
a(n) = if(n==1, 1, 1 / (2 * floor(an[n-1]) + 1 - an[n-1]));
\\ We will use a vector to hold the values and compute them iteratively to avoid stack overflow
an = vector(20);
an[1] = 1;
for(i=2, 20, an[i] = a(i));
\\ Now we print the vector
print(an);
\\ Initialize variables for the while loop
a = 1;
n = 1;
\\ Loop until the condition is met
while(a != 83116/51639,{
a = 1/(2 * floor(a) + 1 - a);
if(n>=123456789,print(n));
n++;
});
\\ Output the number of iterations needed to reach 83116/51639
print(n);
</syntaxhighlight>
{{out}}
<pre>
[1, 1/2, 2, 1/3, 3/2, 2/3, 3, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4, 1/5, 5/4, 4/7, 7/3, 3/8]
123456789
</pre>
=={{header|Pascal}}==
These programs were written in Free Pascal, using the Lazarus IDE and the Free Pascal compiler version 3.2.0. They are based on the Wikipedia article "Calkin-Wilf tree", rather than the algorithms in the task description.
Line 2,385 ⟶ 2,492:
for 83116/51639, the element number for the Calkin─Wilf sequence is: 123,456,789th
</pre>
=={{header|RPL}}==
{{works with|HP|49g}}
≪ { } SWAP
'''WHILE''' DUP '''REPEAT '''
ROT OVER IDIV2
4 ROLL ROT + SWAP
'''END''' ROT DROP2
≫ '<span style="color:blue">CONTFRAC</span>' STO
≪ {1}
'''WHILE''' DUP2 SIZE > '''REPEAT'''
DUP DUP SIZE GET
DUP IP R→I 2 * 1 + SWAP - INV EVAL +
'''END''' NIP
≫ ≫ '<span style="color:blue">CWILF</span>' STO
≪
<span style="color:blue">CONTFRAC</span> DUP SIZE
'''IF''' DUP MOD '''THEN''' DROP '''ELSE'''
DUP2 GET 1 - PUT 1 + '''END'''
1 → frac pow2
≪ 0
1 frac SIZE '''FOR''' j
frac j GET
'''WHILE''' DUP '''REPEAT'''
'''IF''' j 2 MOD '''THEN''' SWAP pow2 + SWAP '''END'''
2 'pow2' STO*
1 -
'''END''' DROP
'''NEXT'''
≫ ≫ '<span style="color:blue">CWPOS</span>' STO
20 <span style="color:blue">CWILF</span>
83116 51639 <span style="color:blue">CWPOS</span>
{{out}}
<pre>
2: {1 '1/2' 2 '1/3' '3/2' '2/3' 3 '1/4' '4/3' '3/5' '5/2' '2/5' '5/3' '3/4' 4 '1/5' '5/4' '4/7' '7/3' '3/8'}
1: 123456789
</pre>
=={{header|Ruby}}==
{{trans|Python}}
Line 2,411 ⟶ 2,558:
123456789
</pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">// [dependencies]
Line 2,754 ⟶ 2,902:
{{libheader|Wren-rat}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./fmt" for Fmt, Conv
var calkinWilf = Fn.new { |n|
| |||