Calkin-Wilf sequence: Difference between revisions
m (→{{header|AppleScript}}: Minor comment edits.) |
m (→{{header|AppleScript}}: Minor label and comment changes.) |
||
Line 28: | Line 28: | ||
=={{header|AppleScript}}== |
=={{header|AppleScript}}== |
||
<lang applescript>-- Return the first n terms of the sequence. Tree |
<lang applescript>-- Return the first n terms of the sequence. Tree generation. Faster for this purpose. |
||
on CalkinWilfSequence(n) |
on CalkinWilfSequence(n) |
||
script o |
script o |
||
Line 34: | Line 34: | ||
end script |
end script |
||
-- Work through the growing sequence list, adding the two children of each term |
-- Work through the growing sequence list, adding the two children of each term to the end and |
||
-- converting each |
-- converting each term to text representing the vulgar fraction. Stop adding children halfway through. |
||
set halfway to n div 2 |
set halfway to n div 2 |
||
repeat with |
repeat with position from 1 to n |
||
set {numerator, denominator} to item |
set {numerator, denominator} to item position of o's sequence |
||
⚫ | |||
⚫ | |||
⚫ | |||
tell numerator + denominator |
tell numerator + denominator |
||
set end of o's sequence to {numerator, it} |
set end of o's sequence to {numerator, it} |
||
if (( |
if ((position < halfway) or (position * 2 < n)) then set end of o's sequence to {it, denominator} |
||
end tell |
end tell |
||
end if |
end if |
||
⚫ | |||
end repeat |
end repeat |
||
Line 51: | Line 51: | ||
end CalkinWilfSequence |
end CalkinWilfSequence |
||
-- Alternatively, return terms |
-- Alternatively, return terms pos1 to pos2. Binary run-length encoding. Doesn't need to work from the beginning of the sequence. |
||
on CalkinWilfSequence2( |
on CalkinWilfSequence2(pos1, pos2) |
||
script o |
script o |
||
property sequence : {} |
property sequence : {} |
||
end script |
end script |
||
repeat with |
repeat with position from pos1 to pos2 |
||
-- Build a continued fraction list from the binary run-length encoding of this position index. |
-- Build a continued fraction list from the binary run-length encoding of this position index. |
||
-- There's no need to put last value into the list as it's used immediately. |
-- There's no need to put the last value into the list as it's used immediately. |
||
set continuedFraction to {} |
set continuedFraction to {} |
||
set bitValue to 1 |
set bitValue to 1 |
||
set |
set runLength to 0 |
||
repeat until ( |
repeat until (position = 0) |
||
if ( |
if (position mod 2 = bitValue) then |
||
set |
set runLength to runLength + 1 |
||
else |
else |
||
set end of continuedFraction to |
set end of continuedFraction to runLength |
||
⚫ | |||
set bitValue to (bitValue + 1) mod 2 |
set bitValue to (bitValue + 1) mod 2 |
||
⚫ | |||
end if |
end if |
||
set |
set position to position div 2 |
||
end repeat |
end repeat |
||
-- Work out the numerator and denominator from the continued fraction and derive text representing the vulgar fraction. |
-- Work out the numerator and denominator from the continued fraction and derive text representing the vulgar fraction. |
||
set numerator to |
set numerator to runLength |
||
set denominator to 1 |
set denominator to 1 |
||
repeat with i from (count continuedFraction) to 1 by -1 |
repeat with i from (count continuedFraction) to 1 by -1 |
||
Line 88: | Line 88: | ||
end CalkinWilfSequence2 |
end CalkinWilfSequence2 |
||
-- Return the position |
-- Return the sequence position of the term with the given numerator and denominator. |
||
on |
on CalkinWilfSequencePosition(numerator, denominator) |
||
-- Build a continued fraction list from the input. |
-- Build a continued fraction list from the input. |
||
set continuedFraction to {} |
set continuedFraction to {} |
||
Line 101: | Line 101: | ||
set end of continuedFraction to 1 |
set end of continuedFraction to 1 |
||
end if |
end if |
||
-- |
-- "Binary run-length decode" the entries to get the position index. |
||
set position to 0 |
set position to 0 |
||
set bitValue to 1 |
set bitValue to 1 |
||
Line 112: | Line 112: | ||
return position |
return position |
||
end CalkinWilfSequencePosition |
|||
end CalkinWilfSequencePos |
|||
-- Task code: |
-- Task code: |
||
Line 118: | Line 118: | ||
set sequenceResult1 to CalkinWilfSequence(20) |
set sequenceResult1 to CalkinWilfSequence(20) |
||
set sequenceResult2 to CalkinWilfSequence2(1, 20) |
set sequenceResult2 to CalkinWilfSequence2(1, 20) |
||
set positionResult to |
set positionResult to CalkinWilfSequencePosition(83116, 51639) |
||
set astid to AppleScript's text item delimiters |
set astid to AppleScript's text item delimiters |
||
set AppleScript's text item delimiters to ", " |
set AppleScript's text item delimiters to ", " |
Revision as of 11:28, 1 January 2021
You are encouraged to solve this task according to the task description, using any language you may know.
The Calkin-Wilf sequence contains every nonnegative rational number exactly once. It can be calculated recursively as follows:
a1 = 1
an+1 = 1/(2⌊an⌋+1-an) for n > 1
- Show on this page terms 1 through 20 of the Calkin-Wilf sequence.
To avoid floating point error, you may want to use a rational number data type.
It is also possible, given a nonnegative rational number, to determine where it appears in the sequence without calculating the sequence. The procedure is to get the continued fraction representation of the rational and use it as the run-length encoding of the binary representation of the term number, beginning from the end of the continued fraction.
It only works if the number of terms in the continued fraction is odd- use either of the two equivalent representations to achieve this:
[a0; a1, a2, ..., an] = [a0; a1, a2 ,..., an-1, 1]
Thus, for example, the fraction 9/4 has odd continued fraction representation 2; 3, 1, giving a binary representation of 100011, which means 9/4 appears as the 35th term of the sequence.
- Find the position of the number 83116/51639 in the Calkin-Wilf sequence.
- See also
- Wikipedia entry: Calkin-Wilf tree
- Continued fraction
- Continued fraction/Arithmetic/Construct from rational number
AppleScript
<lang applescript>-- Return the first n terms of the sequence. Tree generation. Faster for this purpose. on CalkinWilfSequence(n)
script o property sequence : Template:1, 1 -- Initialised with the first term ({numerator, denominator}). end script -- Work through the growing sequence list, adding the two children of each term to the end and -- converting each term to text representing the vulgar fraction. Stop adding children halfway through. set halfway to n div 2 repeat with position from 1 to n set {numerator, denominator} to item position of o's sequence if (position ≤ halfway) then tell numerator + denominator set end of o's sequence to {numerator, it} if ((position < halfway) or (position * 2 < n)) then set end of o's sequence to {it, denominator} end tell end if set item position of o's sequence to (numerator as text) & "/" & denominator end repeat return o's sequence
end CalkinWilfSequence
-- Alternatively, return terms pos1 to pos2. Binary run-length encoding. Doesn't need to work from the beginning of the sequence. on CalkinWilfSequence2(pos1, pos2)
script o property sequence : {} end script repeat with position from pos1 to pos2 -- Build a continued fraction list from the binary run-length encoding of this position index. -- There's no need to put the last value into the list as it's used immediately. set continuedFraction to {} set bitValue to 1 set runLength to 0 repeat until (position = 0) if (position mod 2 = bitValue) then set runLength to runLength + 1 else set end of continuedFraction to runLength set bitValue to (bitValue + 1) mod 2 set runLength to 1 end if set position to position div 2 end repeat -- Work out the numerator and denominator from the continued fraction and derive text representing the vulgar fraction. set numerator to runLength set denominator to 1 repeat with i from (count continuedFraction) to 1 by -1 tell numerator set numerator to numerator * (item i of continuedFraction) + denominator set denominator to it end tell end repeat set end of o's sequence to (numerator as text) & "/" & denominator end repeat return o's sequence
end CalkinWilfSequence2
-- Return the sequence position of the term with the given numerator and denominator. on CalkinWilfSequencePosition(numerator, denominator)
-- Build a continued fraction list from the input. set continuedFraction to {} repeat until (denominator is 0) set end of continuedFraction to numerator div denominator set {numerator, denominator} to {denominator, numerator mod denominator} end repeat -- If it has an even number of entries, convert to the equivalent odd number. if ((count continuedFraction) mod 2 is 0) then set last item of continuedFraction to (last item of continuedFraction) - 1 set end of continuedFraction to 1 end if -- "Binary run-length decode" the entries to get the position index. set position to 0 set bitValue to 1 repeat with i from (count continuedFraction) to 1 by -1 repeat (item i of continuedFraction) times set position to position * 2 + bitValue end repeat set bitValue to (bitValue + 1) mod 2 end repeat return position
end CalkinWilfSequencePosition
-- Task code: local sequenceResult1, sequenceResult2, positionResult, output, astid set sequenceResult1 to CalkinWilfSequence(20) set sequenceResult2 to CalkinWilfSequence2(1, 20) set positionResult to CalkinWilfSequencePosition(83116, 51639) set astid to AppleScript's text item delimiters set AppleScript's text item delimiters to ", " set output to "First twenty terms of sequence using tree generation:" & (linefeed & sequenceResult1) set output to output & (linefeed & "Ditto using binary run-length encoding:") & (linefeed & sequenceResult1) set AppleScript's text item delimiters to astid set output to output & (linefeed & "83116/51639 is term number " & positionResult) return output</lang>
- Output:
<lang applescript>"First twenty terms of sequence using tree generation: 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"</lang>
C++
<lang cpp>#include <iostream>
- include <vector>
- include <boost/rational.hpp>
using rational = boost::rational<unsigned long>;
unsigned long floor(const rational& r) {
return r.numerator()/r.denominator();
}
rational calkin_wilf_next(const rational& term) {
return 1UL/(2UL * floor(term) + 1UL - term);
}
std::vector<unsigned long> continued_fraction(const rational& r) {
unsigned long a = r.numerator(); unsigned long b = r.denominator(); std::vector<unsigned long> result; do { result.push_back(a/b); unsigned long c = a; a = b; b = c % b; } while (a != 1); if (result.size() > 0 && result.size() % 2 == 0) { --result.back(); result.push_back(1); } return result;
}
unsigned long term_number(const rational& r) {
unsigned long result = 0; unsigned long d = 1; unsigned long p = 0; for (unsigned long n : continued_fraction(r)) { for (unsigned long i = 0; i < n; ++i, ++p) result |= (d << p); d = !d; } return result;
}
int main() {
rational term = 1; std::cout << "First 20 terms of the Calkin-Wilf sequence are:\n"; for (int i = 1; i <= 20; ++i) { std::cout << std::setw(2) << i << ": " << term << '\n'; term = calkin_wilf_next(term); } rational r(83116, 51639); std::cout << r << " is the " << term_number(r) << "th term of the sequence.\n";
}</lang>
- Output:
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.
Factor
<lang factor>USING: formatting io kernel lists lists.lazy math math.continued-fractions math.functions math.parser prettyprint sequences strings vectors ;
- next-cw ( x -- y ) [ floor dup + ] [ 1 swap - + recip ] bi ;
- calkin-wilf ( -- list ) 1 [ next-cw ] lfrom-by ;
- >continued-fraction ( x -- seq )
1vector [ dup last integer? ] [ dup next-approx ] until dup length even? [ unclip-last 1 - suffix! 1 suffix! ] when ;
- cw-index ( x -- n )
>continued-fraction <reversed> [ even? CHAR: 1 CHAR: 0 ? <string> ] map-index concat bin> ;
! Task "First 20 terms of the Calkin-Wilf sequence:" print 20 calkin-wilf ltake [ pprint bl ] leach nl nl
83116/51639 cw-index "83116/51639 is at index %d.\n" printf</lang>
- Output:
First 20 terms of the Calkin-Wilf sequence: 1 1/2 2 1/3 1+1/2 2/3 3 1/4 1+1/3 3/5 2+1/2 2/5 1+2/3 3/4 4 1/5 1+1/4 4/7 2+1/3 3/8 83116/51639 is at index 123456789.
FreeBASIC
Uses the code from Greatest common divisor#FreeBASIC as an include.
<lang freebasic>#include "gcd.bas"
type rational
num as integer den as integer
end type
dim shared as rational ONE, TWO ONE.num = 1 : ONE.den = 1 TWO.num = 2 : TWO.den = 1
function simplify( byval a as rational ) as rational
dim as uinteger g = gcd( a.num, a.den ) a.num /= g : a.den /= g if a.den < 0 then a.den = -a.den a.num = -a.num end if return a
end function
operator + ( a as rational, b as rational ) as rational
dim as rational ret ret.num = a.num * b.den + b.num*a.den ret.den = a.den * b.den return simplify(ret)
end operator
operator - ( a as rational, b as rational ) as rational
dim as rational ret ret.num = a.num * b.den - b.num*a.den ret.den = a.den * b.den return simplify(ret)
end operator
operator * ( a as rational, b as rational ) as rational
dim as rational ret ret.num = a.num * b.num ret.den = a.den * b.den return simplify(ret)
end operator
operator / ( a as rational, b as rational ) as rational
dim as rational ret ret.num = a.num * b.den ret.den = a.den * b.num return simplify(ret)
end operator
function floor( a as rational ) as rational
dim as rational ret ret.den = 1 ret.num = a.num \ a.den return ret
end function
function cw_nextterm( q as rational ) as rational
dim as rational ret = (TWO*floor(q)) ret = ret + ONE : ret = ret - q return ONE / ret
end function
function frac_to_int( byval a as rational ) as uinteger
redim as uinteger cfrac(-1) dim as integer lt = -1, ones = 1, ret = 0 do lt += 1 redim preserve as uinteger cfrac(0 to lt) cfrac(lt) = floor(a).num a = a - floor(a) : a = ONE / a loop until a.num = 0 or a.den = 0 if lt mod 2 = 1 and cfrac(lt) = 1 then lt -= 1 cfrac(lt)+=1 redim preserve as uinteger cfrac(0 to lt) end if if lt mod 2 = 1 and cfrac(lt) > 1 then cfrac(lt) -= 1 lt += 1 redim preserve as uinteger cfrac(0 to lt) cfrac(lt) = 1 end if for i as integer = lt to 0 step -1 for j as integer = 1 to cfrac(i) ret *= 2 if ones = 1 then ret += 1 next j ones = 1 - ones next i return ret
end function
function disp_rational( a as rational ) as string
if a.den = 1 or a.num= 0 then return str(a.num) return str(a.num)+"/"+str(a.den)
end function
dim as rational q q.num = 1 q.den = 1 for i as integer = 1 to 20
print i, disp_rational(q) q = cw_nextterm(q)
next i
q.num = 83116 q.den = 51639 print disp_rational(q)+" is the "+str(frac_to_int(q))+"th term."</lang>
- Output:
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 83116/51639 is the 123456789th term.
Go
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. <lang go>package main
import (
"fmt" "math" "math/big" "strconv" "strings"
)
func calkinWilf(n int) []*big.Rat {
cw := make([]*big.Rat, n+1) cw[0] = big.NewRat(1, 1) one := big.NewRat(1, 1) two := big.NewRat(2, 1) for i := 1; i < n; i++ { t := new(big.Rat).Set(cw[i-1]) f, _ := t.Float64() f = math.Floor(f) t.SetFloat64(f) t.Mul(t, two) t.Sub(t, cw[i-1]) t.Add(t, one) t.Inv(t) cw[i] = new(big.Rat).Set(t) } return cw
}
func toContinued(r *big.Rat) []int {
a := r.Num().Int64() b := r.Denom().Int64() var res []int for { res = append(res, int(a/b)) t := a % b a, b = b, t if a == 1 { break } } le := len(res) if le%2 == 0 { // ensure always odd res[le-1]-- res = append(res, 1) } return res
}
func getTermNumber(cf []int) int {
b := "" d := "1" for _, n := range cf { b = strings.Repeat(d, n) + b if d == "1" { d = "0" } else { d = "1" } } i, _ := strconv.ParseInt(b, 2, 64) return int(i)
}
func commatize(n int) string {
s := fmt.Sprintf("%d", n) if n < 0 { s = s[1:] } le := len(s) for i := le - 3; i >= 1; i -= 3 { s = s[0:i] + "," + s[i:] } if n >= 0 { return s } return "-" + s
}
func main() {
cw := calkinWilf(20) fmt.Println("The first 20 terms of the Calkin-Wilf sequnence are:") for i := 1; i <= 20; i++ { fmt.Printf("%2d: %s\n", i, cw[i-1].RatString()) } fmt.Println() r := big.NewRat(83116, 51639) cf := toContinued(r) tn := getTermNumber(cf) fmt.Printf("%s is the %sth term of the sequence.\n", r.RatString(), commatize(tn))
}</lang>
- Output:
The first 20 terms of the Calkin-Wilf sequnence are: 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 83116/51639 is the 123,456,789th term of the sequence.
Haskell
<lang haskell>import Control.Monad (forM_) import Data.Bool (bool) import Data.List.NonEmpty (NonEmpty, fromList, toList, unfoldr) import Text.Printf (printf)
-- The infinite Calkin-Wilf sequence, a(n), starting with a(1) = 1. calkinWilfs :: [Rational] calkinWilfs = iterate (\r -> recip (2 * fromIntegral (floor r) - r + 1)) 1
-- The index into the Calkin-Wilf sequence of a given rational number, starting -- with 1 at index 1. calkinWilfIdx :: Rational -> Integer calkinWilfIdx = rld . cfo
-- A continued fraction representation of a given rational number, guaranteed -- to have an odd length. cfo :: Rational -> NonEmpty Int cfo = oddLen . cf
-- The canonical (i.e. shortest) continued fraction representation of a given -- rational number. cf :: Rational -> NonEmpty Int cf = unfoldr step
where step r = case properFraction r of (n, 1) -> (1+n, Nothing) (n, 0) -> ( n, Nothing) (n, f) -> ( n, Just (recip f))
-- Ensure a continued fraction has an odd length. oddLen :: NonEmpty Int -> NonEmpty Int oddLen = fromList . go . toList
where go (x:y:[]) = [x, y-1, 1] go (x:y:zs) = x : y : go zs go xs = xs
-- Run-length decode a continued fraction. rld :: NonEmpty Int -> Integer rld = snd . foldr step (True, 0)
where step i (b, n) = let p = 2^i in (not b, n*p + bool 0 (p-1) b)
main :: IO () main = do
forM_ (take 20 $ zip [1::Int ..] calkinWilfs) $ \(i, r) -> printf "%2d %s\n" i (show r) let r = 83116 / 51639 printf "\n%s is at index %d of the Calkin-Wilf sequence.\n" (show r) (calkinWilfIdx r)</lang>
- Output:
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 at index 123456789 of the Calkin-Wilf sequence.
Julia
<lang julia>function calkin_wilf(n)
cw = zeros(Rational, n + 1) for i in 2:n + 1 t = Int(floor(cw[i - 1])) * 2 - cw[i - 1] + 1 cw[i] = 1 // t end return cw[2:end]
end
function continued(r::Rational)
a, b = r.num, r.den res = [] while true push!(res, Int(floor(a / b))) a, b = b, a % b a == 1 && break end return res
end
function term_number(cf)
b, d = "", "1" for n in cf b = d^n * b d = (d == "1") ? "0" : "1" end return parse(Int, b, base=2)
end
const cw = calkin_wilf(20) println("The first 20 terms of the Calkin-Wilf sequence are: $cw")
const r = 83116 // 51639 const cf = continued(r) const tn = term_number(cf) println("$r is the $tn-th term of the sequence.")
</lang>
- Output:
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] 83116//51639 is the 123456789-th term of the sequence.
Phix
<lang Phix>function calkin_wilf(integer len)
sequence cw = repeat(0,len) integer n=0, d=1 for i=1 to len do {n,d} = {d,(floor(n/d)*2+1)*d-n} cw[i] = {n,d} end for return cw
end function
function to_continued_fraction(sequence r)
integer {a,b} = r sequence res = {} while true do res &= floor(a/b) {a, b} = {b, remainder(a,b)} if a=1 then exit end if end while return res
end function
function get_term_number(sequence cf)
sequence b = {} integer d = 1 for i=1 to length(cf) do b &= repeat(d,cf[i]) d = 1-d end for return bits_to_int(b)
end function
-- additional verification methods (2 of) function i_to_cf(integer i) -- sequence b = trim_tail(int_to_bits(i,32),0)&2,
sequence b = int_to_bits(i)&2, cf = iff(b[1]=0?{0}:{}) while length(b)>1 do for j=2 to length(b) do if b[j]!=b[1] then cf &= j-1 b = b[j..$] exit end if end for end while -- replace even length with odd length equivalent: if remainder(length(cf),2)=0 then cf[$] -= 1 cf &= 1 end if return cf
end function
function cf2r(sequence cf)
integer n=0, d=1 for i=length(cf) to 2 by -1 do {n,d} = {d,n+d*cf[i]} end for return {n+cf[1]*d,d}
end function
function prettyr(sequence r)
integer {n,d} = r return iff(d=1?sprintf("%d",n):sprintf("%d/%d",{n,d}))
end function
sequence cw = calkin_wilf(20) printf(1,"The first 20 terms of the Calkin-Wilf sequence are:\n") for i=1 to 20 do
string s = prettyr(cw[i]), r = prettyr(cf2r(i_to_cf(i))) integer t = get_term_number(to_continued_fraction(cw[i])) printf(1,"%2d: %-4s [==> %2d: %-3s]\n", {i, s, t, r})
end for printf(1,"\n") sequence r = {83116,51639} sequence cf = to_continued_fraction(r) integer tn = get_term_number(cf) printf(1,"%d/%d is the %,d%s term of the sequence.\n", r&{tn,ord(tn)})</lang>
- Output:
The first 20 terms of the Calkin-Wilf sequence are: 1: 1 [==> 1: 1 ] 2: 1/2 [==> 2: 1/2] 3: 2 [==> 3: 2 ] 4: 1/3 [==> 4: 1/3] 5: 3/2 [==> 5: 3/2] 6: 2/3 [==> 6: 2/3] 7: 3 [==> 7: 3 ] 8: 1/4 [==> 8: 1/4] 9: 4/3 [==> 9: 4/3] 10: 3/5 [==> 10: 3/5] 11: 5/2 [==> 11: 5/2] 12: 2/5 [==> 12: 2/5] 13: 5/3 [==> 13: 5/3] 14: 3/4 [==> 14: 3/4] 15: 4 [==> 15: 4 ] 16: 1/5 [==> 16: 1/5] 17: 5/4 [==> 17: 5/4] 18: 4/7 [==> 18: 4/7] 19: 7/3 [==> 19: 7/3] 20: 3/8 [==> 20: 3/8] 83116/51639 is the 123,456,789th term of the sequence.
Python
<lang python>from fractions import Fraction from math import floor from itertools import islice, groupby
def cw():
a = Fraction(1) while True: yield a a = 1 / (2 * floor(a) + 1 - a)
def r2cf(rational):
num, den = rational.numerator, rational.denominator while den: num, (digit, den) = den, divmod(num, den) yield digit
def get_term_num(rational):
ans, dig, pwr = 0, 1, 0 for n in r2cf(rational): for _ in range(n): ans |= dig << pwr pwr += 1 dig ^= 1 return ans
if __name__ == '__main__':
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.")</lang>
- Output:
TERMS 1..20: 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 83116/51639 is the 123_456_789'th term.
Raku
In Raku, arrays are indexed from 0. The Calkin-Wilf sequence does not have a term defined at 0.
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.
<lang perl6>my @calkin-wilf = Any, 1, {1 / (.Int × 2 + 1 - $_)} … *;
- Rational to Calkin-Wilf index
sub r2cw (Rat $rat) { :2( join , flat (flat (1,0) xx *) Zxx reverse r2cf $rat ) }
- The task
say "First twenty terms of the Calkin-Wilf sequence: ",
@calkin-wilf[1..20]».&prat.join: ', ';
say "\n99991st through 100000th: ",
(my @tests = @calkin-wilf[99_991 .. 100_000])».&prat.join: ', ';
say "\nCheck reversibility: ", @tests».Rat».&r2cw.join: ', ';
say "\n83116/51639 is at index: ", r2cw 83116/51639;
- Helper subs
sub r2cf (Rat $rat is copy) { # Rational to continued fraction
gather loop {
$rat -= take $rat.floor; last if !$rat; $rat = 1 / $rat;
}
}
sub prat ($num) { # pretty Rat
return $num unless $num ~~ Rat|FatRat; return $num.numerator if $num.denominator == 1; $num.nude.join: '/';
}</lang>
- Output:
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 99991st through 100000th: 1085/303, 303/1036, 1036/733, 733/1163, 1163/430, 430/987, 987/557, 557/684, 684/127, 127/713 Check reversibility: 99991, 99992, 99993, 99994, 99995, 99996, 99997, 99998, 99999, 100000 83116/51639 is at index: 123456789
Rust
<lang rust>// [dependencies] // num = "0.3"
use num::rational::Rational;
fn calkin_wilf_next(term: &Rational) -> Rational {
Rational::from_integer(1) / (Rational::from_integer(2) * term.floor() + 1 - term)
}
fn continued_fraction(r: &Rational) -> Vec<isize> {
let mut a = *r.numer(); let mut b = *r.denom(); let mut result = Vec::new(); loop { let (q, r) = num::integer::div_rem(a, b); result.push(q); a = b; b = r; if a == 1 { break; } } let len = result.len(); if len != 0 && len % 2 == 0 { result[len - 1] -= 1; result.push(1); } result
}
fn term_number(r: &Rational) -> usize {
let mut result: usize = 0; let mut d: usize = 1; let mut p: usize = 0; for n in continued_fraction(r) { for _ in 0..n { result |= d << p; p += 1; } d ^= 1; } result
}
fn main() {
println!("First 20 terms of the Calkin-Wilf sequence are:"); let mut term = Rational::from_integer(1); for i in 1..=20 { println!("{:2}: {}", i, term); term = calkin_wilf_next(&term); } let r = Rational::new(83116, 51639); println!("{} is the {}th term of the sequence.", r, term_number(&r));
}</lang>
- Output:
First 20 terms of the Calkin-Wilf sequence are: 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 83116/51639 is the 123456789th term of the sequence.
Wren
<lang ecmascript>import "/rat" for Rat import "/fmt" for Fmt, Conv
var calkinWilf = Fn.new { |n|
var cw = List.filled(n, null) cw[0] = Rat.one for (i in 1...n) { var t = cw[i-1].floor * 2 - cw[i-1] + 1 cw[i] = Rat.one / t } return cw
}
var toContinued = Fn.new { |r|
var a = r.num var b = r.den var res = [] while (true) { res.add((a/b).floor) var t = a % b a = b b = t if (a == 1) break } if (res.count%2 == 0) { // ensure always odd res[-1] = res[-1] - 1 res.add(1) } return res
}
var getTermNumber = Fn.new { |cf|
var b = "" var d = "1" for (n in cf) { b = (d * n) + b d = (d == "1") ? "0" : "1" } return Conv.atoi(b, 2)
}
var cw = calkinWilf.call(20) System.print("The first 20 terms of the Calkin-Wilf sequence are:") Rat.showAsInt = true for (i in 1..20) Fmt.print("$2d: $s", i, cw[i-1]) System.print() var r = Rat.new(83116, 51639) var cf = toContinued.call(r) var tn = getTermNumber.call(cf) Fmt.print("$s is the $,r term of the sequence.", r, tn)</lang>
- Output:
The first 20 terms of the Calkin-Wilf sequence are: 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 83116/51639 is the 123,456,789th term of the sequence.