Статья Автор: Деникина Н.В., Деникин А.В.

1.1 Дробные системы счисления — бесконечные периодические дроби и цифра на позиции

Периодическая дробь — тоже обыкновенная

Если знаменатель не сводится к степени основания, запись бесконечна и периодична. Разворачивать её незачем — достаточно узнать обыкновенную дробь. 0,(01)₂ — это сумма геометрической прогрессии:

0,(01)₂ = 1/4 + 1/16 + 1/64 + ... = (1/4)/(1 - 1/4) = 1/3

Сдвиг записи вправо на один разряд делит число пополам: 0,0(01)₂ = 1/6, 0,00(01)₂ = 1/12 и так далее. Целый ряд таких чисел — это геометрическая прогрессия со знаменателем 1/2 и первым членом 1/3.

Зачем это на олимпиаде

Типовая задача: сложить первые n членов такого ряда, перевести сумму в шестнадцатеричную и посчитать сумму цифр дробной части. Прямое сложение n дробей ничего не даст — n бывает порядка тысяч. Работает формула суммы прогрессии:

S = 1/3 · (1 + 1/2 + 1/4 + ... ) = (2/3)·(1 - 2^-n)

А дальше — знакомый приём. S = (2ⁿ⁺¹ - 2) / (3·2ⁿ), числитель делится на 3 при чётном n, и в двоичной записи получается 1010...10 из n разрядов. Группируем по четыре — каждая четвёрка 1010 даёт цифру A. Если n делится на 4, все n/4 шестнадцатеричных цифр равны A, и сумма цифр равна 10·n/4.

▶ Запустите и проверьте формулу на n = 4, 8 и 2024.

from fractions import Fraction

digits = "0123456789ABCDEF"

def to_hex_frac(x):
    """x < 1 с знаменателем-степенью двойки -> цифры после запятой в 16-ричной"""
    e = x.denominator.bit_length() - 1
    L = ((e + 3) // 4) * 4                  # дополняем до кратного четырём
    bits = bin(x.numerator * 2 ** (L - e))[2:].rjust(L, "0")
    out = ""
    for i in range(0, L, 4):
        out = out + digits[int(bits[i:i + 4], 2)]
    return out

# a_k = 0,0...0(01) в двоичной: (k-1) нулей перед периодом
def a(k):
    return Fraction(1, 3) * Fraction(1, 2 ** (k - 1))

print(a(1), a(2), a(3))

for n in [4, 8, 2024]:
    S = sum(a(k) for k in range(1, n + 1))
    h = to_hex_frac(S)
    print(n, "->", h[:12] + ("..." if len(h) > 12 else ""), "| цифр:", len(h),
          "| сумма цифр:", sum(int(c, 16) for c in h))

Программа печатает:

1/3 1/6 1/12
4 -> A | цифр: 1 | сумма цифр: 10
8 -> AA | цифр: 2 | сумма цифр: 20
2024 -> AAAAAAAAAAAA... | цифр: 506 | сумма цифр: 5060

Аналитический шаг здесь — свернуть ряд и увидеть двоичный узор 1010...10. Всё остальное программа делает механически.

Цифра на заданной позиции

Второй вопрос про бесконечные дроби: какая цифра стоит на k-й позиции после запятой у дроби m/n в системе p. Умножение на p сдвигает запись на разряд влево, поэтому

r = (m · p^k-1) mod n,   цифра = целая часть (r · p / n)

Степень p^k-1 берётся сразу по модулю n — при k порядка миллиона это доли секунды. Тот же самый приём, что и с хвостом степени: показатель огромен, но модуль маленький.

Длина периода такой записи — это порядок p по модулю n. Например, для 1/7 в шестнадцатеричной: 16 = 2 (mod 7), а 2³ = 1 (mod 7), значит период равен 3.

digits = "0123456789ABCDEF"

def digit_at(num, den, p, k):
    """цифра на k-й позиции после запятой у дроби num/den в системе p"""
    r = (num * pow(p, k - 1, den)) % den
    return digits[(r * p) // den]

print("".join(digit_at(1, 3, 2, k) for k in range(1, 13)))
print("".join(digit_at(5, 7, 16, k) for k in range(1, 13)))
print(digit_at(5, 7, 16, 2026))

Программа печатает:

010101010101
B6DB6DB6DB6D
B

Какая цифра стоит на 100-й позиции после запятой в двоичной записи числа 1/3?

Проверить ответ

Чему равна длина периода шестнадцатеричной записи дроби 1/7?

Проверить ответ

Первые 8 членов ряда 0,(01)₂, 0,0(01)₂, 0,00(01)₂, ... сложили. Чему равна сумма цифр дробной части суммы, записанной в шестнадцатеричной системе?

Проверить ответ

Верно или неверно?

Проверить ответ

Итог урока

Все шесть тетрадей — про один и тот же приём. Дробь превращается в обыкновенную, вопрос про цифры превращается в вопрос про остаток, а огромный показатель ужимается периодом. Программа подключается только после этого — и тогда считает мгновенно.

Загрузка...

Чтобы оставить комментарий, необходимо авторизоваться

💬

Пока нет комментариев. Будьте первым!

Печать