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

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

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

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

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

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

Не сложно показать, что цепочка: 89, 179, 359, 719, 1439, 2879, состоящая из 6-ти простых - это вторая в последовательности цепочка длиной больше 4-х простых в цепочках чисел Софи Жермен. Первая цепочка больше 4-х простых: 2, 5, 11, 23, 47.

Список цепочек чисел Софи Жермен из 4-х простых начинается так:

509, 1019, 2039, 4079
1229, 2459, 4919, 9839
1409, 2819, 5639, 11279
2699, 5399, 10799, 21599
3539, 7079, 14159, 28319
...

Следует уточнить, что последнее простое число в цепочках не является числом Cофи Жермен по определению.

Формула общего члена последовательности чисел Жермен

g_n = g_0 2^n + 2^ n - 1   где g_0 = (g_1 - 1)/2

vorvalm пишет:Формула общего члена последовательности чисел Жермен

g_n = g_0 2^n + 2^ n - 1   где g_0 = (g_1 - 1)/2

Sophie Germain prime (Wiki)

137211941292195 × 2¹⁷¹⁹⁶⁰ − 1
Разве это можно назвать числом! Ведь число  - это то, что можно перечислить.

Все дело в 2^n - 1

Число g_0 имеет минимальный нечетный простой делитель р
Если n = ф(p), то 2^ф(p) = 1 (mod p),
'это означает, что при  n-1 или ф(p)-2 цепочка обрывается,
кроме случаев, когда указанное сравнение имеет квадратичный вычет

Пример
g_1 = 41, g_0 = 20, p = 5

Длина цепочки :5 - 2 = 3 (41, 83, 167) обрывается на 335

Пример с квадратичным вычетом
g_1 = 29, g_0 = 14, p = 7

т.к. 2^6 = 2^3(mod 7), то длина цепочки не 7 - 2 = 5, а только 2

Предложенная формула дает максимально возможное число вычетов цепочки СЖ с учетом последнего простого числа. 
Эта цепочка может быть прервана "случайным" взаимно простым с р числом, но
затем будет продолжаться до числа, кратного р.  Пример

g_1 = 89, g_0 = 44, p = 11, n(max) = 11- 2 = 9, это

89, 179, 359, 719, 1439, 2879, 5759, 11519, 23039  (46079=11*443)

5759 = 13*443 (случайное число)

При достаточно больших цепочках СЖ возможно несколько  случайных разрывов.

Так что же получается, что я велосипед изобретал:
Удивительная функция

nooartur пишет:Так что же получается, что я велосипед изобретал:
Удивительная функция

Тема: "Удивительная функция" стала замусориваться оффтопиками, и я решил пока не отвечать, а потом закрутился и забыл.
Возобновим.

Если мы нашли g_0 = 704 , то надо определить его минимальный нечетный простой делитель.
В вашем случае это р = 11

vorvalm пишет:Если мы нашли g_0 = 704 , то надо определить его минимальный нечетный простой делитель.
В вашем случае это р = 11

Если правильно понимаю, то Ваш метод срабатывает для первых цепочек с продолжением? В любом случае это полезно.
Но p=11 и для цепочки из 6 чисел, и для цепочки из 4 чисел.
Посмотрим. Для цепочки 1229, 2459, 4919, 9839  p=307 - что с этим делать?

Ключевые слова: "нашли g_0" Это открытая задача для цепочек Каннингема. Добывают биткоин генерации таких цепочек для нужд криптографии. Есть упрощённый алгоритм (доказательство тоже есть). Нужна известная база данных всех известных простых чисел в непрерывающейся последовательности .

Для дальнейшего плодотворного исследования хотелось бы предложить некоторый фильтр. Цепочки Каннингема первого рода длиной 2 числа нас не интересуют, так как это просто числа Софи Жермен (туда же и цепочки второго рода отнесём). Цепочки из 3 чисел тоже мало интересны по причине их прерывания без последствий. Интересны цепочки больше или равно 4 чисел. На этом и предлагаю остановить внимание исследования.

Оказывается, что до сих пор не найден метод генерации 
чисел Каннингэма (википедия). А он лежит на поверхности. 
Из формулы  g _п  = 2ⁿ g₀ + 2ⁿ - 1
 видно, что все зависит от g ₀, которое должно удовлетворять
 следующим требованиям
1)     Число  g ₀  должно быть составным вида 5k – 1  (k = 1,2,3,…)
    Число  k  определяется сравнением  5k ≡ 1(mod p)  по заданному  p.
  Ранее было определено, что  р  минимальный нечетный простой делитель g₀.
 2)  Если g ₀.  оказалось простым  числом, то это означает, что это  вычет цепочки.
       Т.к.  g ₀ = Ар   то  число вычетов цепочки  Каннингэма   может быть
 N(g) ≤ p – 2.                        
3)      p = 3  и 7 не создают цепочек Канингэма, т.е. минимальным
надо считать р  = 11.
4)      Число 2^п – 1 может оказаться кратным  р при  n < ф(p), например,
      если  2ⁿ - 1  будет квадратичным вычетом.
пример, р = 7, g ₀ = 14, ф(р) = 6 ,тогда р⁶ – 1 ≡ p³ – 1 ≡ (mod 7).
5)      Среди вычетов цепочек, представляющих максимальное их число при
данном  g ₀, т.e. р – 2, могут оказаться не простые числа, но взаимно простые  с  g ₀.
Например, при р = 11, g ₀ = 44, N(g) = 9  будем иметь
 
89, 179, 359, 719, 1439, 2879, 5759, 11519, 23039, но
 
5759 = 13*443
 
При таких ограничениях весьма непросто отыскать нужное  g ₀,
поэтому неудивительно, что известные цепочки Каннингэма

имеют такие большие начальные числа Жермен

5k-1 - не пропустит цепочки из 4, 5, 6... чисел, а вот цепочки из 3-х чисел пропускает (но они нас пока мало интересуют, можно потом наверстать).
А вот следующие условия или пропускают цепочки (посмотрите на те первые, которые выписаны в этой теме), или приводят к тому, что мы не знаем из каких множителей состоит g_0 - а гадать - это не совсем короткий путь.

p/s Удалю Ваш пустой пост. Но скажите, почему Вы сами не удалили? Что-то не то в настройках форума?

На каком основании вы решили, что  числа типа 5к - 1 
не пропускают цепочки 4,5,6,...
При к = 9 получим g_0 =44, p = 11, N(g) = p - 2 = 9
(c пустым постом больше не повторится)

На основании доказательства. Посмотрите когда g_1 = 5к-1. А g_0 зависит (простыми выкладками) от g_1, следовательно тоже не пропускает цепочки.
Есть ещё много интересного. Откроем пару тем в продолжение этой темы.

Я, наверное, так плохо изложил свои мысли о числах Жермен.,
если вы не поняли мои  доводы.
Число 5k – 1 никакого отношения к  g₁  не имеет.
5k – 1 = g₀,  следовательно , g₁ = 2g₀ + 1 = 10k – 1.
Для  генерации чисел Каннингэма  не надо искать g₀ среди
простых чисел. Надо его самим  назначить с помощью числа  k.
по формуле g₀ = 5k – 1.
Вопрос в том, как найти нужное число  k ?
Здесь нам помогут сравнения. Известно, что g₀ , кратные 3 и 7
не дают чисел Каннгингэма, следовательно, надо исключить их
из списка нужных нам чисел  k.
5k ≡ 1(mod 3), k = 2 + 3m = 2, 5, 8, 11, 14…….
5k ≡ 1(mod 7), k = 3 + 7m = 3, 10, 17, 24,…….
Если их объединить, то получим список бесполезных  k.
2, 3, 5, 8, 10, 11, 14, 17, …….
Отсюда мы можем выделить  нужные нам  k::
4, 6, 7, 9, 12, 13, 15, 16,……..
Это все относится числам Жермен  типа 10х + 9, т.е.
с последней цифрой 9.

5k-1 перекрывает и 10x+9, и 10у-1, когда k чётное. Другими словами = не пропускает искомых чисел. Но и создаёт много лишних чисел. Когда мы отбросим лишние k, то это, конечно, поубавит работы. Но этого пока мало для решения проблемки. В ряду оставленных чисел (кандидатов на цепочки) будет в разы больше составных, или пар (которые просто образуют числа Жермен), или троек (которых, кстати, тоже не так уж и много с последней цифрой 9). Для примера выпишу здесь все тройки с окончанием на 9 и первым простым до 10000. И будет видно сколько же чисел приходится отбрасывать.
Вот посмотрите. До 10000: одна 5-ка, одна 6-ка и пять 4-к. И всё.

Вы совершенно правы. Мы ограничили  k  по g₀
      Среди выделенных нужных  k  остались ненужные по g₁ , т.е.
10k ≡ 1(mod 3), k = 1 + 3m = 1, 4, 7, 10, 13 ……
10k ≡ 1(mod 7), k = 5 + 7m = 5, 12, 19, 26, ….
Исключаем их из списка нужных k
6, 9, 12 , 15, 18, 21, 24, 27, 30, ……
И из этого списка надо исключить ненужные  k  по g₂ = 20k - 1
20k ≡ 1(mod 7), k = 6 + 7m = 6, 13, 20 , 27, 34, 41…..
Получим достаточно приличный список нужных  k

9,  15, 18, 21, 30, 36, 39, 42, 51…..…..

Все ваши числа Каннингэма являются огрызками полных
цепочек.
Под полными цепочками чисел Жермен надо понимать
число вычетов, когда N(g) = p - 2
Среди ваших чисел есть  р = 11, 13, 17, 19, 43, 59  т.е.
теоретически с такими  р  должно быть 9, 11. 15. 17, 41, 57
вычетов.

Это полный список цепочек до 10000 с последней цифрой числа 9. Без пропусков. Дорабатывайте теорию.