Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 найдите число
Период десятичной дроби а/p состоит из чётного числа цифр 2k. Известно, что если этот период умножить на целое число x, где 2 ≤ x ≤ 9, то цифры не изменятся, а лишь сдвинутся по кругу. Я умножил это число на 111-значное число, число стало на 111 знаков больше, если я вам дам первые 111 цифр из полученного числа, вы должны восстановить первоначальное число, и чтобы не было лишних вопросов «а если...», 111 цифр — это подсказка и гарантия для восстановления числа без всяких «если». Да, найдутся товарищи, которые скажут: «1000000... умножить», сразу говорю: нет, число 111-значное, 0000... не имеет.

 Re: найдите число
GogalNikolay в сообщении #1737816 писал(а):
Период десятичной дроби а/p состоит из чётного числа цифр 2k. Известно, что если этот период умножить на целое число x, где 2 ≤ x ≤ 9, то цифры не изменятся, а лишь сдвинутся по кругу. Я умножил это число

Какое "это число"? Ранее в тексте говорится про "число x, где 2 ≤ x ≤ 9, ", вы x умножили? Кто на ком стоял...

Опять у вас проблемы с формулировками. Ну обозначьте вы упоминаемые объекты буквами...

-- добавлено через 6 минут --

GogalNikolay в сообщении #1737816 писал(а):
число 111-значное, 0000... не имеет.

Что это значит? В записи нет четырёх нулей подряд? :D

P.S. У вас четвёртая тема уже называется "найдите число". Серьезно? :facepalm:

 Re: найдите число
wrest в сообщении #1737825 писал(а):
P.S. У вас четвёртая тема уже называется "найдите число". Серьезно
согласен убираю
Просто подумал, может, интересно, кроме меня, кому будет правки нет, я тему убираю.
\documentclass{article}
\usepackage{amsmath}

\begin{document}

\section{Задача о свёртке периода}

\subsection{Условие}

Рассмотрим дробь $\frac{a}{p}$, где $a$ и $p$ — взаимно простые числа, а $p$ — простое. Пусть $N$ — период этой дроби, состоящий из $n$ цифр. Если умножить $N$ на $10^m - 1$ (где $m$ девяток), то:
- При каких условиях произведение будет равно исходному числу $N$?
- При каких условиях произведение будет циклическим сдвигом числа $N$?

\subsection{Теорема}

1. Пусть $N$ — период дроби $\frac{a}{p}$ из $n$ цифр.
2. Умножим $N$ на $10^m - 1$ (где $m$ девяток).
3. Запишем результат как $R = A \cdot 10^n + B$, где $A$ — первые $m$ цифр $N$, а $B$ — последние $n$ цифр.

\textbf{Утверждения:}

1. Свёртка $R$ равна исходному числу $N$ тогда и только тогда, когда $10^m \equiv 2 \pmod{p}$.
2. Если $10^m \not\equiv 2 \pmod{p}$, то свёртка $R$ будет циклическим сдвигом $N$ на $s$ позиций, где $s$ определяется как $10^s \equiv 10^m - 1 \pmod{p}$.
3. При $2a < p$, $A$ будет первыми $m$ цифрами $N$, а $B$ — оставшейся частью $N$ без $A$.

\subsection{Доказательство}

1. $R + N = N \cdot 10^m$.
2. $N \cdot 10^m = S_m + H(10^n - 1)$, где $S_m$ — циклический сдвиг $N$ влево на $m$ цифр, $H$ — первые $m$ цифр.
3. Отсюда $R = H \cdot 10^n + (S_m - N - H)$, и свёртка равна $S_m - N = \frac{10^n-1}{p}((a \cdot 10^m \bmod p) - a)$.

\subsection{Пример}

Рассмотрим период $\frac{23}{223}$ (222 цифры). Умножим на 18 девяток:
- Первые 18 цифр: 103139013452914798.
- Свёртка возвращает исходное число $N$, так как $10^{18} \equiv 2 \pmod{223}$.

\subsection{Таблица волшебных \(m\)}

\begin{center}
\begin{tabular}{|c|c|c|}
\hline
$p$ & период & $m$ восстановления \\
\hline
7 & 6 & 2 \\
17 & 16 & 10 \\
19 & 18 & 17 \\
23 & 22 & 8 \\
29 & 28 & 11 \\
223 & 222 & 18 \\
\hline
\end{tabular}
\end{center}

\end{document}

 Re: найдите число
Пример 3: m = 111 = n/2 для \frac{23}{223}

Здесь выполняется условие Миди для половинок: 10^{111} \equiv -1 \pmod{223}. Период

N = 103139013452914798206278026905829596412556053811659192825112107623318385650224215246636771300448430493273542600896860986547085201793721973094170403587443946188340807174887892376681614349775784753363228699551569506726457399

разбивается на две половины по 111 цифр, и они дают в сумме 111 девяток. Умножим N на 10^{111}-1; произведение имеет 111+222 = 333 цифры и распадается на блоки A (111 цифр) и B (222 цифры):

A = 103139013452914798206278026905829596412556053811659192825112107623318385650224215246636771300448430493273542600

B = 793721973094170403587443946188340807174887892376681614349775784753363228699551569506726457399103139013452914798206278026905829596412556053811659192825112107623318385650224215246636771300448430493273542601

Поскольку 2a = 46 < p = 223, заем через границу блоков не происходит, и A — это в точности первая половина периода N, без всякой поправки. Тогда вторая половина восстанавливается через девятки:

\underbrace{99\ldots9}_{111} - A = 896860986547085201793721973094170403587443946188340807174887892376681614349775784753363228699551569506726457399,

и это в точности вторая половина N. Восстановление:

N = A \ |\ (\underbrace{99\ldots9}_{111} - A).

Свёртка A+B (222 цифры):

793721973094170403587443946188340807174887892376681614349775784753363228699551569506726457399103139013452914798206278026905829596412556053811659192825112107623318385650224215246636771300448430493273542600896860986547085201

Это циклический сдвиг N на s = 129 позиций: условие сдвига даёт 10^s \equiv 10^{111}-1 \equiv -2 \pmod{223}, а поскольку 10^{111} \equiv -1 и 10^{18} \equiv 2, получаем s \equiv 111 + 18 = 129 \pmod{222} — в свёртке соединились оба «магических» показателя: 111 от Миди и 18 от восстановления.

Заметь, чем этот случай красивее полного набора девяток: там передний блок был N-1 и нужна была поправка +1, а здесь при m = n/2 с выполненным условием Миди передний блок совпадает с первой половиной периода напрямую, и число склеивается из двух половинок мгновенно — одна из них дана в произведении как есть, вторая получается вычитанием из девяток.
Пример 3: m = 111 = n/2 для \frac{23}{223}

Здесь выполняется условие Миди для половинок: 10^{111} \equiv -1 \pmod{223}. Период N имеет 222 цифры и разбивается на две половины X и Y по 111 цифр, дающие в сумме 111 девяток:

X = 103 139013 452914 798206 278026 905829 596412 556053
811659 192825 112107 623318 385650 224215 246636
771300 448430 493273 542600

Y = 896 860986 547085 201793 721973 094170 403587 443946
188340 807174 887892 376681 614349 775784 753363
228699 551569 506726 457399


Умножим N на 10^{111}-1: произведение имеет 333 цифры и распадается на блок A (старшие 111 цифр) и блок B (младшие 222 цифры). Поскольку 2a = 46 < p = 223, заема через границу блоков нет, и

A = 103 139013 452914 798206 278026 905829 596412 556053
811659 192825 112107 623318 385650 224215 246636
771300 448430 493273 542600


— в точности первая половина периода, A = X.

Восстановление. Вторая половина периода получается вычитанием из девяток:

999...9 (111 девяток) - A = 896 860986 547085 201793 721973 094170
403587 443946 188340 807174 887892 376681 614349
775784 753363 228699 551569 506726 457399


и это в точности Y. Итого N = A \,\|\, (\underbrace{99\ldots9}_{111} - A) — период склеивается из двух половинок без всяких поправок.

Отсюда изящное следствие: раз X + Y = 10^{111}-1, то 10^{111} - Y = X+1, и младший блок произведения расщепляется как

B = (Y-X-1)\cdot 10^{111} + (X+1).

В самом деле, последние 111 цифр B — это X+1 (ср. с концом X: ...493273 542600 против ...493273 542601 в B).

Замечание. Не путать два объекта: вычитание 999\ldots9 - A даёт вторую половину периода (это восстановление, 111 цифр), а свёртка A+B — число из 222 цифр, и по общей теореме она равна циклическому сдвигу N на s = 129 позиций: 10^s \equiv 10^{111}-1 \equiv -2 \pmod{223}, откуда s = 111 + 18 — в свёртке соединяются оба «магических» показателя: 111 от Миди и 18 от восстановления.

 Re: найдите число
wrest в сообщении #1737825 писал(а):
.S. У вас четвёртая тема уже называется "найдите число". Серьезно? :facepalm:

Четвёртая тема: никак мы с вами не сойдёмся, вы ж меня извините, я ведь ни на что не претендую, просто выявил, что никто не обращал внимания, и всё. :oops:
Откуда это берётся: замечания к примеру 3

Разбиение периода на половины, дающие в сумме девятки, — классическая теорема Миди (1836): если период дроби с простым знаменателем имеет чётную длину $n = 2m$, то его половины дополняют друг друга до $m$ девяток. Этим мы и воспользовались. Известны и обобщения: на составные знаменатели, на разбиение на $k > 2$ частей, на другие системы счисления.

Но у нашего восстановления есть два следствия, которые в литературе о Миди отдельно обычно не выделяют.

1. Тождество с множителем. Из теоремы Миди следует, что если $X$ — первая половина периода, то $N = (X+1)(10^m - 1)$. Действительно, вторая половина равна $(10^m - 1) - X$, поэтому

$$
N = X \cdot 10^m + \left(10^m - 1 - X\right) = (X+1)\left(10^m - 1\right).
$$

Простой пример: $142857 = 143 \times 999$. Период дроби $\frac{1}{7}$ — это в точности 143 экземпляра девяток. Заметили: множитель $X+1$ — это то самое число, которое появляется в хвосте произведения при умножении периода на длинную строку девяток. Хвостовая копия — не случайность, а прямое следствие этого тождества.

2. Инвариантность переднего блока. При умножении периода на $10^M - 1$ с $M \geq m$ первые $m$ цифр произведения совпадают с $X$ при любом $M$. Причина проста: произведение распадается на копии $N$ со сдвигом, а вычитание соседних копий порождает заём, который «не дотягивается» до старшего блока. Поэтому восстановление по переднему блоку работает без поправок при любом достаточно длинном множителе — что и показано в примере 3 (проверено вплоть до 223 девяток).

3. Восстановление периода по двум блокам. Собирая сказанное: зная только первые $m$ цифр периода (блок $X$), восстанавливаем весь период как $X \,\|\, (10^m - 1 - X)$ — одно вычитание и склейка. Если в руки попала хвостовая копия — блок $X+1$, — сначала вычитаем единицу, затем дополняем до девяток и склеиваем. Оба входа дают один и тот же период; чистый вход — через передний блок, запасной — через хвостовой.

 Re: найдите число
GogalNikolay в сообщении #1737981 писал(а):
2. Инвариантность переднего блока. При умножении периода на $10^M - 1$ с $M \geq m$ первые $m$ цифр произведения совпадают с $X$ при любом $M$.

Тут надо глубже доказывать, ибо если "передний блок" будет начинаться с цифр 5,6,7,8,9, то он не будет "инвариантным".
Например 535464*999=534928536
Соответственно, вам надо доказать, что "передний блок" начинается только с цифр 1,2,3,4
Если доказать не сможете, то и всё рассуждение ошибочное.

 Re: найдите число
wrest в сообщении #1738048 писал(а):
начинается только с цифр 1,2,3,4

Это я всё давно проходил, только в данном случае, если число начинается с 5, то при умножении на 2 уже будет лишняя 1, а у нас.
Известно, что если этот период умножить на целое число x, где 2 ≤ x ≤ 9, то цифры не изменятся,

 Re: найдите число
GogalNikolay в сообщении #1738050 писал(а):
Известно, что если этот период умножить на целое число x, где 2 ≤ x ≤ 9, то цифры не изменятся,

Хорошо, ну так надо было в вашем пункте 2
GogalNikolay в сообщении #1737981 писал(а):
2. Инвариантность переднего блока.
написать об этом.

 Re: найдите число
wrest в сообщении #1738052 писал(а):
написать об этом.

Ваш пример корректен арифметически, но он попадает в случай, который в моей формулировке был оговорён небрежно, а не опровергает утверждение. Вот точная схема.

Пусть период $N = X \cdot 10^m + Y$, где $X + Y = 10^m - 1$ (теорема Миди). Умножаем на множитель из $M$ девяток, т.е. считаем $N(10^M - 1)$.

Хвостовой блок. Последние $m$ цифр результата — всегда $X+1$. Это то самое «$+1$» из моего поста, оно выполняется без условий.

Передний блок при $M \geq 2m$. Если число девяток в множителе не меньше длины всего периода, то первые $m$ цифр результата равны $X$ безусловно. Доказательство: $N \cdot 10^M - N = (N-1) \cdot 10^M + (10^M - N)$; так как $N < 10^M$, заём при вычитании замыкается в младших $M$ разрядах и до старшего блока не доходит, а $N-1$ сохраняет передний блок $X$, поскольку $Y \geq 1$ (период $1/p$ не оканчивается нулём: $Np = 10^{2m}-1 \equiv 9 \pmod{10}$).

Передний блок при $M = m$. Здесь правило двухступенчатое:
$$
N(10^m - 1) = (X-\varepsilon)\,\big|\,(Y - 1 - X + \varepsilon \cdot 10^m)\,\big|\,(X+1),
\qquad \varepsilon = 1 \iff X \geq 5\cdot 10^{m-1}.
$$
То есть если передний блок начинается с цифры 5–9, он выходит уменьшенным на единицу. Именно это и происходит в вашем примере: $X = 535 \geq 500$, формула даёт $534\,|\,928\,|\,536 = 534928536$ — совпадает с вашим вычислением дословно. Хвост $X+1 = 536$ при этом на месте, так что структура не ломается, а уточняется.

Два замечания вдогонку.

Во-первых, число 535464 удовлетворяет условию Миди ($535 + 464 = 999$), но не является периодом никакой дроби $1/p$: $999999/535464$ — не целое. Для настоящих периодов $1/p$ ($p$ простое, $p \neq 2,5$) верно даже больше, чем вы требуете: $X = \lfloor N/10^m \rfloor < 10^m/p \leq 10^m/7 < 2\cdot 10^{m-1}$, то есть передний блок начинается с 0 или 1 — случай 5–9 для $1/p$ не возникает в принципе. Он возникает только для дробей $a/p$ с большим $a$: например $4/7 = 0.(571428)$, $X = 571$, и действительно $571428 \cdot 999 = 570856572 = 570\,|\,856\,|\,572$ — передний блок $X-1$, хвост $X+1$, всё по формуле.

Во-вторых, уже при $M = 2m$ передний блок сохраняется и для $X$, начинающегося с 5–9: $571428 \cdot 999999 = 571427428572 = 571\,|\,427\,|\,428\,|\,572$.

Итого: инвариантность переднего блока — доказанное свойство, но с корректным условием «девяток не меньше длины периода» (в основном примере поста — 223 девятки против 6-значного периода, запас колоссальный). При коротком множителе из ровно $m$ девяток правило уточняется: передний блок равен $X$ или $X-1$ в зависимости от первой цифры, хвостовой блок всегда $X+1$.

 Re: найдите число
GogalNikolay в сообщении #1738054 писал(а):
инвариантность переднего блока — доказанное свойство, но с корректным условием «девяток не меньше длины периода»

Доказательства не видно что-то. Я не говорю, что утверждение про "инвариантность переднего блока" в новой формулировке неверно. Я говорю, что доказательства не представлено.

 [ Сообщений: 10 ] 


Соглашение о конфиденциальности | Общие правила

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group