Talk:Calkin-Wilf sequence: Difference between revisions
(comment) |
|||
Line 29: | Line 29: | ||
::: 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) |
::: 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) |
::::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) |
Latest revision as of 19:32, 31 December 2020
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. --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. --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:
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
zeroth, and first terms are both 1. Best to do as wikepedia does and have istart at 1 for the series I think? --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... --Pete Lomax (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... --Paddy3118 (talk) 05:24, 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.
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>
- Output:
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.