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

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

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

Продолжим решение задачи, сформулированной Михалычем:

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

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

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

Первые наброски решения можно почитать далее по постам в той теме.

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

Теория заключается вот в чем.
Рассмотрим формулу общего члена цепочки Каннингэма

.g_n = 2ⁿg₀ + 2ⁿ - 1

.т.к. g₀ = Kp (р минимальное нечетное простое число.), то
приняв n = ф(p), получим

g_n = 2ⁿKp + 2^ф^(p) – 1 = p ( 2ⁿK + m), т.е. g_n уже не простое число.

Но мы выбрали n = ф(p), (функция Эйлера по модулю р)
,следовательно число членов цепочки не может быть больше ф(р) -1
Члены цепочки должны быть простыми, т.е. взаимно простыми
с модулем р, или иначе. вычетами ПСВ (приведенная система вычетов)
по модулю р. Но, т.к. число членов цепочки подсчитывается попарно, то
последний член не имеет пару и их не может быть больше р – 2
Практика показывает, что полное число вычетов цепочки практически
недостижимо, т.к.они прерывается раньше случайными составными
взаимно простыми с модулем числами.
Единственные примеры полных цепочек мы можем наблюдать
при р = 7

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

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

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

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

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

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

g₀ = Kp = 15k – 1

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

15k ≡ 1(mod p)

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

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

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

Вы совершенно правильно вычислили, что через k - тупик.

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

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

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

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

автор Михаил Полянский Сб Янв 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.

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

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

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

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

Всё так. Ваш метод беспрекословно полезен. Пусть этот метод цепляет продолжением числа Жермен - укорачивает алгоритм поиска. Почувствовал, что если сложить наши изыскания воедино, то может получиться много полезного.

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

vorvalm пишет:Что такое УРА ?

Читайте, пожалуйста, все мои посты. Выше расшифровал: усовершенствованное решето Аткина (УРА).

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

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

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

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

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

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

15к -2⁴

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

автор Михаил Полянский Сб Янв 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 (ещё случайное)... мне дальше неохота, где цепочки?

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

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

15к -2⁴

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

Все цепочки Каннингема 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

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

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

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

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

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

автор vorvalm Вс Янв 06, 2019 9:08 am

Михаил Полянский пишет:
vorvalm пишет:Пример 2. р = 11., N(g) = 11 – 2 = 9
Берем k = 47, g₀ = 705 -1 = 704, g₁ = 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) - число вычетов цепочки по модулю р но не простых чисел Каннингэма

автор Михаил Полянский Вс Янв 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

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

автор vorvalm Вс Янв 06, 2019 12:27 pm

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

автор 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, g₀ = 15*17 -1 = 254, g₁ = 254*2 +1 = 509

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

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

Да, верно. Пропустил, отредактирую посты, где четвёрки и тройки.
Спасибо.

автор Михаил Полянский Вс Янв 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 - есть числа С.Ж и цепочки любой длины.

автор vorvalm Вс Янв 06, 2019 11:14 pm

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

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

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

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

''ЕСЛИ ТЕОРЕМЫ МАТЕМАТИКИ ПРИЛАГАЮТСЯ К ОТРАЖЕНИЮ РЕАЛЬНОГО МИРА, ОНИ НЕ ТОЧНЫ; ОНИ ТОЧНЫ ДО ТЕХ ПОР, ПОКА ОНИ НЕ ССЫЛАЮТСЯ НА ДЕЙСТВИТЕЛЬНОСТЬ'' - Albert Einstein

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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