判别非负有理数在正整数基上展开的周期重复位数

Question

我实现了一个算法，对于给定的非负有理数 r 和一个正整数 b，计算 r 在基数中展开的所有数字b。算法本身实际上输出一个函数f(i: int)满足方程n = ... + f(-2)*b**-2 + f(-1)*b**-1 + f(0)*b**0 + f(1)*b**1 + f(2)*b**2 + ...，它通过另外两个辅助函数分别计算r的整数和小数部分的位数。

下面是我在 Python (3.10.2) 中的代码。 Python 代码看起来很奇怪，因为我实际上是在 MIT/GNU Scheme (15.3) 中实现算法并在 Python 上“绘制”它。我展示的是 Python 实现而不是 Scheme 实现，主要是因为我相信在 Python.

中更容易表述这个问题（并且实际上已经回答了）

# `base`: convert a non-negative fraction to any positive integer base

from fractions import Fraction

# a natural number is a integer greater than or equal to 0
def is_natural(n):
    return isinstance(n, int) and n >= 0

# a fractional is a positive rational number strictly between 0 and 1
def is_fractional(x):
    return isinstance(x, Fraction) and 0 < x < 1

# given a natural number `n` and a positive integer `b` as, compute the base
# `b` expansion of `n` as a unary procedure `f` over the integers such that
#   n = ... + f(-2)b^-2 + f(-1)b^-1 + f(0)b^0 + f(1)b^1 + f(2)b^2 + ...
#
# since `n` is a  natural number, then f(i) = 0 for any integer `i` such that
# either i < 0 or i > log_b n. thus, there are only finitely many non-trivial
# values of `f` to compute
def natural_to_proc(n, b):
    if not is_natural(n):
        raise SyntaxError("%s is not a natural number." % n)
    if not (isinstance(b, int) and b > 0):
        raise SyntaxError("%s is not a positive integer." % b)

    def proc(i: int):
        if i < 0:
            return 0

        j = -1
        q = n
        while j != i:
            j += 1
            r = q % b
            q = q // b

        return r

    return proc

# given a fractional number `x` and a positive integer `b` as, compute the base
# `b` expansion of `n` as a unary procedure `f` over the integers such that
#   n = ... + f(-2)b^-2 + f(-1)b^-1 + f(0)b^0 + f(1)b^1 + f(2)b^2 + ...
#
# since `x` is a fractional number, then f(i) = 0 for any integer i >= 1 and,
# for some integer j < 0, f(i) is periodic for all integers i < j. thus, there
# are only finitely many non-trivial values of `f` to compute
def fractional_to_proc(x, b):
    if not is_fractional(x):
        raise SyntaxError("%s is not a fractional number." % x)
    if not (isinstance(b, int) and b > 0):
        raise SyntaxError("%s is not a positive integer." % b)

    n = x.numerator
    d = x.denominator

    def proc(i: int):
        if i > 0:
            return 0
        
        j = 1
        r = n
        while j != i:
            j -= 1
            q = r // d
            r = (r % d) * b

        return q

    return proc

# given a non-negative rational number `r` and a positive integer `b` as,
# compute the base `b` expansion of `n` as a unary procedure `f` over the
# integers such that
#   n = ... + f(-2)b^-2 + f(-1)b^-1 + f(0)b^0 + f(1)b^1 + f(2)b^2 + ...
#
# since `r` is a rational number, then there are a natural number `n` and a
# fractional number `x` such that r = n + x. thus, the expansion of `r` is
# simply the concatenation of the expansions of `n` and `x`
def rational_to_proc(r, b):
    if not (isinstance(r, Fraction) and r >= 0):
        raise SyntaxError("%s is not a non-negative fraction." % r)
    if not (isinstance(b, int) and b > 0):
        raise SyntaxError("%s is not a positive integer." % b)

    n = r.numerator // r.denominator
    x = r - n

    def proc(i: int):
        if i < 0:
            return fractional_to_proc(x, b)(i)
        return natural_to_proc(n, b)(i)

    return proc

现在，我想实现一个辅助算法，给定这样一个函数 f(i)，计算哪些数字是周期性重复的，并将它们与其余数字区分开来。更具体地说，我希望它输出一个列表 l 使得 l[0] 是 r 整个部分的数字列表（可能为空），l[1:-1] 是一个r 的小数部分的非周期性重复数字列表（如果有）（否则 l[1:-1] 为空），l[-1] 是小数部分周期性重复数字的列表r 的一部分（如果有的话，否则 l[-1] = []），其中 l[0] 从最低位到最高位排序，其他两个列表从最高位到最低位排序数字。例如，以 10 为基数的 2376661/33000 的输出应该是 [[2, 7], [0, 2, 0], [0, 3]]，因为它的十进制展开是 72.020[03].

我的问题是：我将如何着手实施第二个算法？更具体地说，如果我提前知道输入是一个非负有理数，我将如何区分周期性重复的数字？

Answer 1

步骤：

分成整数和小数部分
通过重复除以 b 来提取整个数字，直到没有任何剩余。
通过重复与 b 相乘来提取小数位数，直到我们达到之前见过的分数。
在我们第一次看到最终分数值的地方拆分小数位。

def analyze(r, b):
    whole, fractional = divmod(r, 1)

    whole_digits = []
    while whole:
        whole, digit = divmod(whole, b)
        whole_digits.append(digit)

    fractional_digits = []
    seen = {}
    while fractional not in seen:
        seen[fractional] = len(fractional_digits)
        digit, fractional = divmod(fractional * b, 1)
        fractional_digits.append(digit)

    s = seen[fractional]
    return [whole_digits,
            fractional_digits[:s],
            fractional_digits[s:] if fractional else []]

演示用法：

from fractions import Fraction

r = Fraction(2376661, 33000)
b = 10

print(float(r))
print(analyze(r, b))

输出（Try it online!）：

72.0200303030303
[[2, 7], [0, 2, 0], [0, 3]]

以 100 为基数的输出（为清楚起见，我编辑了前导零）：

72.0200303030303
[[72], [02, 00], [30]]

基数 1000 的输出（为清楚起见，我编辑了前导零）：

72.0200303030303
[[072], [020], [030, 303]]

判别非负有理数在正整数基上展开的周期重复位数

To discriminate the periodically repeating digits of the expansion of a non-negative rational number in a positive integer base

python

algorithm

number-theory