Calkin-Wilf sequence: Difference between revisions
m
→{{header|EasyLang}}
(→{{header|J}}: simplify) |
|||
| (14 intermediate revisions by 8 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,003 ⟶ 1,039:
=={{header|Fōrmulæ}}==
{{FormulaeEntry|page=https://formulae.org/?script=examples/Calkin-Wilf_correspondence}}
=={{header|Go}}==
{{trans|Wren}}
Line 1,224 ⟶ 1,257:
cw_next_term=: [: % +:@<. + -.
ccf =: compute_continued_fraction=:
if. 0 -: y do.
, 0
else.
result=. i. 0
remainder=. % y
whilst. remainder do.
remainder=. % remainder
integer_part=. <. remainder
remainder=. remainder - integer_part
result=. result , integer_part
end.
end.
)
molcf =: make_odd_length_continued_fraction=: (}: , 1 ,~ <:@{:)^:(0 -: 2 | #)
Line 1,231 ⟶ 1,277:
index_cw_term=: #.@|.@(# 1 0 $~ #)@molcf@ccf
</syntaxhighlight>
Note that <code>ccf</code> could be expressed more concisely:
<syntaxhighlight lang=J>ccf=: _1 {"1 |.@(0 1 #: %@{.)^:(0~:{.)^:a:</syntaxhighlight>
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.ArrayDeque;
import java.util.Deque;
public final class CalkinWilfSequence {
public static void main(String[] aArgs) {
Rational term = Rational.ONE;
System.out.println("First 20 terms of the Calkin-Wilf sequence are:");
for ( int i = 1; i <= 20; i++ ) {
System.out.println(String.format("%2d", i) + ": " + term);
term = nextCalkinWilf(term);
}
System.out.println();
Rational rational = new Rational(83_116, 51_639);
System.out.println(" " + rational + " is the " + termIndex(rational) + "th term of the sequence.");
}
private static Rational nextCalkinWilf(Rational aTerm) {
Rational divisor = Rational.TWO.multiply(aTerm.floor()).add(Rational.ONE).subtract(aTerm);
return Rational.ONE.divide(divisor);
}
private static long termIndex(Rational aRational) {
long result = 0;
long binaryDigit = 1;
long power = 0;
for ( long term : continuedFraction(aRational) ) {
for ( long i = 0; i < term; power++, i++ ) {
result |= ( binaryDigit << power );
}
binaryDigit = ( binaryDigit == 0 ) ? 1 : 0;
}
return result;
}
private static Deque<Long> continuedFraction(Rational aRational) {
long numerator = aRational.numerator();
long denominator = aRational.denominator();
Deque<Long> result = new ArrayDeque<Long>();
while ( numerator != 1 ) {
result.addLast(numerator / denominator);
long copyNumerator = numerator;
numerator = denominator;
denominator = copyNumerator % denominator;
}
if ( ! result.isEmpty() && result.size() % 2 == 0 ) {
final long back = result.removeLast();
result.addLast(back - 1);
result.addLast(1L);
}
return result;
}
}
final class Rational {
public Rational(long aNumerator, long aDenominator) {
if ( aDenominator == 0 ) {
throw new ArithmeticException("Denominator cannot be zero");
}
if ( aNumerator == 0 ) {
aDenominator = 1;
}
if ( aDenominator < 0 ) {
numer = -aNumerator;
denom = -aDenominator;
} else {
numer = aNumerator;
denom = aDenominator;
}
final long gcd = gcd(numer, denom);
numer = numer / gcd;
denom = denom / gcd;
}
public Rational add(Rational aOther) {
return new Rational(numer * aOther.denom + aOther.numer * denom, denom * aOther.denom);
}
public Rational subtract(Rational aOther) {
return new Rational(numer * aOther.denom - aOther.numer * denom, denom * aOther.denom);
}
public Rational multiply(Rational aOther) {
return new Rational(numer * aOther.numer, denom * aOther.denom);
}
public Rational divide(Rational aOther) {
return new Rational(numer * aOther.denom, denom * aOther.numer);
}
public Rational floor() {
return new Rational(numer / denom, 1);
}
public long numerator() {
return numer;
}
public long denominator() {
return denom;
}
@Override
public String toString() {
return numer + "/" + denom;
}
public static final Rational ONE = new Rational(1, 1);
public static final Rational TWO = new Rational(2, 1);
private long gcd(long aOne, long aTwo) {
if ( aTwo == 0 ) {
return aOne;
}
return gcd(aTwo, aOne % aTwo);
}
private long numer;
private long denom;
}
</syntaxhighlight>
{{ out }}
<pre>
First 20 terms of the Calkin-Wilf sequence are:
1: 1/1
2: 1/2
3: 2/1
4: 1/3
5: 3/2
6: 2/3
7: 3/1
8: 1/4
9: 4/3
10: 3/5
11: 5/2
12: 2/5
13: 5/3
14: 3/4
15: 4/1
16: 1/5
17: 5/4
18: 4/7
19: 7/3
20: 3/8
83116/51639 is the 123456789th term of the sequence.
</pre>
=={{header|jq}}==
Line 1,598 ⟶ 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,643 ⟶ 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,213 ⟶ 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,239 ⟶ 2,558:
123456789
</pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">// [dependencies]
Line 2,582 ⟶ 2,902:
{{libheader|Wren-rat}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./fmt" for Fmt, Conv
var calkinWilf = Fn.new { |n|
| |||