Циклические числа

[Ian]

n-значное число в десятичной системе счисления назовем циклическим, если от переноса его первой цифры в конец получилось, как будто его умножили на m. Если написать циклическое число два раза подряд, снова получится циклическое, отсюда и название. Возникает вопрос о минимально возможном n для данного m. Например, при m=3 n=6. Но закономерности не наблюдается, а должна быть. Точно должна быть в p-ичной системе счисления, где p простое. Сделал программку для построения циклических чисел "с хвоста", но путаюсь. И кстати, чем определяется множество цифр [math]a, которые переносятся, кроме конечно [math]am<10

[zykov]

С какого конца переносим? (Есть два конца.)
После переноса тоже должно быть цикличным или это только один раз?

[Ian]

первую цифру (старший разряд) делаем младшим. Например 142857 в 428571. Ну а дальше, с 428571 такое маловероятно, старший разряд уже вырос в разы

[zykov]

Понятно.

Ну для [math]m=1 все тривиально. Подходит любое число, которое состоит только из одинаковых цифр (и только такие числа). Так что самое короткое - любое однозначное (наверно кроме нуля).

Для [math]m>1 представим число как сумму старшей цифры и остатка: [math]a10^{n-1}+b, \; 1\leq a \leq 9, \; 10^{n-2}\leq b < 10^{n-1} (очевидно [math]n\geq 2).
Тогда имеем [math]m(a10^{n-1}+b)=10b+a и следовательно [math]a(m10^{n-1}-1)=b(10-m).
Из этого равенства и того что [math]b<10^{n-1} имеем [math]a(m10^{n-1}-1)<(10-m)10^{n-1}. Следовательно [math]10^{n-1}(10-m-am)>a и отсюда получаем [math]10-m-am>0, т.е. [math]m(a+1)<10.
Значит:
1) При [math]m\geq5 решений вообще нет.
2) При [math]m\in\{2,3,4\}:
--> [math]m=2: [math]a\in\{1,2,3\}
--> [math]m=3: [math]a\in\{1,2\}
--> [math]m=4: [math]a=1


[math]m=2:
Уравнение [math]a(2 \cdot 10^{n-1}-1)=8b. Решений нет, т.к. правая часть делится на 8, а левая нет (левая часть - это произведение [math]a\in\{1,2,3\} на нечётное число).

[math]m=4:
Уравнение [math]4 \cdot 10^{n-1}-1=6b. Решений нет, т.к. правая часть делится на 2, а левая нет.

[math]m=3:
Уравнение [math]a(3 \cdot 10^{n-1}-1)=7b, где [math]a\in\{1,2\}.
[math]3 \cdot 10^1-1=29 - нет
[math]3 \cdot 10^2-1=299=13\cdot23 - нет
[math]3 \cdot 10^3-1=2999 - нет
[math]3 \cdot 10^4-1=29999=131\cdot229 - нет
[math]3 \cdot 10^5-1=299999=7\cdot17\cdot2521 - да ([math]b=a\cdot42857)
[math]3 \cdot 10^6-1=2999999 - нет
[math]3 \cdot 10^7-1=29999999 - нет
[math]3 \cdot 10^8-1=299999999=13\cdot23076923 - нет
[math]3 \cdot 10^9-1=2999999999=16937\cdot177127 - нет
[math]3 \cdot 10^{10}-1=29999999999=2113 \cdot3767 \cdot3769 - нет
[math]3 \cdot 10^{11}-1=299999999999=7 \cdot683 \cdot953 \cdot65843 - да ([math]b=a\cdot42857142857)
[math]3 \cdot 10^{12}-1=2999999999999=359 \cdot8356545961 - нет
и т.д.
Для [math]m=3 будет только [math]142857, [math]285714 и цепочки из этих чисел.

Следует из того, что [math]x_n=3\cdot10^n даёт остаток 1 при делении на 7, только если [math]n даёт остаток 5 при делении на 6.
[math]x_1=30 - остаток 2
[math]x_2=10x_1 - остаток 20 -> 6
[math]x_3=10x_2 - остаток 60 -> 4
[math]x_4=10x_3 - остаток 40 -> 5
[math]x_5=10x_4 - остаток 50 -> 1
[math]x_6=10x_5 - остаток 10 -> 3
[math]x_7=10x_6 - остаток 30 -> 2
и дальше по циклу с периодом 6.

[zykov]

Вывод:
при [math]m=1 мнимальное [math]n=1
при [math]m=3 мнимальное [math]n=6
при других [math]m решений нет

[Ian]

Я помнил, когда открывал тему, что в решении получалось и 28- значное число, так как сам его находил.
http://intelmath.narod.ru/rebus.html
Но там, оказывается, было немного другое условие.Извините, недоработал. Попробую обобщить задачу, чтоб она стала интереснее. И метод у меня другой, допускающий любые обобщения, в том числе и на эту http://intelmath.narod.ru/olymp1sol3.html задачу

[Ian]

Как верно заметил zykov, есть два конца. В посте 1 был задан левый циклический сдвиг, основная масса цифр перемещается на 1 позицию влево. Изучается вопрос, когда это преобразование числа равносильно умножению на [math]m. рассмотрим пример на умножение столбиком
[math]\begin{array}{ccccccc}
a_{1} & a_{n} & ... & a_{5} & a_{4} & a_{3} & a_{2}\\
& & & & & \times & m\\
b_{n} & b_{n-1} & ... & b_{4} & b_{3} & b_{2} & 0\\
a_{n} & a_{n-1} & ... & a_{4} & a_{3} & a_{2} & a_{1}
\end{array},здесь [math]b_i<m-цифры, переносимые в старший разряд, как младшеклассников учили. Тогда [math]a_2m+0=pb_2+a_1, где [math]p =10 -основание системы счисления.Это уравнение для первой колонки, с участием второй, а вообще [math]a_km+b_{k-1}=pb_k+a_{k-1}Получаем уравнение для всех левых сдвигов на 1, которые равносильны умножению на [math]m:
[math]-pb_k+ma_k=a_{k-1}-b_{k-1} или короче [math](b_k,a_k)=\pi_+(b_{k-1},a_{k-1}), где [math]0\leq a_k<p найдется однозначно, когда [math]m взаимно просто с [math]p
Теперь можно изучать все задачи о левом сдвиге сразу. Полное зацикливание, такое как на примере, возникает, когда [math]\pi_+(a_n,b_n)=(a_1,0), что значит [math]\pi_+^n(a_1,0)=(a_1,0)- n- кратное применение этого отображения приводит в ту же точку. [math]\pi_+ на множестве чисел [math]0,1,...pm-1 действует, при p,m взаимно простых, как перестановка.А перестановка разлагается в произведение независимых циклов, так вот длины тех циклов, в которых есть хоть одна пара, начинающаяся на 0, и есть искомые n. Но это я рассказал решение задачи, которая, как показал zykov, имеет почти все ответы тривиальные
А пусть тогда цифра с 1-го места слева переносится на второе справа, тогда циклический сдвиг влево происходит на множестве всех цифр, кроме последней, тогда то же уравнение действует только на этом множестве. Пример должен быть записан в таких обозначениях:
[math]\begin{array}{ccccccc}
a_{2} & a_{n} & ... & a_{5} & a_{4} & a_{3} & a_{1}\\
& & & & & \times & m\\
b_{n} & b_{n-1} & ... & b_{4} & b_{3} & b_{2} & 0\\
a_{n} & a_{n-1} & ... & a_{4} & a_{3} & a_{2} & a_{1}
\end{array}, а из первого уравнения [math]a_1m=a_1+pb_2, [math]m-1 должно быть делителем [math]p, при [math]p=10 [math]m=3,6. Значит, смотрим для [math](0,a_1)=m=3:(0,5),m=6:(0,2),(0,4),(0,6),(0,8)...,орбиты вторых пар [math](b_2,a_2),m=3:b_2=1,m=6:b_2=1,2,3,4 и встретятся ли в этих орбитах пары [math](0,a_2). Задача о правом сдвиге в след. посте, а то уже много

[Ian]

Правый сдвиг, общий метод решения задач из блога, на который была ссылка
[math]\begin{array}{ccccccc}
a_{n-1} & a_{n-2} & ... & a_{3} & a_{2} & a_{1} & a_{n}\\
& & & & & \times & m\\
b_{n-1} & b_{n-2} & ... & b_{3} & b_{2} & b_{1} & 0\\
a_{n} & a_{n-1} & ... & a_{4} & a_{3} & a_{2} & a_{1}
\end{array}
[math]ma_{n}=a_{1}+pb_{1}
[math]ma_{k-1}+b_{k-1}=a_{k}+pb_{k},\quad k=2,...,n-1
[math]ma_{n-1}+b_{n-1}=a_{n}
[math](a_{k},b_{k})=\pi_{-}(a_{k-1},b_{k-1})Это отображение уже взаимно-однозначно (является перестановкой) для всех m,p
[math]\pi_{-}^{n}(a_{n},0)=(a_{n},0)
Перестановка [math]\pi_- разлагается в произведение независимых циклов. Возможные n-это длины тех циклов, которые содержат элементы вида [math](0,a) Но можно рассматривать задачи о переносе не первого, а например второго знака вперед, анализируя ту же самую перестановку.