Created
March 27, 2025 23:40
-
-
Save dmishin/ccc1ee068a88de31cff8a8dce255eb7a to your computer and use it in GitHub Desktop.
Implementation of "Rosier Q function", supports all rationals with odd denominator
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| from fractions import Fraction | |
| from typing import List, Union, Tuple | |
| def _orbit(x:Fraction)->Tuple[List[int], List[int]]: | |
| """Returns Collatz orbit of x, as a tuple of two lists: initial path and cycle. Assumes the cycle is always reached.""" | |
| if x == 0: return [],[0] | |
| if x.denominator%2 == 0: raise ValueError("2-adically fractional values are not allowed") | |
| visited = {x} | |
| orbit = [x] | |
| while True: | |
| if x.numerator % 2 == 0: | |
| x = x/2 | |
| else: | |
| x = (3*x+1)/2 | |
| if x not in visited: | |
| visited.add(x) | |
| orbit.append(x) | |
| else: | |
| break | |
| idx = orbit.index(x) | |
| return orbit[:idx], orbit[idx:] | |
| #sanity check | |
| assert _orbit(Fraction(5,1)) == ([5, 8, 4], [2, 1]) | |
| def _from_binary(digits_increasing: List[int])->int: | |
| result = 0 | |
| weight = 1 | |
| for digit in digits_increasing: | |
| result += digit*weight | |
| weight *= 2 | |
| return result | |
| def _parity(p:List[int])->List[int]: | |
| return [x%2 for x in p] | |
| def rosier_q(x:Union[Fraction, int])->Fraction: | |
| if isinstance(x,int): x = Fraction(x) | |
| path, cycle = _orbit(x) | |
| return _from_binary(_parity(path)) - Fraction(_from_binary(_parity(cycle)), 2**len(cycle)-1) * 2**len(path) | |
| #sanity check | |
| assert rosier_q(3) == -Fraction(23, 3) | |
| print([rosier_q(i) for i in range(10)]) | |
| print(rosier_q(-Fraction(3, 7))) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment