Цепочки простых чисел Софи Жермен

Страница 2 из 10 Предыдущий  1, 2, 3, 4, 5, 6, 7, 8, 9, 10  Следующий

Перейти вниз

Цепочки простых чисел Софи Жермен - Страница 2 Empty Цепочки простых чисел Софи Жермен

Сообщение автор Михаил Полянский в Вс Сен 16, 2012 5:43 pm

Первое сообщение в теме :

Продолжим решение задачи, сформулированной Михалычем:
Я однажды при решении одной (кстати, вполне практической задачи) столкнулся с забавной ситуацией.
Рассмотрим последовательность
x(n+1) = 2x(n)+1.
Пусть
х(1) = 2 - простое
х(2) = 5 - простое
х(3) = 11 - простое
х(4) = 23 - простое
х(5) = 47 - простое

Но х(6) = 95 - составное.
"Цепочки Софи Жермен" :))

Я не знаю, есть ли цепочки бОльшей длины (не пытался доказывать)
И не знаю, как часто такие цепочки встречаются.
Удачи!
Первые наброски решения можно почитать далее по постам в той теме.
Михаил Полянский
Михаил Полянский
Модератор

Сообщения : 3764
АКТИВНОСТЬ : 9587
РЕПУТАЦИЯ : 30
Дата регистрации : 2009-09-16
Возраст : 57
Откуда : Москва

Вернуться к началу Перейти вниз


Цепочки простых чисел Софи Жермен - Страница 2 Empty Re: Цепочки простых чисел Софи Жермен

Сообщение автор vorvalm в Сб Янв 05, 2019 6:35 pm

Теория  заключается  вот  в  чем.
Рассмотрим формулу общего члена цепочки Каннингэма
 
       .gn  = 2ng0 + 2n  - 1
 
.т.к.  g0 = Kp  (р минимальное нечетное простое число.), то
приняв  n = ф(p), получим
 
gn = 2nKp + 2ф(p) – 1 = p ( 2nK +  m),   т.е.  gn  уже не простое число.
 
Но мы выбрали  n = ф(p), (функция Эйлера по модулю  р)
,следовательно число  членов цепочки не может быть больше ф(р) -1
Члены цепочки должны быть простыми, т.е. взаимно простыми
с модулем  р, или иначе. вычетами ПСВ (приведенная система  вычетов)
по модулю  р. Но,  т.к. число членов цепочки подсчитывается попарно, то
последний член не имеет пару  и их не может быть больше  р – 2
Практика показывает, что полное число вычетов цепочки практически
недостижимо, т.к.они прерывается раньше случайными составными
взаимно простыми с модулем числами.
Единственные примеры полных цепочек  мы можем наблюдать
при  р = 7

vorvalm

Сообщения : 158
АКТИВНОСТЬ : 434
РЕПУТАЦИЯ : 11
Дата регистрации : 2018-09-23

Вернуться к началу Перейти вниз

Цепочки простых чисел Софи Жермен - Страница 2 Empty Re: Цепочки простых чисел Софи Жермен

Сообщение автор Михаил Полянский в Сб Янв 05, 2019 6:57 pm

Всё это так. Если не задать себе вопрос: почему тогда включают такие серьёзные вычислительные мощности для нахождения цепочек, если было бы так просто? Функция Эйлера конечно упрощает задачу, но не настолько, чтобы предсказать точно первое простое число цепочки. Это должно быть понятно ещё хотя бы потому, что если бы была возможность предсказать простое число, то ни цепочек, ни чисел Мерсенна, ни других открытых задач нам бы уже не надо было. Мы каждый раз в этих задачах натыкаемся на два недоразумения: первое - работает, но не для всех чисел; второе - пропускает числа.
Михаил Полянский
Михаил Полянский
Модератор

Сообщения : 3764
АКТИВНОСТЬ : 9587
РЕПУТАЦИЯ : 30
Дата регистрации : 2009-09-16
Возраст : 57
Откуда : Москва

Вернуться к началу Перейти вниз

Цепочки простых чисел Софи Жермен - Страница 2 Empty Re: Цепочки простых чисел Софи Жермен

Сообщение автор Михаил Полянский в Сб Янв 05, 2019 8:01 pm

Работаю с помощью усовершенствованного решета Аткина (УРА).
На мой не проверенный взгляд - этот путь будет покороче.
Выпишу вам все остальные цепочки Каннингема первого рода с первым простым до 10000 (для осмысления). Работайте тоже.
Михаил Полянский
Михаил Полянский
Модератор

Сообщения : 3764
АКТИВНОСТЬ : 9587
РЕПУТАЦИЯ : 30
Дата регистрации : 2009-09-16
Возраст : 57
Откуда : Москва

Вернуться к началу Перейти вниз

Цепочки простых чисел Софи Жермен - Страница 2 Empty Re: Цепочки простых чисел Софи Жермен

Сообщение автор vorvalm в Сб Янв 05, 2019 8:22 pm

Определение первого простого числа цепочек Каннингэма является
просто удачей, но мы можем значительно снизить число претендентов
То, что мы пытались с помощью  k  ограничить границы поиска
первых чисел цепочек оказалось тупиковым. Назовем его «метод k»
Но есть еще вариант метода генерации первых членов цепочек,
                         используя  опыт «метода k».
Для этого в формуле  g0 изменим коэффициент при k  и примем
 
           g0 = Kp =  15k – 1 

Этим мы исключаем  р = 3  из числа делителей  g0   Рассмотрим сравнение

15k ≡ 1(mod p)
 
и будем находить k  при различных  р, начиная с  р = 11.
Пример
15k ≡ 1(mod 11),  к = 3 + 11m = 3, 14, 25, 36, 47, ……
Берем  k = 3,  g0 = 45 – 1 = 44,  .g1 = 88 + 1 = 89
Мы получили известную цепочку.

vorvalm

Сообщения : 158
АКТИВНОСТЬ : 434
РЕПУТАЦИЯ : 11
Дата регистрации : 2018-09-23

Вернуться к началу Перейти вниз

Цепочки простых чисел Софи Жермен - Страница 2 Empty Re: Цепочки простых чисел Софи Жермен

Сообщение автор Михаил Полянский в Сб Янв 05, 2019 9:12 pm

@vorvalm пишет:Определение первого простого числа цепочек Каннингэма является
просто удачей, но мы можем значительно снизить число претендентов
То, что мы пытались с помощью  k  ограничить границы поиска
первых чисел цепочек оказалось тупиковым. Назовем его «метод k»
Но есть еще вариант метода генерации первых членов цепочек,
                         используя  опыт «метода k».
Вы совершенно правильно вычислили, что через k - тупик.

По поводу прогрессий 15k+х есть более совершенный метод (покрывает без излишеств все простые и цепочки, и...).

15k+/- 2^i. где i=1,2,3,4. - это центральная (от ядра) запись УРА.
Михаил Полянский
Михаил Полянский
Модератор

Сообщения : 3764
АКТИВНОСТЬ : 9587
РЕПУТАЦИЯ : 30
Дата регистрации : 2009-09-16
Возраст : 57
Откуда : Москва

Вернуться к началу Перейти вниз

Цепочки простых чисел Софи Жермен - Страница 2 Empty Re: Цепочки простых чисел Софи Жермен

Сообщение автор vorvalm в Сб Янв 05, 2019 9:33 pm

Пример 2.  р = 11., N(g) = 11 – 2 = 9
Берем  k = 47,  g0 = 705 -1 = 704,  g1 = 1409
Это одна из ваших цепочек, но она имеет продолжение.
1409, 2819, 5639, 11279, 22559,,45119, 90239, 180479, 90239.
Здесь мы имеем два случайных числа  22559 и 180479

vorvalm

Сообщения : 158
АКТИВНОСТЬ : 434
РЕПУТАЦИЯ : 11
Дата регистрации : 2018-09-23

Вернуться к началу Перейти вниз

Цепочки простых чисел Софи Жермен - Страница 2 Empty Re: Цепочки простых чисел Софи Жермен

Сообщение автор Михаил Полянский в Сб Янв 05, 2019 9:35 pm

Например, цепочки Каннингема 1-го рода длиной 4, 5, 6 чисел располагаются в прогрессии 15k-2^4.
цепочки Каннингема 2-го рода длиной 4, 5, 6 чисел располагаются в прогрессии 15k+2^4.
Цепочки 1-го рода и 2-го рода длиной 3 числа из других прогрессий типа 15k+/-2^i (длинней там не будет по определению УРА) выпишу до 10000.
Михаил Полянский
Михаил Полянский
Модератор

Сообщения : 3764
АКТИВНОСТЬ : 9587
РЕПУТАЦИЯ : 30
Дата регистрации : 2009-09-16
Возраст : 57
Откуда : Москва

Вернуться к началу Перейти вниз

Цепочки простых чисел Софи Жермен - Страница 2 Empty Re: Цепочки простых чисел Софи Жермен

Сообщение автор vorvalm в Сб Янв 05, 2019 9:40 pm

Что такое УРА ?

vorvalm

Сообщения : 158
АКТИВНОСТЬ : 434
РЕПУТАЦИЯ : 11
Дата регистрации : 2018-09-23

Вернуться к началу Перейти вниз

Цепочки простых чисел Софи Жермен - Страница 2 Empty Re: Цепочки простых чисел Софи Жермен

Сообщение автор Михаил Полянский в Сб Янв 05, 2019 9:40 pm

@vorvalm пишет:Пример 2.  р = 11., N(g) = 11 – 2 = 9
Берем  k = 47,  g0 = 705 -1 = 704,  g1 = 1409
Это одна из ваших цепочек, но она имеет продолжение.
1409, 2819, 5639, 11279, 22559,,45119, 90239, 180479, 90239.
Здесь мы имеем два случайных числа  22559 и 180479
Всё так. Ваш метод беспрекословно полезен. Пусть этот метод цепляет продолжением числа Жермен - укорачивает алгоритм поиска. Почувствовал, что если сложить наши изыскания воедино, то может получиться много полезного.
Михаил Полянский
Михаил Полянский
Модератор

Сообщения : 3764
АКТИВНОСТЬ : 9587
РЕПУТАЦИЯ : 30
Дата регистрации : 2009-09-16
Возраст : 57
Откуда : Москва

Вернуться к началу Перейти вниз

Цепочки простых чисел Софи Жермен - Страница 2 Empty Re: Цепочки простых чисел Софи Жермен

Сообщение автор Михаил Полянский в Сб Янв 05, 2019 9:42 pm

@vorvalm пишет:Что такое УРА ?
Читайте, пожалуйста, все мои посты. Выше расшифровал: усовершенствованное решето Аткина (УРА).
Михаил Полянский
Михаил Полянский
Модератор

Сообщения : 3764
АКТИВНОСТЬ : 9587
РЕПУТАЦИЯ : 30
Дата регистрации : 2009-09-16
Возраст : 57
Откуда : Москва

Вернуться к началу Перейти вниз

Цепочки простых чисел Софи Жермен - Страница 2 Empty Re: Цепочки простых чисел Софи Жермен

Сообщение автор vorvalm в Сб Янв 05, 2019 9:53 pm

Это ни о чем не говорит

vorvalm

Сообщения : 158
АКТИВНОСТЬ : 434
РЕПУТАЦИЯ : 11
Дата регистрации : 2018-09-23

Вернуться к началу Перейти вниз

Цепочки простых чисел Софи Жермен - Страница 2 Empty Re: Цепочки простых чисел Софи Жермен

Сообщение автор Михаил Полянский в Сб Янв 05, 2019 10:00 pm

Ещё как говорит, когда с помощью УРА я Вас буду опережать на 5 шагов вперёд - обещаю!
Михаил Полянский
Михаил Полянский
Модератор

Сообщения : 3764
АКТИВНОСТЬ : 9587
РЕПУТАЦИЯ : 30
Дата регистрации : 2009-09-16
Возраст : 57
Откуда : Москва

Вернуться к началу Перейти вниз

Цепочки простых чисел Софи Жермен - Страница 2 Empty Re: Цепочки простых чисел Софи Жермен

Сообщение автор vorvalm в Сб Янв 05, 2019 10:12 pm

Приведите пример решения цепочек с помощью ваших прогрессий
 
15к -24


Мне кажется, что соревнования здесь неуместны

vorvalm

Сообщения : 158
АКТИВНОСТЬ : 434
РЕПУТАЦИЯ : 11
Дата регистрации : 2018-09-23

Вернуться к началу Перейти вниз

Цепочки простых чисел Софи Жермен - Страница 2 Empty Re: Цепочки простых чисел Софи Жермен

Сообщение автор Михаил Полянский в Сб Янв 05, 2019 10:25 pm

@vorvalm пишет:1409, 2819, 5639, 11279, 22559,,45119, 90239, 180479, 90239.
Здесь мы имеем два случайных числа  22559 и 180479
Да нет уж. Просто цепочка прервалась... и повезло, что в продолжении через случайное число встретилось число Жермен, а затем через случайное число встретилось одно простое число. А далее  13*13883 (как бы случайное), 360959 (простое),11*65629 (опять случайное), 1443839, (простое число), 61*47339 (ещё случайное)... мне дальше неохота, где цепочки?
Михаил Полянский
Михаил Полянский
Модератор

Сообщения : 3764
АКТИВНОСТЬ : 9587
РЕПУТАЦИЯ : 30
Дата регистрации : 2009-09-16
Возраст : 57
Откуда : Москва

Вернуться к началу Перейти вниз

Цепочки простых чисел Софи Жермен - Страница 2 Empty Re: Цепочки простых чисел Софи Жермен

Сообщение автор Михаил Полянский в Сб Янв 05, 2019 10:30 pm

@vorvalm пишет:Приведите пример решения цепочек с помощью ваших прогрессий
 
15к -24


Мне кажется, что соревнования здесь неуместны
Все цепочки Каннингема 1-го рода, где первое простое число до 10000 заканчивается цифрой 9:

6.1) 89, 179, 359, 719, 1439, 4079

4.1) 509, 1019, 2039, 4079
4.2) 1129, 2459, 4919, 9839
4.3) 1409, 2819, 5639, 11279
4.4) 2699,
5399, 10799, 21599
4.5) 3539, 7079, 14159, 28319
4.6) 6449, 12899, 25799, 51599


3.1.9) 1889, 3779, 7559
3.2.9) 3449, 6899, 13799
3.3.9) 5849, 11699, 23399
3.4.9) 7349, 14699, 29399
3.5.9) 8969, 17939, 35879



Соревнование и не нужно. Нужна работа.


Последний раз редактировалось: Михаил Полянский (Вс Янв 06, 2019 1:46 pm), всего редактировалось 2 раз(а)
Михаил Полянский
Михаил Полянский
Модератор

Сообщения : 3764
АКТИВНОСТЬ : 9587
РЕПУТАЦИЯ : 30
Дата регистрации : 2009-09-16
Возраст : 57
Откуда : Москва

Вернуться к началу Перейти вниз

Цепочки простых чисел Софи Жермен - Страница 2 Empty Re: Цепочки простых чисел Софи Жермен

Сообщение автор Михаил Полянский в Сб Янв 05, 2019 10:35 pm

Извините, не написал: k=2n+1, n=1,2,3...


Последний раз редактировалось: Михаил Полянский (Вс Янв 06, 2019 2:25 am), всего редактировалось 1 раз(а)
Михаил Полянский
Михаил Полянский
Модератор

Сообщения : 3764
АКТИВНОСТЬ : 9587
РЕПУТАЦИЯ : 30
Дата регистрации : 2009-09-16
Возраст : 57
Откуда : Москва

Вернуться к началу Перейти вниз

Цепочки простых чисел Софи Жермен - Страница 2 Empty Re: Цепочки простых чисел Софи Жермен

Сообщение автор vorvalm в Сб Янв 05, 2019 10:50 pm

Извиняюсь, но это туфта. 
В любом случае пример при доказательстве необходим.

vorvalm

Сообщения : 158
АКТИВНОСТЬ : 434
РЕПУТАЦИЯ : 11
Дата регистрации : 2018-09-23

Вернуться к началу Перейти вниз

Цепочки простых чисел Софи Жермен - Страница 2 Empty Re: Цепочки простых чисел Софи Жермен

Сообщение автор vorvalm в Вс Янв 06, 2019 9:08 am

@Михаил Полянский пишет:
@vorvalm пишет:Пример 2.  р = 11., N(g) = 11 – 2 = 9
Берем  k = 47,  g0 = 705 -1 = 704,  g1 = 1409
Это одна из ваших цепочек, но она имеет продолжение.
1409, 2819, 5639, 11279, 22559,,45119, 90239, 180479, 360959.
Здесь мы имеем два случайных числа  22559 и 180479
Всё так. Ваш метод беспрекословно полезен. Пусть этот метод цепляет продолжением числа Жермен - укорачивает алгоритм поиска. Почувствовал, что если сложить наши изыскания воедино, то может получиться много полезного.
В цепочке Каннингэма допущена ошибка. Эту строчку надо читать так.
(g_0=704= 11*64),1409,2819,5639,11279,22559,45119,90239,180479,360959,(721919=11*65629)
Очевидно, что цепочка начинается с числа кратного 11 и заканчивается числом кратным 11.
Число вычетов цепочки N(п) = 11 - 2 = 9
Обращаю внимание.N(g) - число вычетов цепочки по модулю р но не простых чисел Каннингэма


Последний раз редактировалось: vorvalm (Вс Янв 06, 2019 2:57 pm), всего редактировалось 1 раз(а)

vorvalm

Сообщения : 158
АКТИВНОСТЬ : 434
РЕПУТАЦИЯ : 11
Дата регистрации : 2018-09-23

Вернуться к началу Перейти вниз

Цепочки простых чисел Софи Жермен - Страница 2 Empty Re: Цепочки простых чисел Софи Жермен

Сообщение автор Михаил Полянский в Вс Янв 06, 2019 10:28 am

Завершение списка цепочек Каннингема 1-го рода, где первое простое число до 10000.

3.1.1)  1, 3, 7
3.2.1)  41, 83, 167
3.3.1)  1031, 2063, 4127
3.4.1)  1451, 2903, 5807
3.5.1)  1481, 2963, 5927
3.6.1)  1511, 3023, 6047
3.7.1)  1811, 3623, 7247
3.8.1)  1901, 3803, 7607
3.9.1)  1931, 3863, 7727
3.10.1) 3491, 6983, 13967
3.11.1) 3911, 7823, 15647
3.12.1) 5081, 10163, 20327
3.13.1) 6101, 12203, 24407
3.14.1) 6131, 12263, 24527
3.15.1) 7151, 14303, 28607
3.16.1) 7901, 15803, 31607
3.17.1) 9221, 18443, 36887

Все выписанные в этой теме цепочки - без пропусков = полный список.
Михаил Полянский
Михаил Полянский
Модератор

Сообщения : 3764
АКТИВНОСТЬ : 9587
РЕПУТАЦИЯ : 30
Дата регистрации : 2009-09-16
Возраст : 57
Откуда : Москва

Вернуться к началу Перейти вниз

Цепочки простых чисел Софи Жермен - Страница 2 Empty Re: Цепочки простых чисел Софи Жермен

Сообщение автор vorvalm в Вс Янв 06, 2019 12:27 pm

У вас 5399 отнесено к тройкам, но является вычетом
четверки 2699.5399......

vorvalm

Сообщения : 158
АКТИВНОСТЬ : 434
РЕПУТАЦИЯ : 11
Дата регистрации : 2018-09-23

Вернуться к началу Перейти вниз

Цепочки простых чисел Софи Жермен - Страница 2 Empty Re: Цепочки простых чисел Софи Жермен

Сообщение автор vorvalm в Вс Янв 06, 2019 1:08 pm

Пример 3. р = 127. N(g) = 127- 1 = 126
                        15k ≡ 1 (mod 127), k = 17 + 127m = 17, 144, 271, 398,……

Берем  k = 17,  g0 = 15*17 -1 = 254, g1 = 254*2 +1 = 509

vorvalm

Сообщения : 158
АКТИВНОСТЬ : 434
РЕПУТАЦИЯ : 11
Дата регистрации : 2018-09-23

Вернуться к началу Перейти вниз

Цепочки простых чисел Софи Жермен - Страница 2 Empty Re: Цепочки простых чисел Софи Жермен

Сообщение автор Михаил Полянский в Вс Янв 06, 2019 1:42 pm

@vorvalm пишет:У вас 5399 отнесено к тройкам, но является вычетом
четверки 2699.5399......
Да, верно. Пропустил, отредактирую посты, где четвёрки и тройки.
Спасибо.
Михаил Полянский
Михаил Полянский
Модератор

Сообщения : 3764
АКТИВНОСТЬ : 9587
РЕПУТАЦИЯ : 30
Дата регистрации : 2009-09-16
Возраст : 57
Откуда : Москва

Вернуться к началу Перейти вниз

Цепочки простых чисел Софи Жермен - Страница 2 Empty Re: Цепочки простых чисел Софи Жермен

Сообщение автор Михаил Полянский в Вс Янв 06, 2019 10:00 pm

Доказательство с помощью УРА для цепочек 1-го рода.
Решето УРА:
30k+(1,7,11,13,17,19,23,29)
1) 30k+1 - нет цепочек и чисел С.Ж.
2) 30k+7 - нет цепочек и чисел С.Ж.
3) 30k+11 - есть числа С.Ж и цепочки длиной до 3-х чисел.
4) 30k+13 - нет цепочек и чисел С.Ж.
5) 30k+17 - нет цепочек и чисел С.Ж.
6) 30k+19 - нет цепочек и чисел С.Ж.
7) 30k+23 - есть числа С.Ж и цепочки длиной до 2-х чисел.
8 )30k+29 - есть числа С.Ж и цепочки любой длины.
Михаил Полянский
Михаил Полянский
Модератор

Сообщения : 3764
АКТИВНОСТЬ : 9587
РЕПУТАЦИЯ : 30
Дата регистрации : 2009-09-16
Возраст : 57
Откуда : Москва

Вернуться к началу Перейти вниз

Цепочки простых чисел Софи Жермен - Страница 2 Empty Re: Цепочки простых чисел Софи Жермен

Сообщение автор vorvalm в Вс Янв 06, 2019 11:14 pm

Откуда взялись числа (1, 7, 11, 13, 17, 19, 23, 29)

vorvalm

Сообщения : 158
АКТИВНОСТЬ : 434
РЕПУТАЦИЯ : 11
Дата регистрации : 2018-09-23

Вернуться к началу Перейти вниз

Цепочки простых чисел Софи Жермен - Страница 2 Empty Re: Цепочки простых чисел Софи Жермен

Сообщение автор Михаил Полянский в Пн Янв 07, 2019 3:56 am

@vorvalm пишет:Откуда взялись числа (1, 7, 11, 13, 17, 19, 23, 29)
Из решета Аткина. В некотором роде - это мой инструмент, с помощью которого давно работаю, что видно по некоторым темам. Например, "Признаки делимости". По крайней мере удаётся избежать многих ненужных чисел. А за счёт внутренней симметрии такого решета можно сокращать алгоритмы ещё в разы. Например, легко показать, что не факторизованное число RSA 232 (которое пока не поддаётся известным методам факторизации и мощностям современных вычислительных средств даже с помощью распределённых вычислений) принадлежит прогрессии 30k+19, где k - чётное (и имеет 6 вариантов, какие могут быть множители вида 30k+а). Если бы математики знали про моё решето, то упростили бы алгоритмы в разы. Но мы пока не будем подсказывать людям, которые борются за 100000 долларов (пусть помучаются).
Михаил Полянский
Михаил Полянский
Модератор

Сообщения : 3764
АКТИВНОСТЬ : 9587
РЕПУТАЦИЯ : 30
Дата регистрации : 2009-09-16
Возраст : 57
Откуда : Москва

Вернуться к началу Перейти вниз

Цепочки простых чисел Софи Жермен - Страница 2 Empty Re: Цепочки простых чисел Софи Жермен

Сообщение автор Спонсируемый контент


Спонсируемый контент


Вернуться к началу Перейти вниз

Страница 2 из 10 Предыдущий  1, 2, 3, 4, 5, 6, 7, 8, 9, 10  Следующий

Вернуться к началу


 
Права доступа к этому форуму:
Вы не можете отвечать на сообщения