View source for Talk:Calkin-Wilf sequence

==Off by one error?==
The wikipedia entry starts the series with 1 not zero. The calculation of what term represents a rational also seems off by one.
--[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 22:29, 28 December 2020 (UTC)

Other calculations fail as 0 is never a term if calculating the i'th term from the run length encodings of i for example. Best to correct the task wording and adjust all examples I think. --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 23:37, 28 December 2020 (UTC)

The 123456789'th term of 83116 / 51639 applies to the wikipedia series where the "first" term is 1. 

I get, using the wikipedia calcs:
<pre>for i in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:
    print(i, ith_term(i))
0 1
1 1
2 1/2
3 2
4 1/3
5 3/2
6 2/3
7 3
8 1/4
9 4/3</pre>
zeroth, and first terms are both 1. Best to do as wikepedia does and have istart at 1 for the series I think? --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 00:07, 29 December 2020 (UTC)

: When I try this, I get 'error, ith_term has not been defined'. To be slightly less churlish, I see wp defines "starting from q1 = 1" and there simply is no "zeroth" term. A q0 of 1 is just as wrong, in fact even wronger, and I'd like to see that ith_term - if it ''is'' using the formula I see on wp and in the task description it would a) be wrong and b) not be possible without assuming a q0 of 0. In my entry I cheekily went printf(1,"The first 21 terms of the Calkin-Wilf sequence are:\n 0: 0\n") just to match everyone else. Perhaps the task could be amended to say "you can quietly assume a q0 of 0 to simplify calculations but '''do not show it'''". Lastly, when you say "seems off by one" the wikipedia page clearly links 4/3 and 9 and 3/4 and 14 so... --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 00:37, 29 December 2020 (UTC)

:: I read the wp entry some more as well as others, and I agree, there is no zero'th indexed item. The series ''starts from the 1-indexed item which has a value of 1''. Different methods of arriving at the i'th term, for i being one of all positive integers '''not''' including zero, agree. Extrapolating to a zero'th term do not, and have no meaning in terms of the tree that is traversed to form the series.
:: I could amend the task description... --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 05:24, 29 December 2020 (UTC)

::: Description fixed. Examples flagged. It is a great task. This is just a minor change. --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 05:55, 29 December 2020 (UTC)
::::That all seems fine. Cheers.  [[User:Thebigh|Thebigh]] ([[User talk:Thebigh|talk]]) 08:00, 29 December 2020 (UTC)


==More Calculations: Python==
I enjoyed learning about the sequence; especially the use of run-length encoded binaries and continued fractions from the Wikipedia page. I coded four ways of generating the sequence as well as the '''full''' method of finding the index to any rational in the sequence.<br>
I don't think it's enough to create a separate task from, so I park it here:

<lang python>from fractions import Fraction
from math import floor
from itertools import islice, groupby
from typing import List
from random import randint


def cw_floor() -> Fraction:
    "Calkin-Wilf sequence generator (uses floor function)"
    a = Fraction(1)
    while True:
        yield a
        a = 1 / (2 * floor(a) + 1 - a)

def cw_mod() -> Fraction:
    """\
    Calkin-Wilf sequence generator (uses modulo function)
      See: https://math.stackexchange.com/a/3298088/55677"""
    a, b = 1, 1
    while True:
        yield Fraction(a, b)
        a, b = b, a - 2*(a%b) + b

def cw_direct(i: int) -> Fraction:
    "Calkin-Wilf sequence generation directly from index"
    as_bin = f"{i:b}"
    run_len_encoded = [len(list(g)) 
                       for k,g in groupby(reversed(as_bin))]
    if as_bin[-1] == '0':   # Correction for even i by inserting zero 1's
        run_len_encoded.insert(0, 0)
    return _continued_frac_to_fraction((run_len_encoded))
    
def _continued_frac_to_fraction(cf):
    ans = Fraction(cf[-1])
    for term in reversed(cf[:-1]):
        ans = term + 1 / ans
    return ans

def get_cw_terms_index(f: Fraction) -> int:
    "Given f return the index of where it occurs in the Calkin-Wilf sequence"
    ans, dig, pwr = 0, 1, 0
    for n in _frac_to_odd_continued_frac(f):
        for _ in range(n):
            ans |= dig << pwr
            pwr += 1
        dig ^= 1
    return ans

def _frac_to_odd_continued_frac(f: Fraction) -> List[int]:
    num, den = f.as_integer_ratio()
    ans = []
    while den:
        num, (digit, den) = den, divmod(num, den)
        ans.append(digit)
    if len(ans) %2 == 0:    # Must be odd length
        ans[-1:] = [ans[-1] -1, 1]
    return ans

def fusc() -> List[int]:
    "Fusc sequence generator."
    f = [0]
    yield f
    f.append(1)
    yield f
    n = 2
    while True:
        fn2 = f[n // 2]
        f.append(fn2)
        yield f
        f.append(fn2 + f[n // 2 + 1])
        yield f
        n += 2

def cw_fusc() -> Fraction:
    "Calkin-Wilf sequence generator (uses fusc generator)"
    f = fusc()
    next(f); next(f)
    for series in f:
        yield Fraction(*series[-2:])

   

if __name__ == '__main__':
    n = 10_000
    print(f"Checking {n:_} terms calculated in four ways:")
    using_floor  = list(islice(cw_floor(), n))
    using_mod    = list(islice(cw_mod(), n))
    using_direct = [cw_direct(i) for i in range(1, n+1)]
    using_fusc   = list(islice(cw_fusc(), n))
    if using_floor == using_mod == using_direct == using_fusc:
        print('  OK.')
        print('  FIRST 15 TERMS:', ', '.join(str(x) for x in using_direct[:15]))
        # Indices of successive terms
        print('  CHECKING SUCCESSIVE TERMS ARE FROM SUCCESSIVE INDICES: ')
        first_index = randint(999, 999_999_999)
        #terms = [Fraction(83116, 51639), Fraction(51639, 71801)]
        terms = [cw_direct(first_index), cw_direct(first_index + 1)]
        indices = [get_cw_terms_index(t) for t in terms]
        nth_terms = [cw_direct(index) for index in indices]
        if terms == nth_terms and indices[0] + 1 == indices[1]:
            for t, i in zip(terms, indices):
                print(f"    {t} is the {i:_}'th term.")
        else:
            print('    Whoops! Problems in finding indices of '
                  "successive terms.")
    else:
        print('Whoops! Calculation methods do not match.')</lang>

{{out}}
<pre>Checking 10_000 terms calculated in four ways:
  OK.
  FIRST 15 TERMS: 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
  CHECKING SUCCESSIVE TERMS ARE FROM SUCCESSIVE INDICES: 
    13969/9194 is the 416_907_269'th term.
    9194/13613 is the 416_907_270'th term.</pre>

--[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 19:30, 31 December 2020 (UTC)