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

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

Перейти вниз

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

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

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

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

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

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

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

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

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

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


Последний раз редактировалось: Михаил (Пн Сен 24, 2012 11:07 pm), всего редактировалось 1 раз(а)
Михаил Полянский
Михаил Полянский
Модератор

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

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

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

Сообщение автор Михаил Полянский в Пн Сен 17, 2012 11:11 pm

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

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

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

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

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

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

Сообщение автор vorvalm в Вс Дек 09, 2018 3:00 pm

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

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

vorvalm

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

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

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

Сообщение автор vps137 в Чт Дек 13, 2018 4:45 pm

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

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

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

_________________
Felix qui potuit rerum cognoscere causas. /Вергилий/
Апейроника - наука будущего?

vps137
Модератор

Сообщения : 465
АКТИВНОСТЬ : 3756
РЕПУТАЦИЯ : 27
Дата регистрации : 2011-01-20
Откуда : Екатеринбург

http://vps137.narod.ru/phys/

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

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

Сообщение автор vorvalm в Вс Дек 16, 2018 12:32 pm

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

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

vorvalm

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

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

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

Сообщение автор vorvalm в Вс Дек 16, 2018 5:31 pm

Пример
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

vorvalm

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

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

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

Сообщение автор vorvalm в Вс Дек 16, 2018 8:55 pm

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

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 (случайное число)

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

vorvalm

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

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

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

Сообщение автор nooartur в Пн Дек 17, 2018 9:04 pm

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

Сообщения : 1078
АКТИВНОСТЬ : 2243
РЕПУТАЦИЯ : 29
Дата регистрации : 2017-07-12
Возраст : 49

http://academy.noo-ws.com

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

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

Сообщение автор Михаил Полянский в Сб Дек 22, 2018 9:39 pm

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

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

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

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

Сообщение автор Михаил Полянский в Вт Дек 25, 2018 7:55 am

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

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 (случайное число)

При достаточно больших цепочках СЖ возможно несколько  случайных разрывов.
Исправим незначительную ошибку 46079=11*59*71

Если серьёзно! То предложенная Вами формула – это формула Каннингема (Британский математик). Первые исследования цепочек он провёл на рубеже 20-го века. Вы пишете о цепочках первого рода (уточним, ведь есть и цепочки второго рода. Вот цитата из Википедии (в переводе с англ.):
«Цепочка Каннингема первого типа длины n - это последовательность простых чисел (p1, ..., pn), такая что pi+1 = 2pi+1 для всех 1 ≤ i < n (Следовательно, каждый член такой цепочки, кроме последнего, - простое число Софи Жермен, и каждый член, кроме первого, - надёжное простое).»

У меня есть придирка к этой цитате. Надо было написать: …и каждый член, кроме первого и последнего, – надёжное простое. Ну да ладно.

По делу вопрос.


Вот цепочка: 1409, 2819, 5639, 11279

g1=1409, g0=704, 704/2=352 – не простое.


Что делать в таком случае?
Михаил Полянский
Михаил Полянский
Модератор

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

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

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

Сообщение автор vorvalm в Пн Дек 31, 2018 5:50 pm

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

vorvalm

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

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

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

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

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

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



Последний раз редактировалось: Михаил Полянский (Чт Янв 03, 2019 9:36 am), всего редактировалось 1 раз(а)
Михаил Полянский
Михаил Полянский
Модератор

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

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

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

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

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

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

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

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

Сообщение автор vorvalm в Чт Янв 03, 2019 2:35 pm

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

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


Последний раз редактировалось: vorvalm (Чт Янв 03, 2019 2:56 pm), всего редактировалось 3 раз(а)

vorvalm

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

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

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

Сообщение автор Михаил Полянский в Чт Янв 03, 2019 5:28 pm

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

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

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

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

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

Сообщение автор vorvalm в Чт Янв 03, 2019 6:08 pm

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

vorvalm

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

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

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

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

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

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

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

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

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

Ещё 4 цепочки 1-го рода из 4-х чисел (пригодятся для упражнений).


4.5 ) 6449, 12899, 25799, 51599
4.6 ) 10589, 21179, 42359, 84719
4.7 ) 11909, 23819, 47639, 95279
4.8 ) 12119, 24239, 48479, 96959
Михаил Полянский
Михаил Полянский
Модератор

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

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

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

Сообщение автор vorvalm в Пт Янв 04, 2019 11:15 am

Я, наверное, так плохо изложил свои мысли о числах Жермен.,
если вы не поняли мои  доводы.
Число 5k – 1 никакого отношения к  g1  не имеет.
5k – 1 = g0,  следовательно , g1 = 2g0 + 1 = 10k – 1.
Для  генерации чисел Каннингэма  не надо искать g0 среди
простых чисел. Надо его самим  назначить с помощью числа  k.
по формуле g0 = 5k – 1.
Вопрос в том, как найти нужное число  k ?
Здесь нам помогут сравнения. Известно, что g0 , кратные 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.

vorvalm

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

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

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

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

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

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

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

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

Сообщение автор vorvalm в Пт Янв 04, 2019 10:11 pm

Вы совершенно правы. Мы ограничили  k  по g0
      Среди выделенных нужных  k  остались ненужные по g1 , т.е.
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  по g2 = 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…..…..

vorvalm

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

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

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

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

Первые 3-ки до 10000 с последней цифрой 9 (всего 6 штук):

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


Посчитайте по своим полезным k - сколько ненужных чисел в отброс ушло.
Так что просто прогрессия здесь не очень помогает. Как говорил Михалыч: "...простые числа не коммутативны."
Эйлер доказал, что последовательность простых чисел не поддаётся линейному представлению.
Михаил Полянский
Михаил Полянский
Модератор

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

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

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

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

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

vorvalm

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

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

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

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

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

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

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

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

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


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


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

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

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


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