найдите число

[wrest]

Booker48
Функция для вычисления знаменателя дроби по периоду

period_to_denom(P) = my(s=Str(P)); (10^#s-1)/gcd(eval(s), 10^#s-1)

Запуск:

? period_to_denom("01")
%1 = 99

Функция вычисления длины периода по знаменателю

denom_to_period=my(q=n/(2^(valuation(n,2))*5^valuation(n,5)));return(znorder(Mod(10,q)))

 Запуск:

? denom_to_period(99)
%1 = 2
? denom_to_period(99*99)
%2 = 198
?

[Booker48]

wrest
Ну да, но хотелось сделать именно само умножение, а не вычисление длины периода. )))
Ну, как бы складывать периодические дроби где-то проще, чем обыкновенные: выравниваем периоды и вперёд. )))
А вот умножение - Адъ и Израиль.

[wrest]

Booker48 в сообщении #1737821 писал(а):

Ну, как бы складывать периодические дроби где-то проще, чем обыкновенные:

Чем же проще?

-- добавлено через 40 секунд --

Booker48 в сообщении #1737821 писал(а):

выравниваем периоды

А если они взаимно-простые?

[Booker48]

wrest в сообщении #1737823 писал(а):

А если они взаимно-простые?

Никто не обещал. что будет совсем просто. )))
Но в сущности да, придется повторять однотипные действия, возможно много раз.
Но всё ограничивается сложением, если не считать приписывания периодов, пока они не совпадут по длине.

[Dmitriy40]

Есть и с меньшим периодом длиной 7:
3388: 3389 50821 4272269 39744629 91069441 109977869 164097781

И длиной 8:
5780: 17341 28901 433501 1086641 10155461 23836721 17256525241 81049425761

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

А есть и длиной 9:
875140: 875141 8751401 19253081 1769533081 2111712821 2153719541 4184919481 4851776161 10624263485221
1515572: 7577861 257647241 331910269 341003701 718381129 803253161 2021773049 1515518954981 85828924755929
1879420: 1879421 13155941 39467821 45106081 107126941 327019081 360848641 2317324861 27470420267701

[wrest]

Dmitriy40 в сообщении #1737832 писал(а):

А есть и длиной 9:

Да что ж такое, я видать не там искал.

[gris]

я всё о своём. Никак не могу найти обратки с периодом 74. До 12 млрд нашлось только 7253.
И с полпериодом 148 тоже мало: 149, 3109, 111149. Остальные, видимо, далеко.
У меня всё по-простому. Беру большое число и формирую вектор длин( можно и половин). И просматриваю все простые до этого числа. Элемент вектора с номером, равным длине периода, увеличиваю на 1. Сам по себе вектор интересный:) Ищу в нём семёрки и шестёрки.

{N=50 000 000; vklp=vector(N);
forprime(p=7,N,
   k=znorder(Mod(10,p));
   vklp[k]++;
);
for(i=1,N,if(vklp[i]>5,print(i," ", vklp[i])));
}
1620 6
3140 6
5780 6
15900 7
46620 6

По длинам и простые нахожу. Но до 50 мдрд.
Что делать?

[Dmitriy40]

Что интересно период вполне может быть и нечётным:
409: 1637 13907 77711 1375877 2777111 5371851809
3343023: 73546507 133720921 180523243 220639519 447965083 588372049 4045057831

gris в сообщении #1737837 писал(а):

Что делать?

Я дальше для найденных запускаю перебор простых, причём сразу с шагом k:

? foreach([32,214,380,409,686,1620,15900],k, print1(k,":"); forprimestep(p=1,1e10,k, if(Mod(10,p)^k==1 && znorder(Mod(10,p))==k, print1(" ",p))); print);
32: 353 449 641 1409 69857
214: 1499 28463 74687 392263 795653
380: 761 1901 3041 74861 417332341
409: 1637 13907 77711 1375877 2777111 5371851809
686: 1373 14407 46649 209917 275087
1620: 1621 8101 19441 27541 68041 119881
15900: 15901 63601 95401 111301 349801 5724001 5739901
time = 1min, 32,962 ms.

[wrest]

gris в сообщении #1737837 писал(а):

я всё о своём. Никак не могу найти обратки с периодом 74.

Я вас обманул :( Период 74*2=148 Простые:
[149, 3109, 111149, 708840373781, 669031686661427842829, 40548140514062774758071840361]

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

Dmitriy40 в сообщении #1737840 писал(а):

Что интересно период вполне может быть и нечётным:

Да, может. Просто изначально в теме фигурировали чётные периоды. Они подпадают под теорему Миди.

[Dmitriy40]

gris в сообщении #1737837 писал(а):

Что делать?

А для малых периодов через факторизацию проще и быстрее (похоже wrest именно так и искал):

? for(k=2,65, w=select(p->znorder(Mod(10,p))==k, factor(10^k\9)[,1])~; if(#w>=5, print(k,": ",w,", len=",#w)); );
29: [3191, 16763, 43037, 62003, 77843839397], len=5
32: [353, 449, 641, 1409, 69857], len=5
61: [733, 4637, 329401, 974293, 1360682471, 106007173861643, 7061709990156159479], len=7
63: [10837, 23311, 45613, 45121231, 1921436048294281], len=5
1,396 ms
...
79: [317, 6163, 10271, 307627, 49172195536083790769, 3660574762725521461527140564875080461079917], len=6
81: [163, 9397, 2462401, 676421558270641, 130654897808007778425046117], len=5
89: [497867, 103733951, 104984505733, 5078554966026315671444089, 403513310222809053284932818475878953159], len=5
91: [547, 14197, 17837, 4262077, 43442141653, 316877365766624209, 110742186470530054291318013], len=7
107: [643, 999809, 9885089, 215257037, 2386760191, 511399538427507881, 646826950155548399, 10288079467222538791302311556310051849], len=8

Кстати оказывается длина 7 достигается уже для периода длиной 61.
И длина 5 есть уже для 29.

[GogalNikolay]

wrest в сообщении #1737841 писал(а):

Да, может. Просто изначально в теме фигурировали чётные периоды. Они подпадают под теорему Миди.

Гинзберг (Ginsberg). Он показал: если период дроби разбить на три части равной длины и сложить их, то в ряде случаев сумма тоже будет кратна числу из одних девяток (то есть будет «работать аналог теоремы Миди для делителя 3» При этом есть важный нюанс: для нечётных делителей (вроде 3) ситуация в целом менее предсказуема, чем для чётных. В некоторых случаях сумма действительно даёт нужный результат, а в других могут возникать переносы при сложении, и картина нарушается. Например, для дроби 3/7 период тоже имеет длину 6 (то есть 3×2), но если складывать тройки цифр попарно (42 + 85 + 71), получится 198 — это уже не просто «999», а 2×99.

[wrest]

Dmitriy40 в сообщении #1737848 писал(а):

похоже wrest именно так и искал

Я искал в таблице ("cunningham project")
https://web.archive.org/web/20201127042 ... fac10p.txt

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

GogalNikolay в сообщении #1737853 писал(а):

Например, для дроби 3/7 период тоже имеет длину 6 (то есть 3×2), но если складывать тройки цифр попарно (42 + 85 + 71), получится 198 — это уже не просто «999», а 2×99. Я когда-то этот казус с Гинзбергом устранял, показывал, как и почему в таких случаях не работает.

Это не казус, теорема Миди (расширенная) об этом прямо говорит.

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

GogalNikolay в сообщении #1737853 писал(а):

если период дроби разбить на три части равной длины и сложить их,

На любое количество равных частей, которому кратна длина периода.

[GogalNikolay]

wrest в сообщении #1737854 писал(а):

Этотне казус, теорема Миди (расширенная) об этом прямо говорит.

\subsection*{Следствие (умножение на полное число девяток)}

Пусть $N$ --- период дроби $\frac{a}{p}$ из $n$ цифр. Умножим его на $10^n-1$:

$$ N(10^n-1) = N\cdot 10^n - N = (N-1)\cdot 10^n + (10^n - N). $$

Отсюда три факта:

\textbf{1.} Произведение распадается на два блока по $n$ цифр: спереди стоит $N-1$, сзади --- $10^n - N$. Поэтому исходное число восстанавливается тривиально: прибавлением единицы к переднему блоку.

\textbf{2.} Свёртка произведения равна

$$ (N-1)+(10^n-N) = 10^n - 1, $$

то есть числу из одних девяток --- независимо от того, совместима ли дробь с теоремой Миди. Более того, это согласуется с общей формулой: при $m=n$ имеем $10^n \equiv 1 \pmod p$ (свойство периода), вычет равен нулю, и свёртка обязана давать $99\ldots9 \equiv 0 \pmod p$.

\textbf{3.} Если дробь совместима с Миди, то девять-дополнение заднего блока $99\ldots9 - (10^n-N) = N-1$ --- это циклический сдвиг $N$: пара Миди возникает в произведении автоматически.

\textit{Пример.} $142857 \cdot 999999 = 142856\,857143$: передний блок $142856$, $+1$ даёт исходное число; задний блок $857143$ --- сдвиг семёрки, а его девять-дополнение $142856$ замыкает пару Миди.

Практический вывод: если даны первые $n$ цифр произведения $N(10^n-1)$, число $N$ восстанавливается одним прибавлением единицы --- даже без знания $p$.

[Dmitriy40]

Из A003020 и A102380 можно получить точное разложение для всех k<353.
Проверка их даёт следующие минимальные периоды для каждой длины (отдельно чётные и нечётные периоды):

32: [353, 449, 641, 1409, 69857], len=5
148: [149, 3109, 111149, 708840373781, 669031686661427842829, 40548140514062774758071840361], len=6
206: [1237, 44092859, 102860539, 984385009, 612053256358933, 182725114866521155647161, 1471865453993855302660887614137521979], len=7
29: [3191, 16763, 43037, 62003, 77843839397], len=5
61: [733, 4637, 329401, 974293, 1360682471, 106007173861643, 7061709990156159479], len=7
79: [317, 6163, 10271, 307627, 49172195536083790769, 3660574762725521461527140564875080461079917], len=6
107: [643, 999809, 9885089, 215257037, 2386760191, 511399538427507881, 646826950155548399, 10288079467222538791302311556310051849], len=8
131: [80173, 109517, 141811693, 446790173, 7370364319027, 15594845538029429933, 7317723970031057677693, 131758351065116151205213, 180222062287834025451247081], len=9

Причём эти длины точные, никаких ещё больших делителей не осталось.

[GogalNikolay]

wrest в сообщении #1737854 писал(а):

На любое количество равных частей, которому кратна длина периода.

Это-то ясно, только при этом не всегда будут одни 9.