Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 08.05.2013, 13:18
Новичок

Отправить личное сообщение для malira Посмотреть профиль Найти все сообщения от malira
 
Регистрация: 02.09.2010
Сообщений: 12

Изоморфные цепи чисел
Есть алгоритм, порождающий замкнутую последовательность (цепь) целых положительных чисел:
m1=2*m0 mod N1
m2=2*m1 mod N1
...
m0-нечетное, N1=N-1, N-в общем случае четное, но можно ограничиться N=2^n

Например, при m0=5 и N=32 имеем цепь 5-10-20-9-18
Аналогичную цепь (с циклическим сдвигом) дает и m0=9.

Проблема: Как найти всевозможные m0<N, порождающие такие изоморфные цепи?
Какой раздел математики рассматривает такие задачи - теория чисел, теория групп?
  #2  
Старый 09.05.2013, 10:27
Пользователь

Отправить личное сообщение для maxal Посмотреть профиль Найти все сообщения от maxal
 
Регистрация: 28.11.2006
Сообщений: 68

Непонятно, что дано и что надо найти. Покажите, какого ответа вы ждете на примере N1=31.

Чем не устраивает прямолинейный алгоритм построения цепей умножением на 2 по модулю N1?

А вообще два числа a и b принадлежат одной цепи если число a/b является степенью 2-ки по модулю N1.
  #3  
Старый 10.05.2013, 12:25
Новичок

Отправить личное сообщение для malira Посмотреть профиль Найти все сообщения от malira
 
Регистрация: 02.09.2010
Сообщений: 12

С праздником Победы Вас, maxal!

В задаче нужен способ быстрого определения, что для конкретного m0 при последовательном просмотре цепочек при m0=1,3,5,7,9,... уже встречалась циклически сдвинутая цепь с такой же последовательностью чисел.

Например, в приведенном примере для m0=5 цепь следует "принять", а при m0=9 цепь следует отбросить, так как она уже встречалась при m0=5. Для N1=31 аналогичную пару цепей получаем для m0=11 (принять) и m0=13 (отбросить).

Наивное решение - перебор всех чисел цепочки и поиск mi<m0. Если такое mi в цепи встречается, то цепь следует отбросить. Есть способ ускореного просмотра чисел цепи (основан на том, что ситуация с mi<m0 может возникнуть только перехода 2*m(i-1) через N1.

С этой же задачей связан и предшествующий мой вопрос "Диафантово уравнение".

Интересуют также любые факты (теоремы), связанные с задачей, и разделы теории, близкие к задаче.
  #4  
Старый 11.05.2013, 07:02
Пользователь

Отправить личное сообщение для maxal Посмотреть профиль Найти все сообщения от maxal
 
Регистрация: 28.11.2006
Сообщений: 68

Для случая, когда N1 является простым, можно поступить так:

пусть r - первообразный корень по модулю N1, и число k - таково, что r^k == 2 (mod N1). Пусть g = НОД(k,N1-1). Тогда:
количество различный цепей равно g, и числа r^0, r^1, ..., r^(g-1) по модулю N1 суть представители различных цепей.

Например, для N1 = 31 можно взять r = 3, для которого k = 24 и соответственно g = НОД(24,31-1) = 6. Таким образом, у нас 6 различных цепей и их представителями являются:
1, 3, 9, 27, 19, 26
Можно выписать и сами цепи (начиная с каждого из представителей):
[1, 2, 4, 8, 16]
[3, 6, 12, 24]
[9, 18, 5, 10, 20]
[27, 23, 15, 30, 29]
[19, 7, 14, 28, 25]
[26, 21, 11, 22, 13]
  #5  
Старый 12.05.2013, 11:12
Новичок

Отправить личное сообщение для malira Посмотреть профиль Найти все сообщения от malira
 
Регистрация: 02.09.2010
Сообщений: 12

Блестяще!

Откуда следуют сделанные выводы? Как Вы к ним пришли?
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Раскраска чисел lazychaser Математические алгоритмы (другое) 17 30.11.2010 12:50
Умножения знаковых чисел гость Математические алгоритмы (другое) 8 17.11.2009 03:14
Теория чисел ugolishka Задачи 1 22.02.2009 05:04
Хеширование 5 чисел гость Математические алгоритмы (другое) 4 22.08.2007 09:21
генератор чисел AndriyOs Реализация, исходники, языки 0 05.12.2006 20:11