Более широкий взгляд на числа Мерсенна

[Ascar]

Если $m$ делится на $p$ нацело, то $n=(2^t+1)/(2^p+1)$

Но нас конечно же интересует вариант когда $m$ не делится на $p$ нацело :) что представляет из себя $n$ в этом случае?

-- Сб янв 22, 2011 18:48:29 --

рассмотрим первое составное число вида $(2^x+1)/3$

это $(2^{29}+1)/3=178956971=59*3033169$

число $178956971$ принадлежит нашей последовательности где $m=28$ и $p=1$ ($t=29$)

делитель этого числа $3033169$ также принадлежит нашей последовательности, где $m=22$ и $p=7$ ($t=29$)

[Ascar]

если $m$ четное и $p=m-2$, то $n=(2^{t}+1)/(2^{p+1}-2^{m/2}+1)$

-- Вс янв 23, 2011 19:00:36 --

для любого набора $m$ и $p$ будет верным представление значения $n$ в виде

$n=(2^t+1)/(2^p+x)$

где значение $x$ зависит по некоторому правилу от значения $m$ и $p$, надеюсь это правило выражается (вычисляется) ТОЛЬКО по этим двум значениям, сильно надеюсь :) было бы неплохо

[Sonic86]

Sonic86 писал(а):

Остается случай $a=\frac{2t}{3}$, на котором я пока застрял, но видимо, уже нужно контрпример искать среди чисел $n:n \equiv 2 \pmod 3$ (еще подумаю...)

Если $a=\frac{2t}{3}$, то $\frac{a}{2}=\frac{t}{3}$, значит $-1 \equiv 2^{\frac{a}{2}} \equiv 2^{\frac{t}{3}} \pmod n$. Но $t \leq 2 \log _2(n)$, поэтому $2^{\frac{t}{3}} +1 \leq n^{\frac{2}{3}}+1 < n$, и значит сравнение $2^{\frac{t}{3}}+1 \pmod n$ невозможно.

Т.обр. $2t=2(m+p)$ - порядок числа $2$ по модулю $n$. Отсюда и из $2^{n-1} \equiv 1 \pmod n \Rightarrow 2t|n-1 \Leftrightarrow n \equiv 1 \pmod{2t}$ - свойство 1 я доказал и усилил даже.

Ascar! Я Вам советую переобзначить $t=2(m+p)$ и изучать его (например, перепроверить свойство 3 (усилить, получается))

Sonic86 писал(а):

а как Вы отсюда будете факторизовать эти числа? Если по свойству 2, то имейте ввиду, что $t \leq 2 \log _2(n)$ - это почти никакая информация о делителях...

Возможно, это я зря. Для числа Ферма Эйлер определил общий тип делителей именно с таким свойством. Так что нормально...

-- Вс янв 23, 2011 22:05:15 --

(Оффтоп)

последнюю инфу пока ниасилил. Позже...

-- Вс янв 23, 2011 22:10:38 --

(вот такая мысля...)

то есть Вам свойство $2^{n-m-1} \mod n = n-2^p$ позволяет найти порядок $a$ числа 2 по модулю $n$. Если свойство 2 верно, то порядок $a$ нам дает информацию о разложении $n$ на множители... Можно было бы раскладывать на множители число $n-1$ (а его чаще проще разложить, чем $n: 2^{n-1} \equiv 1 \pmod n$), найти порядок 2 простеньким перебором делителей и уже оттуда искать делители $n$. Кажись, это метод Полларда. Сейчас посмотрю...

[Ascar]

спасибо за доказательство 1-ого свойства, буду ссылаться :)
-----------

про то что написал выше, на всякий случай еще раз
для любого набора $m$ и $p$ будет верным представление значения $n$ в виде

$n=(2^t+1)/(2^p+x)$

где $x=f(m,p)$, я надеюсь что это так
я надеюсь что эта функция имеет ЕДИНСТВЕННОЕ значение

например
при $p=1$; $f(m,p)=1$
при $m$ четное и $p=m-2$; $f(m,p)=2^{p}-2^{m/2}+1$

пока буду искать эту функцию, методом тыка(сбора стат данных) :)

[Sonic86]

Ascar! Проверьте свойство 2:
$n=47349373= 29 \cdot 113 \cdot 14449$
$m=26, p=16, a=2t=84, t=42$, однако $42 \not | \ 29-1$

[Ascar]

Sonic86 в сообщении #403830 писал(а):

Ascar! Проверьте свойство 2:
$n=47349373= 29 \cdot 113 \cdot 14449$
$m=26, p=16, a=2t=84, t=42$, однако $42 \not | \ 29-1$

мы не говорим об единственности представления
я же написал что может быть (как один из вариантов) представленно....
47349373=29*113*14449

$29*113=78*42+1$
$14449=344*42+1$
$47349373=(78*42+1)*(344*42+1)$

-- Пн янв 24, 2011 18:51:43 --

первые составные вида (2^x+1)/3 где x - простое число

(2^29+1)/3=178956971=59*3033169
178956971 m=28 p=1 (t=29)
3033169 m=22 p=7 (t=29)

(2^37+1)/3=45812984491=1777*25781083
45812984491 m=36 p=1 (t=37)
25781083 m=25 p=12 (t=37)

(2^41+1)/3=733007751851 = 83*8831418697
733007751851 m=40 p=1 (t=41)
8831418697 m=34 p=7 (t=41)

(2^47+1)/3=46912496118443 = 283*165768537521
46912496118443 m=46 p=1 (t=47)
165768537521 m=38 p=9 (t=47)

(2^53+1)/3=3002399751580331 = 107*28059810762433
3002399751580331 m=52 p=1 (t=53)
28059810762433 m=45 p=8 (t=53)

(2^59+1)/3=192153584101141163 = 2833*37171*1824726041
192153584101141163 m=58 p=1 (t=59)
1824726041 m=31 p=28 (t=59)
и т.д.

лучше наидите котнр пример этому утверждению :)

-- Пн янв 24, 2011 18:59:54 --

Ascar в сообщении #403844 писал(а):

Sonic86 в сообщении #403830 писал(а):

Ascar! Проверьте свойство 2:
$n=47349373= 29 \cdot 113 \cdot 14449$
$m=26, p=16, a=2t=84, t=42$, однако $42 \not | \ 29-1$

мы не говорим об единственности представления
я же написал что может быть (как один из вариантов) представленно....
47349373=29*113*14449

$29*113=78*42+1$
$14449=344*42+1$
$47349373=(78*42+1)*(344*42+1)$

стоит заметить также что число 29*113=3277
3277 - также это элемент нашей последовательности с показателем степени t=14, общий делитель с 42 равен 7
ну вообщем природа у них общая... некая природа :)

[Sonic86]

Я тогда пока повременю с доказательством свойства 2 - оно выглядит очень вероятно, но доказать строго не получается. Даже идеи нету.
Я хочу заметить, что число $a=P_n(2)$ определяется так независимо от числа $p$, т.е. свойство 2 $(\exists d,q) n=dq, d,q \equiv 1 \pmod n$ можно пытаться доказывать (и опровергать), не только для чисел, определенных выше, но и для всех чисел, псевдопростых по модулю 2 (ну соответственно основание 2 можно попытаться заменить на 3,5 и т.д.)

Вопрос. Пусть $a,b$ удовлетворяют данным условиям 1 и 2. Тогда удовлетворяет ли им число $\omega (a \cdot b)$, где для $x=p_1^{a_1}...p_s^{a_s}$ $\omega(x)=p_1^{a_1 \mod 2}...p_s^{a_s \mod 2}$. Это вариант формализации вопроса:

Ascar писал(а):

интерес вызывают числа у которых p=1
тоесть $n=(2^{m+1}+1)/3$
если n - составное число то его больший делитель также принадлежит нашему ряду

[Ascar]

идея для своиства 2...
ну можно переформулировать

самый большой делитель числа $n$, являющийся простым числом имеет вид $(t*a+1)$, где $a$ целое число больше нуля

[Sonic86]

Ascar писал(а):

интерес вызывают числа у которых p=1
тоесть $n=(2^{m+1}+1)/3$
если n - составное число то его больший делитель также принадлежит нашему ряду
$m+1$ - простое либо псевдопростое будет решена

Я вот это что-то понять не могу - откуда это взялось: $n=(2^{m+1}+1)/3$

Ascar писал(а):

наити его методом тыка практически невозможно, но если кто то придумает как, то задачу факторизации чисел вида$ (2^{m+1}+1)/3$ где

Вообще, если $n=(2^{m+1}+1)/3$, то проблем с разложением его на множители нету: $x^n-1 = \prod\limits_{d|n}\Phi _d(x)$, где $\Phi _d (x)$ - круговые многочлены (можете о них на Вольфраме почитать http://mathworld.wolfram.com/CyclotomicPolynomial.html ). Поскольку $m+1$ четно, что $2^{K}+1 = \prod\limits_{d|K} \Phi _{2d}(2)$. Это для псевдопростых составных чисел. Для простых нужно пытаться сочинать аналог критерия Люка.

Цитата:

если n - составное число то его больший делитель также принадлежит нашему ряду

И кстати, если $a|b$, то и $\frac{2^a+1}{3}$ делит $\frac{2^b+1}{3}$ - это свойство следует отсюда.

-- Вт янв 25, 2011 10:10:31 --

Ascar писал(а):

для любого набора $m$ и $p$ будет верным представление значения $n$ в виде

$n=(2^t+1)/(2^p+x)$

где значение $x$ зависит по некоторому правилу от значения $m$ и $p$, надеюсь это правило выражается (вычисляется) ТОЛЬКО по этим двум значениям, сильно надеюсь :) было бы неплохо

$n=(2^t+1)/(2^p+x) \Leftrightarrow x=\frac{2^t+1}{n} - 2^p$ - существует по свойству 3: $2^t+1 \equiv 0 \pmod n$.
Так что

Ascar писал(а):

пока буду искать эту функцию, методом тыка(сбора стат данных) :)

можете не мучиться.

-- Вт янв 25, 2011 10:19:58 --

Ascar писал(а):

идея для своиства 2...
ну можно переформулировать

самый большой делитель числа $n$, являющийся простым числом имеет вид $(t*a+1)$, где $a$ целое число больше нуля

Лучше побольше последовательность чисел подсчитать и там потестировать хотя бы...

[Ascar]

Sonic86 в сообщении #404135 писал(а):

Ascar писал(а):

$n=(2^t+1)/(2^p+x) \Leftrightarrow x=\frac{2^t+1}{n} - 2^p$ - существует по свойству 3: $2^t+1 \equiv 0 \pmod n$.
Так что

Ascar писал(а):

пока буду искать эту функцию, методом тыка(сбора стат данных) :)

можете не мучиться.

$x=\frac{2^t+1}{n} - 2^p$
это точно не подойдет, тут требуется изначально знать значение n, а я предпологаю что его знать необязательно
по набору m и p можно наити значение x, либо доказать что его не существует
есть над чем помучится

-- Вт янв 25, 2011 10:07:14 --

Sonic86 в сообщении #404135 писал(а):

Ascar писал(а):

Цитата:

если n - составное число то его больший делитель также принадлежит нашему ряду

И кстати, если $a|b$, то и $\frac{2^a+1}{3}$ делит $\frac{2^b+1}{3}$ - это свойство следует отсюда.

нет нет и еще раз нет, вы както слишком просто все поняли, давайте поподробнее на первом составном примере

$(2^{29}+1)/3=178956971=59*3033169$

итак число $178956971$ принадлежит нашей последовательности и оно ДЕЙСТВИТЕЛЬНО имеет вид $(2^{28+1}+1)/(2^1+1)=(2^{29}+1)/3$ (m=28 p=1)
рассмотрим больший из делителей 3033169
$3033169=(2^{22+7}+1)/(2^7+49)=(2^{29}+1)/(2^7+49)$ (m=22 p=7)
а это согласитесь совсем не $\frac{2^b+1}{3}$
если мы научимся находить величину x=49 зная только набор значений (m=22 p=7) было бы неплохо

-- Вт янв 25, 2011 10:09:40 --

(Оффтоп)

круговые многочлены
чесно скажу буду читать долго :) но за ссылку спасибо
но раз числа Марсена удерживают лидерство значит не так уж и прост этот метод круговых многочленов

-- Вт янв 25, 2011 10:23:32 --

Sonic86 в сообщении #404135 писал(а):

Ascar писал(а):

Я вот это что-то понять не могу - откуда это взялось: $n=(2^{m+1}+1)/3$

выявленны две закономерности
1) если $m\equiv 0\pmod{p}$, то x=1
$n=(2^{m+p}+1)/(2^p+1)$, тоесть если p=1 имеем вид $n=(2^{m+1}+1)/3$
ну а если все на практике подсчитать то бросается в глаза что величина m+1 - простые числа, либо псевдопростое по основанию 2 (и кажется только те псевдопростые которые не делятся на 3, опять эта тройка, магическое число :) )

2) если $m$-четное число и $p=m-2$, то $x=2^{p}-2^{m/2}+1$
$n=(2^{m+p}+1)/(2^{p+1}-2^{m/2}+1)$

[Sonic86]

Ascar писал(а):

$x=\frac{2^t+1}{n} - 2^p$
это точно не подойдет, тут требуется изначально знать значение n, а я предпологаю что его знать необязательно

Не понял!!! Какая исходная задача??? Я думал, что "разложить $n$ на множители"...

Ascar писал(а):

нет нет и еще раз нет, вы както слишком просто все поняли, давайте поподробнее на первом составном примере

$(2^{29}+1)/3=178956971=59*3033169$

итак число $178956971$ принадлежит нашей последовательности и оно ДЕЙСТВИТЕЛЬНО имеет вид $(2^{28+1}+1)/(2^1+1)=(2^{29}+1)/3$ (m=28 p=1)
рассмотрим больший из делителей 3033169
$3033169=(2^{22+7}+1)/(2^7+49)=(2^{29}+1)/(2^7+49)$ (m=22 p=7)
а это согласитесь совсем не $\frac{2^b+1}{3}$

понял, спутал число с делителем. Но указанный признак тоже во многих случаях работает...

[Ascar]

Sonic86 в сообщении #404157 писал(а):

Ascar писал(а):

Не понял!!! Какая исходная задача??? Я думал, что "разложить $n$ на множители"...

ну да да.... чтоб наити делитель для числа n1 - который является элементом нашей последовательности, имеющий вид n1=(2^t1+1)/3 (т.е. p1=1)
необходимо уметь находить (желательно быстро) другие элементы нашей последовательности у кторых сумма m+p=t1

[Ascar]

Ascar в сообщении #404148 писал(а):

Sonic86 в сообщении #404135 писал(а):

Ascar писал(а):

выявленны две закономерности
1) если $m\equiv 0\pmod{p}$, то x=1
$n=(2^{m+p}+1)/(2^p+1)$, тоесть если p=1 имеем вид $n=(2^{m+1}+1)/3$
ну а если все на практике подсчитать то бросается в глаза что величина m+1 - простые числа, либо псевдопростое по основанию 2 (и кажется только те псевдопростые которые не делятся на 3, опять эта тройка, магическое число :) )

2) если $m$-четное число и $p=m-2$, то $x=2^{p}-2^{m/2}+1$
$n=(2^{m+p}+1)/(2^{p+1}-2^{m/2}+1)$

третья закономерность
3)если $m+3=2*p$, то $x=2^{p-1}+3$
$n=(2^{m+p}+1)/(2^{p}+2^{p-1}+3)$

[Ascar]

Ascar писал(а):

третья закономерность
3)если $m+3=2*p$, то $x=2^{p-1}+3$
$n=(2^{m+p}+1)/(2^{p}+2^{p-1}+3)$

извините ошибся
3)если $m+3=2*p$ и $m\equiv 0 \pmod 3$, то $x=2^{p-1}+3$
$n=(2^{m+p}+1)/(2^{p}+2^{p-1}+3)$

[Ascar]

Ascar в сообщении #404773 писал(а):

извините ошибся
3)если $m+3=2*p$ и $m\equiv 0 \pmod 3$, то $x=2^{p-1}+3$
$n=(2^{m+p}+1)/(2^{p}+2^{p-1}+3)$

всетаки верно будет так
3)если $m+3=2*p$ и $m+p\equiv 0 \pmod 3$, то $x=2^{p-1}+3$
$n=(2^{m+p}+1)/(2^{p}+2^{p-1}+3)$