Anonymous user
Talk:Calkin-Wilf sequence: Difference between revisions
→More Calculations: Python
(comment) |
|||
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)
::::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)
| |||