Calkin-Wilf sequence: Difference between revisions
m
→{{header|EasyLang}}
(Added Quackery.) |
|||
| (24 intermediate revisions by 15 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 35 ⟶ 37:
* [[Continued fraction/Arithmetic/Construct from rational number]]
<br><br>
=={{header|11l}}==
{{trans|Nim}}
<
n = 1
d = 1
Line 61 ⟶ 62:
L cw() != (83116, 51639)
index++
print("\nThe element 83116/51639 is at position "index‘ in the sequence.’)</
{{out}}
Line 70 ⟶ 71:
The element 83116/51639 is at position 123456789 in the sequence.
</pre>
=={{header|ALGOL 68}}==
Uses code from the [[Arithmetic/Rational]] and [[Continued fraction/Arithmetic/Construct from rational number]] tasks.
<syntaxhighlight lang="algol68">BEGIN
# Show elements 1-20 of the Calkin-Wilf sequence as rational numbers #
# also show the position of a specific element in the seuence #
# Uses code from the Arithmetic/Rational #
# & Continued fraction/Arithmetic/Construct from rational number tasks #
# Code from the Arithmetic/Rational task #
# ============================================================== #
MODE FRAC = STRUCT( INT num #erator#, den #ominator#);
PROC gcd = (INT a, b) INT: # greatest common divisor #
(a = 0 | b |: b = 0 | a |: ABS a > ABS b | gcd(b, a MOD b) | gcd(a, b MOD a));
PROC lcm = (INT a, b)INT: # least common multiple #
a OVER gcd(a, b) * b;
PRIO // = 9; # higher then the ** operator #
OP // = (INT num, den)FRAC: ( # initialise and normalise #
INT common = gcd(num, den);
IF den < 0 THEN
( -num OVER common, -den OVER common)
ELSE
( num OVER common, den OVER common)
FI
);
OP + = (FRAC a, b)FRAC: (
INT common = lcm(den OF a, den OF b);
FRAC result := ( common OVER den OF a * num OF a + common OVER den OF b * num OF b, common );
num OF result//den OF result
);
OP - = (FRAC a, b)FRAC: a + -b,
* = (FRAC a, b)FRAC: (
INT num = num OF a * num OF b,
den = den OF a * den OF b;
INT common = gcd(num, den);
(num OVER common) // (den OVER common)
);
OP - = (FRAC frac)FRAC: (-num OF frac, den OF frac);
# ============================================================== #
# end code from the Arithmetic/Rational task #
# code from the Continued fraction/Arithmetic/Construct from rational number task #
# ================================================================================#
# returns the quotient of numerator over denominator and sets #
# numerator and denominator to the next values for #
# the continued fraction #
PROC r2cf = ( REF INT numerator, REF INT denominator )INT:
IF denominator = 0
THEN 0
ELSE INT quotient := numerator OVER denominator;
INT prev numerator = numerator;
numerator := denominator;
denominator := prev numerator MOD denominator;
quotient
FI # r2cf # ;
# ====================================================================================#
# end code from the Continued fraction/Arithmetic/Construct from rational number task #
# Additional FRACrelated operators #
OP * = ( INT a, FRAC b )FRAC: ( num OF b * a ) // den OF b;
OP / = ( FRAC a, b )FRAC: ( num OF a * den OF b ) // ( num OF b * den OF a );
OP FLOOR = ( FRAC a )INT: num OF a OVER den OF a;
OP + = ( INT a, FRAC b )FRAC: ( a // 1 ) + b;
FRAC one = 1 // 1;
# returns the first n elements of the Calkin-Wilf sequence #
PROC calkin wilf = ( INT n )[]FRAC:
BEGIN
[ 1 : n ]FRAC q;
IF n > 0 THEN
q[ 1 ] := 1 // 1;
FOR i FROM 2 TO UPB q DO
q[ i ] := one / ( ( 2 * FLOOR q[ i - 1 ] ) + one - q[ i - 1 ] )
OD
FI;
q
END # calkin wilf # ;
# returns the position of a FRAC in the Calkin-Wilf sequence by computing its #
# continued fraction representation and converting that to a bit string #
# - the position must fit in a 2-bit number #
PROC position in calkin wilf sequence = ( FRAC f )INT:
IF INT result := 0;
[ 1 : 32 ]INT cf; FOR i FROM LWB cf TO UPB cf DO cf[ i ] := 0 OD;
INT num := num OF f;
INT den := den OF f;
INT cf length := 0;
FOR i FROM LWB cf WHILE den /= 0 DO
cf[ cf length := i ] := r2cf( num, den )
OD;
NOT ODD cf length
THEN # the continued fraction does not have an odd length #
-1
ELSE # the continued fraction has an odd length so we can compute the seuence length #
# build the number by alternating d 1s and 0s where d is the digits of the #
# continued fraction, starting at the least significant #
INT digit := 1;
FOR d pos FROM cf length BY -1 TO 1 DO
FOR i TO cf[ d pos ] DO
result *:= 2 +:= digit
OD;
digit := IF digit = 0 THEN 1 ELSE 0 FI
OD;
result
FI # position in calkin wilf sequence # ;
BEGIN # task #
# get and show the first 20 Calkin-Wilf sequence numbers #
[]FRAC cw = calkin wilf( 20 );
print( ( "The first 20 elements of the Calkin-Wilf sequence are:", newline, " " ) );
FOR n FROM LWB cw TO UPB cw DO
FRAC sn = cw[ n ];
print( ( " ", whole( num OF sn, 0 ), "/", whole( den OF sn, 0 ) ) )
OD;
print( ( newline ) );
# show the position of a specific element in the sequence #
print( ( "Position of 83116/51639 in the sequence: "
, whole( position in calkin wilf sequence( 83116//51639 ), 0 )
)
)
END
END</syntaxhighlight>
{{out}}
<pre>
The first 20 elements of the Calkin-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
Position of 83116/51639 in the sequence: 123456789
</pre>
=={{header|AppleScript}}==
<
on CalkinWilfSequence(n)
script o
Line 169 ⟶ 308:
set AppleScript's text item delimiters to astid
set output to output & (linefeed & "83116/51639 is term number " & positionResult)
return output</
{{output}}
<
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
Ditto using binary run-length encoding:
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 term number 123456789"</
=={{header|Arturo}}==
<
d: new 1
calkinWilf: function [] .export:[n,d] [
Line 206 ⟶ 344:
print ""
print ["The element" ~"|target\0|/|target\1|" "is at position" indx "in the sequence."]</
{{out}}
Line 214 ⟶ 352:
The element 83116/51639 is at position 123456789 in the sequence.</pre>
=={{header|BQN}}==
BQN does not have rational number arithmetic yet, so it is manually implemented.
Line 222 ⟶ 359:
<code>GCD</code> and <code>_while_</code> are idioms from [https://mlochbaum.github.io/bqncrate/ BQNcrate].
<
_while_ ← {𝔽⍟𝔾∘𝔽_𝕣_𝔾∘𝔽⍟𝔾𝕩}
Sim ← { # Simplify a fraction
Line 246 ⟶ 383:
cnt‿fr:
fr ≢ 83116‿51639
} ⟨1,1‿1⟩</
<
⟨ 123456789 ⟨ 83116 51639 ⟩ ⟩</
You can try Part 1 [https://mlochbaum.github.io/BQN/try.html#code=R0NEIOKGkCB7bSDwnZWK4o2fKDA8beKGkPCdlah88J2VqSkg8J2VqH0KX3doaWxlXyDihpAge/CdlL3ijZ/wnZS+4oiY8J2UvV/wnZWjX/CdlL7iiJjwnZS94o2f8J2UvvCdlal9ClNpbSDihpAgewogIHjwnZWKMTog8J2VqOKAvzE7CiAgMPCdlYp5OiAw4oC/8J2VqTsKICDijIrwnZWo4oC/8J2VqSDDtyDwnZWoIEdDRCDwnZWpCn0KQWRkIOKGkCB7CiAgMOKAv2Ig8J2ViiDwnZWpOiDwnZWpOwogIPCdlagg8J2ViiAw4oC/eTog8J2VqDsKICBh4oC/YiDwnZWKIHjigL95OgogICgoYcOXeSkreMOXYikgU2ltIGLDl3kKfQpOZXh0IOKGkCB7buKAv2Q6IOKMvSgyw5fijIrDt8K0buKAv2Qp4oC/MSBBZGQgKGQtbinigL9kfQpDYWwg4oaQIHtOZXh04o2f8J2VqSAx4oC/MX0KCuKAolNob3cgQ2FsIDEr4oaVMjA= here.] Second part can and will hang your browser, so it is best to try locally on [[CBQN]].
=={{header|Bracmat}}==
{{trans|Python}}
<
& 0:?i
& whl
Line 287 ⟶ 423:
)
& out$(get-term-num$83116/51639)
);</
{{out}}
<pre>1/2
Line 309 ⟶ 445:
3/8
123456789</pre>
=={{header|C++}}==
{{libheader|Boost}}
<
#include <vector>
#include <boost/rational.hpp>
Line 364 ⟶ 499:
rational r(83116, 51639);
std::cout << r << " is the " << term_number(r) << "th term of the sequence.\n";
}</
{{out}}
Line 390 ⟶ 525:
20: 3/8
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>
Line 395 ⟶ 562:
===Find first n terms===
{{trans|Pascal}}
<
[For Rosetta Code. EDSAC program, Initial Orders 2.
Prints the first 20 terms of the Calkin-Wilf sequence.
Line 476 ⟶ 643:
P F [enter with acc = 0]
[end]
</syntaxhighlight>
{{out}}
<pre>
Line 502 ⟶ 669:
===Find index of a given term===
{{trans|Pascal}}
<
[For Rosetta Code. EDSAC program, Initial Orders 2.]
[Finds the index of a given rational in the Calkin-Wilf series.]
Line 614 ⟶ 781:
E 19 Z [relative address of entry point]
P F [enter with acc = 0]
</syntaxhighlight>
{{out}}
<pre>
Line 622 ⟶ 789:
=={{header|F_Sharp|F#}}==
===The Function===
<
// Calkin Wilf Sequence. Nigel Galloway: January 9th., 2021
let cW=Seq.unfold(fun(n)->Some(n,seq{for n,g in n do yield (n,n+g); yield (n+g,g)}))(seq[(1,1)])|>Seq.concat
</syntaxhighlight>
===The Tasks===
; first 20
<
cW |> Seq.take 20 |> Seq.iter(fun(n,g)->printf "%d/%d " n g);printfn ""
</syntaxhighlight>
{{out}}
<pre>
Line 636 ⟶ 803:
</pre>
; Indexof 83116/51639
<
printfn "%d" (1+Seq.findIndex(fun n->n=(83116,51639)) cW)
</syntaxhighlight>
{{out}}
<pre>
Line 645 ⟶ 812:
=={{header|Factor}}==
{{works with|Factor|0.99 2020-08-14}}
<
math.continued-fractions math.functions math.parser prettyprint
sequences strings vectors ;
Line 665 ⟶ 832:
20 calkin-wilf ltake [ pprint bl ] leach nl nl
83116/51639 cw-index "83116/51639 is at index %d.\n" printf</
{{out}}
<pre>
Line 673 ⟶ 840:
83116/51639 is at index 123456789.
</pre>
=={{header|Forth}}==
{{works with|gforth|0.7.3}}
<
: frac. swap . ." / " . ;
Line 712 ⟶ 877:
20 cw-seq
cr 83116 51639 2dup frac. cw-index index @ . ;
cw-demo</
{{out}}
Line 736 ⟶ 901:
3 / 8
83116 / 51639 123456789 ok</pre>
=={{header|FreeBASIC}}==
Uses the code from [[Greatest common divisor#FreeBASIC]] as an include.
<
type rational
Line 850 ⟶ 1,012:
q.num = 83116
q.den = 51639
print disp_rational(q)+" is the "+str(frac_to_int(q))+"th term."</
{{out}}
Line 875 ⟶ 1,037:
20 3/8
83116/51639 is the 123456789th term.</pre>
=={{header|Fōrmulæ}}==
{{FormulaeEntry|page=https://formulae.org/?script=examples/Calkin-Wilf_correspondence}}
=={{header|Go}}==
{{trans|Wren}}
Go just has arbitrary precision rational numbers which we use here whilst assuming the numbers needed for this task can be represented exactly by the 64 bit built-in types.
<
import (
Line 977 ⟶ 1,134:
tn := getTermNumber(cf)
fmt.Printf("%s is the %sth term of the sequence.\n", r.RatString(), commatize(tn))
}</
{{out}}
Line 1,005 ⟶ 1,162:
83116/51639 is the 123,456,789th term of the sequence.
</pre>
=={{header|Haskell}}==
<
import Data.Bool (bool)
import Data.List.NonEmpty (NonEmpty, fromList, toList, unfoldr)
Line 1,061 ⟶ 1,217:
"\n%s is at index %d of the Calkin-Wilf sequence.\n"
(show r)
(calkinWilfIdx r)</
{{out}}
<pre>
Line 1,087 ⟶ 1,243:
83116 % 51639 is at index 123456789 of the Calkin-Wilf sequence.
</pre>
=={{header|J}}==
<pre>
Line 1,099 ⟶ 1,254:
</pre>
given definitions
<syntaxhighlight lang="j">
cw_next_term=: [: % +:@<. + -.
Line 1,121 ⟶ 1,276:
NB. base 2 @ reverse @ the cf's representation copies of 1 0 1 0 ...
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}}==
'''Adapted from [[#Wren|Wren]]'''
{{works with|jq}}
'''Also works with gojq, the Go implementation of jq, and with fq'''
See [[Arithmetic/Rational#jq]] for the Rational module included by the `include` directive.
In this module, rationals are represented by JSON objects of the form {n, d}, where .n and .d are
the numerator and denominator respectively. r(n;d) is the constructor function,
and r(n;d) is pretty-printed as `n // d`.
<syntaxhighlight lang=jq>
include "rational"; # see [[Arithmetic/Rational#jq]]
### Generic Utilities
# counting from 0
def enumerate(s): foreach s as $x (-1; .+1; [., $x]);
# input string is converted from "base" to an integer, within limits
# of the underlying arithmetic operations, and without error-checking:
def to_i(base):
explode
| reverse
| map(if . > 96 then . - 87 else . - 48 end) # "a" ~ 97 => 10 ~ 87
| reduce .[] as $c
# state: [power, ans]
([1,0]; (.[0] * base) as $b | [$b, .[1] + (.[0] * $c)])
| .[1];
### The Calkin-Wilf Sequence
# Emit an array of $n terms
def calkinWilf($n):
reduce range(1;$n) as $i ( [r(1;1)];
radd(1; rminus( rmult(2; (.[$i-1]|rfloor)); .[$i-1])) as $t
| .[$i] = rdiv(r(1;1) ; $t)) ;
# input: a Rational
def toContinued:
{ a: .n,
b: .d,
res: [] }
| until( .break;
.res += [.a / .b | floor]
| (.a % .b) as $t
| .a = .b
| .b = $t
| .break = (.a == 1) )
| if .res|length % 2 == 0
then # ensure always odd
.res[-1] += -1
| .res += [1]
else .
end
| .res;
# input: an array representing a continued fraction
def getTermNumber:
reduce .[] as $n ( {b: "", d: "1"};
.b = (.d * $n) + .b
| .d = (if .d == "1" then "0" else "1" end))
| .b | to_i(2) ;
# input: a Rational in the Calkin-Wilf sequence
def getTermNumber:
reduce .[] as $n ( {b: "", d: "1"};
.b = (.d * $n) + .b
| .d = (if .d == "1" then "0" else "1" end))
| .b | to_i(2) ;
def task(r):
"The first 20 terms of the Calkin-Wilf sequence are:",
(enumerate(calkinWilf(20)[]) | "\(1+.[0]): \(.[1]|rpp)" ),
"",
"\(r|rpp) is term # \(r|toContinued|getTermNumber) of the sequence.";
task( r(83116; 51639) )
</syntaxhighlight>
'''Invocation''': jq -nrf calkin-wilf-sequence.jq
{{output}}
<pre>
The 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 term # 123456789 of the sequence.
</pre>
=={{header|Julia}}==
{{trans|Wren}}
<
cw = zeros(Rational, n + 1)
for i in 2:n + 1
Line 1,161 ⟶ 1,584:
const tn = term_number(cf)
println("$r is the $tn-th term of the sequence.")
</
<pre>
The first 20 terms of the Calkin-Wilf sequence are: Rational[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]
Line 1,171 ⟶ 1,594:
===Find first n terms===
{{trans|Pascal}}
<syntaxhighlight lang="little man computer">
// Little Man Computer, for Rosetta Code.
// Displays terms of Calkin-Wilf sequence up to the given index.
Line 1,262 ⟶ 1,685:
b DAT
// end
</syntaxhighlight>
{{out}}
<pre>
Line 1,289 ⟶ 1,712:
{{trans|Pascal}}
The numbers in part 2 of the task are too large for LMC, so the demo program just confirms the example, that 9/4 is the 35th term.
<syntaxhighlight lang="little man computer">
// Little Man Computer, for Rosetta Code.
// Calkin-Wilf sequence: displays index of term entered by user.
Line 1,356 ⟶ 1,779:
index DAT
// end
</syntaxhighlight>
{{out}}
<pre>
9/4<-35
</pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
a[1] = 1;
a[n_?(GreaterThan[1])] := a[n] = 1/(2 Floor[a[n - 1]] + 1 - a[n - 1])
Line 1,381 ⟶ 1,802:
Break[];
]
]</
{{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|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}}==
Line 1,390 ⟶ 1,846:
With these optimizations, the program runs in less than 1.3 s on our laptop.
<
iterator calkinWilf(): Fraction =
Line 1,424 ⟶ 1,880:
inc index
if an == Target: break
echo "\nThe element ", $Target, " is at position ", $index, " in the sequence."</
{{out}}
Line 1,431 ⟶ 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.
<
program CWTerms;
Line 1,555 ⟶ 2,045:
WriteLn( SysUtils.Format( '%8d: %d/%d', [k, Num, Den]));
end.
</syntaxhighlight>
{{out}}
<pre>
Line 1,579 ⟶ 2,069:
20: 3/8
</pre>
<
program CWIndex;
Line 1,630 ⟶ 2,120:
end;
end.
</syntaxhighlight>
{{out}}
<pre>
Index of 83116/51639 is 123456789
</pre>
=={{header|Perl}}==
{{trans|Raku}}
{{libheader|ntheory}}
<
use warnings;
use feature qw(say state);
Line 1,671 ⟶ 2,160:
say 'First twenty terms of the Calkin-Wilf sequence:';
printf "%s ", $calkin_wilf->next() for 1..20;
say "\n\n83116/51639 is at index: " . r2cw(83116,51639);</
{{out}}
<pre>First twenty terms of the Calkin-Wilf sequence:
Line 1,677 ⟶ 2,166:
83116/51639 is at index: 123456789</pre>
=={{header|Phix}}==
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #7060A8;">requires</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1.0.0"</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (new even() builtin)</span>
Line 1,770 ⟶ 2,258:
<span style="color: #004080;">integer</span> <span style="color: #000000;">tn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">get_term_number</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cf</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d/%d is the %,d%s term of the sequence.\n"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">&{</span><span style="color: #000000;">tn</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">ord</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tn</span><span style="color: #0000FF;">)})</span>
<!--</
{{out}}
<pre>
Line 1,797 ⟶ 2,285:
83116/51639 is the 123,456,789th term of the sequence.
</pre>
=={{header|Prolog}}==
<
% John Devou: 26-Nov-2021
Line 1,813 ⟶ 2,300:
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), !.
</syntaxhighlight>
{{out}}
<pre>
Line 1,823 ⟶ 2,310:
X = 123456789.
</pre>
=={{header|Python}}==
<
from math import floor
from itertools import islice, groupby
Line 1,855 ⟶ 2,341:
print('TERMS 1..20: ', ', '.join(str(x) for x in islice(cw(), 20)))
x = Fraction(83116, 51639)
print(f"\n{x} is the {get_term_num(x):_}'th term.")</
{{out}}
Line 1,861 ⟶ 2,347:
83116/51639 is the 123_456_789'th term.</pre>
=={{header|Quackery}}==
<code>cf</code> is defined at [[Continued fraction/Arithmetic/Construct from rational number#Quackery]].
<syntaxhighlight lang="quackery"> [ $ "bigrat.qky" loadfile ] now!
[ ' [ [ 1 1 ] ]
Line 1,875 ⟶ 2,362:
[ 1 & ] is odd ( n --> b )
[ dup size odd not if
Line 1,901 ⟶ 2,381:
[ do vulgar$ echo$ sp ]
cr cr
83116 51639 cw-term echo</
{{out}}
Line 1,908 ⟶ 2,388:
123456789</pre>
=={{header|Raku}}==
In Raku, arrays are indexed from 0. The Calkin-Wilf sequence does not have a term defined at 0.
Line 1,914 ⟶ 2,393:
This implementation includes a bogus undefined value at position 0, having the bogus first term shifts the indices up by one, making the ordinal position and index match. Useful due to how reversibility function works.
<syntaxhighlight lang="raku"
# Rational to Calkin-Wilf index
Line 1,945 ⟶ 2,424:
return $num.numerator if $num.denominator == 1;
$num.nude.join: '/';
}</
{{out}}
<pre>First twenty terms of the Calkin-Wilf sequence: 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
Line 1,954 ⟶ 2,433:
83116/51639 is at index: 123456789</pre>
=={{header|REXX}}==
The meat of this REXX program was provided by Paul Kislanko.
<
/*────────────────────── or finds which sequence number contains a specified fraction). */
numeric digits 2000 /*be able to handle ginormic integers. */
Line 2,007 ⟶ 2,484:
obin= copies(1, f1)copies(0, f0)obin
end /*until*/
return x2d( b2x(obin) ) /*RLE2DEC: Run Length Encoding ──► decimal*/</
{{out|output|text= when using the default inputs:}}
<pre>
Line 2,014 ⟶ 2,491:
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}}
<
y << a = 1.to_r
loop { y << a = 1/(2*a.floor + 1 - a) }
Line 2,038 ⟶ 2,554:
puts cw.take(20).join(", ")
puts term_num (83116/51639r)
</syntaxhighlight>
<pre>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
123456789
Line 2,044 ⟶ 2,560:
=={{header|Rust}}==
<
// num = "0.3"
Line 2,097 ⟶ 2,613:
let r = Rational::new(83116, 51639);
println!("{} is the {}th term of the sequence.", r, term_number(&r));
}</
{{out}}
Line 2,124 ⟶ 2,640:
83116/51639 is the 123456789th term of the sequence.
</pre>
=={{header|Scheme}}==
{{works with|Chez Scheme}}
'''Continued Fraction support'''
<syntaxhighlight lang="scheme">; Create a terminating Continued Fraction generator for the given rational number.
; Returns one term per call; returns #f when no more terms remaining.
(define make-continued-fraction-gen
(lambda (rat)
(let ((num (numerator rat)) (den (denominator rat)))
(lambda ()
(if (= den 0)
#f
(let ((ret (quotient num den))
(rem (modulo num den)))
(set! num den)
(set! den rem)
ret))))))
; Return the continued fraction representation of a rational number as a list of terms.
(define rat->cf-list
(lambda (rat)
(let ((cf (make-continued-fraction-gen rat))
(lst '()))
(let loop ((term (cf)))
(when term
(set! lst (append lst (list term)))
(loop (cf))))
lst)))
; Enforce the length of the given continued fraction list to be odd.
; Changes the list in situ (if needed), and returns its possibly changed value.
(define continued-fraction-list-enforce-odd-length!
(lambda (cf)
(when (even? (length cf))
(let ((cf-last-cons (list-tail cf (1- (length cf)))))
(set-car! cf-last-cons (1- (car cf-last-cons)))
(set-cdr! cf-last-cons (cons 1 '()))))
cf))</syntaxhighlight>
'''Calkin-Wilf sequence'''
<syntaxhighlight lang="scheme">; Create a Calkin-Wilf sequence generator.
(define make-calkin-wilf-gen
(lambda ()
(let ((an 1))
(lambda ()
(let ((ret an))
(set! an (/ 1 (+ (* 2 (floor an)) 1 (- an))))
ret)))))
; Return the position in the Calkin-Wilf sequence of the given rational number.
(define calkin-wilf-position
(lambda (rat)
; Run-length encodes binary value. Assumes first run is 1's. Args: initial value,
; starting place value (a power of 2), and list of run lengths (list must be odd length).
(define encode-list-of-runs
(lambda (value placeval lstruns)
; Encode a single run in a binary value. Args: initial value, bit value (0 or 1),
; starting place value (a power of 2), number of places (bits) to encode.
; Returns multiple values: the encoded value, and the new place value.
(define encode-run
(lambda (value bitval placeval places)
(if (= places 1)
(values (+ value (* bitval placeval)) (* 2 placeval))
(encode-run (+ value (* bitval placeval)) bitval (* 2 placeval) (1- places)))))
; Loop through the list of runs two at a time. If list of length 1, do a final
; '1'-bit encode and return the value. Otherwise, do a '1'-bit then '0'-bit encode,
; and recurse to do the next two runs.
(let-values (((value-1 placeval-1) (encode-run value 1 placeval (car lstruns))))
(if (= 1 (length lstruns))
value-1
(let-values (((value-2 placeval-2) (encode-run value-1 0 placeval-1 (cadr lstruns))))
(encode-list-of-runs value-2 placeval-2 (cddr lstruns)))))))
; Return the run-length binary encoding from the odd-length Calkin-Wilf sequence of the
; given rational number. This is equal to the number's position in the sequence.
(encode-list-of-runs 0 1 (continued-fraction-list-enforce-odd-length! (rat->cf-list rat)))))</syntaxhighlight>
'''The Task'''
<syntaxhighlight lang="scheme">(let ((count 20)
(cw (make-calkin-wilf-gen)))
(printf "~%First ~a terms of the Calkin-Wilf sequence:~%" count)
(do ((num 1 (1+ num)))
((> num count))
(printf "~2d : ~a~%" num (cw))))
(printf "~%Positions in Calkin-Wilf sequence of given numbers:~%")
(let ((num 9/4))
(printf "~a @ ~a~%" num (calkin-wilf-position num)))
(let ((num 83116/51639))
(printf "~a @ ~a~%" num (calkin-wilf-position num)))</syntaxhighlight>
{{out}}
<pre>
First 20 terms of the Calkin-Wilf sequence:
1 : 1
2 : 1/2
3 : 2
4 : 1/3
5 : 3/2
6 : 2/3
7 : 3
8 : 1/4
9 : 4/3
10 : 3/5
11 : 5/2
12 : 2/5
13 : 5/3
14 : 3/4
15 : 4
16 : 1/5
17 : 5/4
18 : 4/7
19 : 7/3
20 : 3/8
Positions in Calkin-Wilf sequence of given numbers:
9/4 @ 35
83116/51639 @ 123456789
</pre>
=={{header|Sidef}}==
<
return 1 if (n == 1)
1/(2*floor(__FUNC__(n-1)) + 1 - __FUNC__(n-1))
Line 2,146 ⟶ 2,775:
with (83116/51639) {|r|
say ("\n#{r.as_rat} is at index: ", r2cw(r))
}</
{{out}}
<pre>
Line 2,153 ⟶ 2,782:
83116/51639 is at index: 123456789
</pre>
=={{header|V (Vlang)}}==
{{trans|Go}}s.
<syntaxhighlight lang="v (vlang)">import math.fractions
import math
import strconv
fn calkin_wilf(n int) []fractions.Fraction {
mut cw := []fractions.Fraction{len: n+1}
cw[0] = fractions.fraction(1, 1)
one := fractions.fraction(1, 1)
two := fractions.fraction(2, 1)
for i in 1..n {
mut t := cw[i-1]
mut f := t.f64()
f = math.floor(f)
t = fractions.approximate(f)
t*=two
t-= cw[i-1]
t+=one
t=t.reciprocal()
cw[i] = t
}
return cw
}
fn to_continued(r fractions.Fraction) []int {
idx := r.str().index('/') or {0}
mut a := r.str()[..idx].i64()
mut b := r.str()[idx+1..].i64()
mut res := []int{}
for {
res << int(a/b)
t := a % b
a, b = b, t
if a == 1 {
break
}
}
le := res.len
if le%2 == 0 { // ensure always odd
res[le-1]--
res << 1
}
return res
}
fn get_term_number(cf []int) ?int {
mut b := ""
mut d := "1"
for n in cf {
b = d.repeat(n)+b
if d == "1" {
d = "0"
} else {
d = "1"
}
}
i := strconv.parse_int(b, 2, 64)?
return int(i)
}
fn commatize(n int) string {
mut s := "$n"
if n < 0 {
s = s[1..]
}
le := s.len
for i := le - 3; i >= 1; i -= 3 {
s = s[0..i] + "," + s[i..]
}
if n >= 0 {
return s
}
return "-" + s
}
fn main() {
cw := calkin_wilf(20)
println("The first 20 terms of the Calkin-Wilf sequnence are:")
for i := 1; i <= 20; i++ {
println("${i:2}: ${cw[i-1]}")
}
println('')
r := fractions.fraction(83116, 51639)
cf := to_continued(r)
tn := get_term_number(cf) or {0}
println("$r is the ${commatize(tn)}th term of the sequence.")
}</syntaxhighlight>
{{out}}
<pre>
The first 20 terms of the Calkin-Wilf sequnence 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 123,456,789th term of the sequence.
</pre>
Line 2,158 ⟶ 2,902:
{{libheader|Wren-rat}}
{{libheader|Wren-fmt}}
<
import "./fmt" for Fmt, Conv
var calkinWilf = Fn.new { |n|
Line 2,207 ⟶ 2,951:
var cf = toContinued.call(r)
var tn = getTermNumber.call(cf)
Fmt.print("$s is the $,r term of the sequence.", r, tn)</
{{out}}
| |||