2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Более широкий взгляд на числа Мерсенна
Сообщение22.01.2011, 17:41 


27/11/08
111
Если $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$)

 Профиль  
                  
 
 Re: Более широкий взгляд на числа Мерсенна
Сообщение23.01.2011, 17:54 


27/11/08
111
если $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$, надеюсь это правило выражается (вычисляется) ТОЛЬКО по этим двум значениям, сильно надеюсь :) было бы неплохо

 Профиль  
                  
 
 Re: Более широкий взгляд на числа Мерсенна
Сообщение23.01.2011, 19:02 
Заслуженный участник


08/04/08
8556
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$. Кажись, это метод Полларда. Сейчас посмотрю...

 Профиль  
                  
 
 Re: Более широкий взгляд на числа Мерсенна
Сообщение23.01.2011, 19:50 


27/11/08
111
спасибо за доказательство 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$

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

 Профиль  
                  
 
 Re: Более широкий взгляд на числа Мерсенна
Сообщение24.01.2011, 17:28 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Более широкий взгляд на числа Мерсенна
Сообщение24.01.2011, 17:47 


27/11/08
111
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
ну вообщем природа у них общая... некая природа :)

 Профиль  
                  
 
 Re: Более широкий взгляд на числа Мерсенна
Сообщение24.01.2011, 19:01 
Заслуженный участник


08/04/08
8556
Я тогда пока повременю с доказательством свойства 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 - составное число то его больший делитель также принадлежит нашему ряду

 Профиль  
                  
 
 Re: Более широкий взгляд на числа Мерсенна
Сообщение24.01.2011, 21:30 


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

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

 Профиль  
                  
 
 Re: Более широкий взгляд на числа Мерсенна
Сообщение25.01.2011, 06:57 
Заслуженный участник


08/04/08
8556
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$ целое число больше нуля

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

 Профиль  
                  
 
 Re: Более широкий взгляд на числа Мерсенна
Сообщение25.01.2011, 08:56 


27/11/08
111
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)$

 Профиль  
                  
 
 Re: Более широкий взгляд на числа Мерсенна
Сообщение25.01.2011, 09:41 
Заслуженный участник


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

Не понял!!! :shock: Какая исходная задача??? Я думал, что "разложить $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}$

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

 Профиль  
                  
 
 Re: Более широкий взгляд на числа Мерсенна
Сообщение25.01.2011, 09:47 


27/11/08
111
Sonic86 в сообщении #404157 писал(а):
Ascar писал(а):

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


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

 Профиль  
                  
 
 Re: Более широкий взгляд на числа Мерсенна
Сообщение26.01.2011, 12:11 


27/11/08
111
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)$

 Профиль  
                  
 
 Re: Более широкий взгляд на числа Мерсенна
Сообщение26.01.2011, 13:28 


27/11/08
111
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)$

 Профиль  
                  
 
 Re: Более широкий взгляд на числа Мерсенна
Сообщение26.01.2011, 17:33 


27/11/08
111
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)$

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 30 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group