Делимость на 1989

[wpoms.]

Пусть `x = a_1a_2...a_n` является `n`-значным числом, где `a_1, a_2, ... , a_n` (`a_1 != 0`) - его цифры. `n` чисел `x_1 = x = a_1a_2...a_n`, `x_2 = a_na_1...a_{n-1}`, `x_3 = a_{n-1}a_na_1...a_{n-2}`, `x_4 = a_{n-2}a_{n-1}a_na_1...a_{n-3}`, `...` , `x_n = a_2a_3...a_na_1` получены из числа `x` циклической перестановкой его цифр. [Например, если `n = 5` и `x = 37001`, то полученными в результате циклической перестановки цифр числами будут `x_1 = 37001`, `x_2 = 13700`, `x_3 = 01370` (`= 1370`), `x_4 = 00137` (`= 137`), `x5 = 70013`.] Найдите, с доказательством, (i) наименьшее натуральное число `n` для которого существует `n`-значное число `x`, такое что все `n` чисел, полученных циклической перестановкой цифр из числа `x`, делятся на `1989`; (ii) наименьшее натуральное число `x`, обладающее этим свойством.

@темы: Теория чисел

Comments

[All_ex]

В теории чисел я не силён... но попробую...

`1989 = 9*13*17`...
Из `x = 0 mod 9` следует, что сумма цифр числа `x` должна быть кратна 9... это очевидно будет сохраняться при перестановке цифр...

Пусть `A = a_1a_2...a_{n-1}, \ \ B = a_n`, тогда `x = A*10 + B `...
Признак делимости на 13: `A*10 + B = 0 mod 13 \ \ iff \ \ A - 9*B = 0 mod 13`...
Признак делимости на 13: `A*10 + B = 0 mod 17 \ \ iff \ \ |A - 5*B| = 0 mod 17`... (здесь очевидно, что `A` должно быть много больше, чем `45 >= 5*B`... поэтому модуль можно не писать)...

Число `x_1 = A*10 + B `, тогда число `x_2 = a_na_1...a_{n-1} = B*10^n + A` …
Перепишем последнее число в виде `x_2 = B*(10^n +9) + (A - 9*B) = B*(10^n +5) + (A - 5*B)` ... Если `x_1` кратно `13*17`, то либо `B = 0`, либо должны выполняться равенства `{(10^n +9 = 0 mod 13), (10^n +5 = 0 mod 17):}` ...

Проведённые рассуждения справедливы для любой пары соседних чисел из данных в условии... И поскольку не все цифры в записи числа `x` нулевые, то из полученной системы и определяется минимальное значение `n`…

Как такая система решается аналитически я себе не представляю... посчитал в Excel... получил, что `n = 47`... надеюсь, что нашёл верно...

О минимальном числе...
Поскольку `{(10^{47} +9 = 0 mod 13), (10^{47} +5 = 0 mod 17):}`, то `10^{47} +22 = 0 mod (13*17)` … Таким образом, искомое число имеет вид `N = (10^{47} +22) + 221*k`, где `k` подбирается таким, чтобы число `N = 0 mod 9` ...
Итого, `N = (5 + 5*k) mod 9`, следовательно, `k = 8`, при этом `N = 100...001790` ...


Наверное так…

[Adjirranirr]

получил, что `n = 47`

Вот блин. А я на GRID-кластере полный перебор делал двое суток, дошел до `n = 44` и плюнул =)

Длина числа, кстати, получается `48`, так как в числе `10^{47}` `48` цифр.

Как такая система решается аналитически я себе не представляю...

Есть варианты. Но по сути, все они — алгоритмы с субэкспоненциальной (или выше) сложностью, и на маленьких числах почти не отличаются от полного перебора. Для перебора достаточно найти числа `k` и `m` такие, что `0 <= k < 13` и `10^k \equiv 4 \text{mod} 13`, и `0 <= m < 17` и `10^m \equiv 12 \text{mod} 17`. Потом, на основании малой теоремы Ферма, получим `n = 16*q + m = 12*p + k`, или `n = 16*q + 15 = 12*p + 11`, откуда `3p - 4q = 1` c минимальным решением `p = 3,\ q = 2`, и `n = 47`.

По решению, остается только показать, что число `100000000000000000000000000000000000000000001790` действительно удовлетворяет условию =)

[Adjirranirr]

Как вариант без переборов — `\sum_{i = 1}^{n} x_i = 1111...111 * \sum_{i = 1}^{n} a_i = a * 9 * \frac {10^n - 1} {9} = a * 10^n - a`. Так как каждое из `x_i` делится на `1989`, то на `1989` делится и их сумма, и `a * 10^n \equiv a \text{mod} 1989 => 10^n \equiv 1 \text{mod} 1989`.
Сравнения `10^{p} \equiv 1 \text{mod} 17`, `10^{q} \equiv 1 \text{mod} 13` и `10^{s} \equiv 1 \text{mod} 9` имеют решения `p = 16*a,\ q = 12*b,\ s = c,\ a,b,c \in NN`, откуда наименьшее значение `n` есть `n = \text{lcm}(16,\ 12,\ 1) = 48`, и наименьшая длина числа — `48` десятичных цифр. Ну, а число уже найдено =)

[All_ex]

Adjirranirr? Вот блин. А я на GRID-кластере полный перебор делал двое суток, дошел до `n = 44` и плюнул =) - Я считал используя признак делимости... там всё на экранную страницу помещается...
Причём проверял двумя способами...
Второй вариант основан на преобразовании `x_2 = {x_1 - B}/{10} + B+10^{n} = {x_1 + B*(10^{n+1} - 1)}/{10}`... откуда число из `(n+1)`-ой единицы должно делится на 13 и 17 одновременно... (тоже одна страница Excel'я)...
Вот только из этого рассуждения трудно выйти на нахождение минимального числа...

Конечно, Excel'вские вычисления, использующие признаки делимости, можно провести вручную... но где уверенность, что они закончатся достаточно быстро...

[All_ex]

Adjirranirr, Длина числа, кстати, получается `48`, так как в числе `10^{47}` `48` цифр. - а вот в этом я похоже всё-таки запутался...

[Adjirranirr]

Я считал используя признак делимости... там всё на экранную страницу помещается...

Ну полностью распараллеленный код на C++ с оптимизационными вставками ассемблера для полноценной работы регистров xmm у меня занял всего 4 экрана. Не так уж и много =) А вот по времени полный перебор очень затратен. Особенная беда с целочисленным делением на `1989` и с тем, что пришлось для представления числа использовать четверку xmm3:xmm4:xmm1:xmm2. На скорости сильно сказалось =)

но где уверенность, что они закончатся достаточно быстро...

Excel умеет делить с остатком более-менее быстро. А вот у меня, например, уже вычисление `10^{7} \text{mod} 1989` заняло бы прилично времени.

число из `(n+1)`-ой единицы должно делится на 13 и 17 одновременно...

На самом деле, просто. По малой теореме ферма, все решения уравнения `a^{n} \equiv 1 \text{mod} p`, где `p` — простое число, имеют вид `n = k * (p - 1)`. Откуда `10^(n + 1) \equiv 1 \text{mod} 17 <=> n + 1 = k * 16,\ 10^{n + 1} \equiv 1 \text{mod} 13 <=> n + 1 = m * 12`, и минимальное `n` — `47`.

[Груша Вильямс]

Я так делал :
Так как каждое делится на `1989`, то и сумма тоже, суммирая (или записывая сумму) в столбик сразу видно, что если разложить эту сумму на множители, то один из них `a_1+a_2+...+a_n`.
Раскладываем
`(a_1+...+a_n)+ 10*(a_1+...+a_n)+...+10^n*(a_1+...+a_n)=(a_1+...+a_n)*(1+10+...+10^n)=(a_1+...+a_n)*((10^n-1)/9)=`
`=9l*((10^n-1)/9)=l*(10^n-1)=1989k` ,
`10^n \equiv 1\text{mod}1989` и всё на этом...

Adjirranirr, По малой теореме ферма, все решения уравнения `a^n \ equiv 1 \ text{mod}p`, где `p` — простое число, имеют вид `n=k(p-1)` .
А как это доказать? Малую теорему Ферма только с этой стороны знаю `a^p-a \equiv 0\text{mod}p` при целых `a!=pk`

[All_ex]

Adjirranirr, На самом деле, просто. По малой теореме ферма, - вот её то я и не знаю... ... в универе нам теорию чисел не читали, а до самостоятельно изучения не добрался...
Красиво у Вас получилось... то есть с деления единиц можно найти длину числа аналитически...

Excel умеет делить с остатком более-менее быстро. - я делил только числа порядка 1000 на 13 и 17 ...

[Груша Вильямс]

All_ex, похоже ошибку нашел...`x_2=a_na_1...a_(n-1)=B*10^(n-1)+A` старший показатель меньше количества разрядов на единицу...
и у меня тогда уравнение `10^(n-1) \equiv 1\text{mod}1989` ...и `n-1=48` тогда. Что-то запутался я...число же вроде бы есть уже и в нем `48` цифр, а не `49`.

[All_ex]

Груша Вильямс, похоже ошибку нашел...`x_2=a_na_1...a_(n-1)=B*10^(n-1)+A` старший показатель меньше количества разрядов на единицу...
например, `x = 1234 = 123*10 + 4`... следовательно, `x_1 = 4*10^{4 -1} + 123`... то есть `n-1` в степени... и Вы правы...

[Груша Вильямс]

All_ex, например `n=4`,`a_1=1`, `a_2=2`, `a_3=3` и `a_4=4`, `x_1=1234`, тогда `A=123`, `B=4`,
таким образом получается `x_1=A*10+B=1230+4=1234`и `x_2=B*10^n+A=4*10^4+123=40000+123=40123`, то есть `n=5` выходит...

В условии ведь написано, что `x_1=x=a_1a_2...a_n`, значит если `x=1234`, то и `x_1=1234`, a `4*14^4+123=153787`

[Груша Вильямс]

Ой, Вы скорее всего вместо `14` `10` имели ввиду, я вначале подумал что в `14` скрытый смысл

[All_ex]

... Мдя... несу ересь...
В степени действительно `n-1`... значит `n-1 = 47` ... итого в числе 48 цифр... если опять не запутался...

[Груша Вильямс]

All_ex, да, дальше тоже самое выходит и число это же, но если решать так (чтобы найти `n`):
`(a_1+...+a_n)+10*(a_1+...+a_n)+...+10^(n-1)*(a_1+...+a_n)=(a_1+...+a_n)*(1+10+...+10^(n-1))=(a_1+...+a_n)*((10^(n-1)-1)/9)=`
`=9l*((10^(n-1)-1)/9)=l*10^(n-1)-l=1989k`
`10^(n-1)\equiv 1\text{mod}1989`
и вот тут самое интересное, если делать как Adjirranirr, то `n-1=\text{lcm}(16,\12,\1)=48`, `n=49`...вот и понять не могу

собственно идея так делать так появилась

[Груша Вильямс]

Ещё такая мысль была: расставим цифры числа `x_1` на окружности, тогда все остальные числа будут получаться `n-1` поворотом окружности...но это вроде тоже самое, хотя вначале казалось, что из этого можно как-то комбинаторно делитель `n-1` найти...

[All_ex]

Груша Вильямс, Ну, вообще-то суммируя геометрическую прогрессию получаем так ... `1 + 10 + ... + 10^(n-1) = {10^n - 1}/9 ` ...
Поэтому дальше получим, что `n = 48`...

[Груша Вильямс]

All_ex, блин вот ведь знаю, что показатель - число членов прогрессии, а постоянно пишу показатель последнего члена...Спасибо