Calkin-Wilf sequence: Difference between revisions

Content added Content deleted

Inline

@@ Line 1,244: / Line 1,244: @@
 index_cw_term=: #.@|.@(# 1 0 $~ #)@molcf@ccf
 </syntaxhighlight>
+=={{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
+: 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
+// 51639 is term # 123456789 of the sequence.
+</pre>
 =={{header|Julia}}==
 {{trans|Wren}}
@@ Line 1,287: / Line 1,393: @@
 //51639 is the 123456789-th term of the sequence.
 </pre>
 =={{header|Little Man Computer}}==
 Runs in a home-made simulator, which is mostly compatible with Peter Higginson's online simulator. Only, for better control of the output format, I've added an instruction OTX (extended output). To run the code in PH's simulator, replace OTX and its parameter with OUT and no parameter.