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

[Ascar]

Мне кажется ниже расматриваемые числа имеет некоторую общую природу с Мерсенновскими числами. Если неправ поправте меня.

Рассмотрим.....
Числа $n$ удовлетворяющие условию.
$2^{n-1}\equiv 1\pmod{n}$
$2^{n-m-1}\equiv n-2^{p}\pmod{n}$
где $m$ и $p$ целые положительные числа больше нуля, удовлеворяющие условию
$2^{m-1}<n<2^{m}$
$1<2^{p}<n$
----------------
заявка в OEIS A167612, лежит на рассмотрении :)
первые элементы
3, 11, 13, 19, 41, 43, 241, 331, 683, 2113, 2731, 3277, 4033, 5419, 8321, 43691, 61681, 65281, 80581, 85489, 87211, 174763, 233017, 253241, 525313, 838861, 1016801, 1397419, 2796203, 3033169, 3605429, 4682833, 6700417, 13421773, 15790321, 16773121, 18837001, 20647621, 22253377, 22366891, 24214051, 25080101, 25781083, 30662497, 47349373, 50155733, ....

----------------
Основные свойства для $n>3$ (тройка как всегда идет своим путем) которые видны с первого взгляда
ключевая величина (показатель степени), введем переменную t
$t=m+p$

1) $n\equiv 1\pmod{t}$
2) Если $n$ - составное число, то его можно представить в виде, $n=(x*t+1)*(y*t+1)$, где $x$ и $y$ целые положительные числа больше нуля.

в этих (первых двух) свойствах я и вижу сходство с числами Мерсенна

3) $2^{t}+1\equiv 0\pmod{n}$
-----------------------
-- Пт янв 21, 2011 12:56:04 --

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

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

[Sonic86]

Вот что такое $m$ я понял: $m = 2^{\lceil \log _2 n\rceil}$ (хотя случай $n=2^r$ у автора не рассмотрен).
А что такое $p$? Это одно число или произвольное $p: 1 \leq p \leq \log _2 n$

[Ascar]

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

Вот что такое $m$ я понял: $m = 2^{\lceil \log _2 n\rceil}$ (хотя случай $n=2^r$ у автора не рассмотрен).
А что такое $p$? Это одно число или произвольное $p: 1 \leq p \leq \log _2 n$

например для 241
m=8 т.к. 128<241<256

p - одно число, находится оно из остатка при рассмотрении выражения $2^{n-m-1}\equiv n-2^{p}\pmod{n}$
p=4 для 241
2^(241-1-8) = 241-2^4 (mod 241)
вообщем $m$ и $p$ для каждого числа $n$ строго определяются если это возможно, в противном случае их просто нет

[Sonic86]

Ascar писал(а):

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

В смысле, Вы нашли несколько чисел $n$, удовлетворяющих условию $2^{n-1}\equiv 1\pmod{n}$, а потом проверяли, являются ли они простыми или псевдопростыми по модулю $2$???

[Ascar]

я нашол $X$!
$X$ - простое или псевдопростое :)

[Sonic86]

Ascar писал(а):

например для 241
m=8 т.к. 128<241<256

ой! наврал, просто: $m=\lceil \log _2 n\rceil$

Ascar писал(а):

p - одно число, находится оно из остатка при рассмотрении выражения $2^{n-m-1}\equiv n-2^{p}\pmod{n}$

То есть, Вы утверждаете, что $(n-2^{n-m-1}) \mod n$ является степенью 2? Или $p = \text{ind}_2(n-2^{n-m-1}) \pmod {\varphi (n)}$ - индекс (дискретный логарифм) по основанию 2? А разве он всегда будет определен? Ведь $2$ - необязательно первообразная по модулю $n$?

-- Пт янв 21, 2011 15:16:50 --

Ascar писал(а):

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

Ну $m$ из формулы определяется всегда. А вот $p$ получается не всегда. Правильно?

Ascar писал(а):

я нашол $X$!
$X$ - простое или псевдопростое :)

А! Пока понятно, туплю...

[Ascar]

к целой части логарифма 1 надо добавить

второе, да mod будет 2^p

p - будет не всегда, я же числа из последовательности привел, берите любое и считайте, когда оно получается

[Sonic86]

Ascar писал(а):

к целой части логарифма 1 надо добавить

В $m=\lceil \log _2 n\rceil$ не целая часть, а функция "потолок" - наименьшее целое, больше или равное данному...

[Ascar]

ааа, сказывается отсутсвие у меня академ образования :) тупим немного

[Sonic86]

Пока исключений не нашел почти, кроме (простых?) чисел Ферма. Например для $n=17$:
$2^{16} \equiv 1 \pmod 17$
$m=5$
$n-2^{n-m-1}\equiv 17-2^{11} \equiv 9 \equiv 2^7 \pmod{17} \to p=7$
$t=m+p=12$
1) $17 \not \equiv 1 \pmod{12}$
В общем - надо уже доказательства свойств искать, иначе неинтересно.

Прежде всего числа, аналогичные Мерсенну, насколько я понимаю, могут быть интересны, если они длинные, среди них много простых + это можно как-то быстро установить. тогда, во-первых, нужен способ этой проверки, что достаточно нетривиально. Например, Мерсенну подобны числа $\frac{(n+1)^p-n^p}{d}$, где $d = \gcd \{ (k+1)^p-k^p\}_{k=1}^{+ \infty}$ - НОД последовательности (а также последовательность $\Phi (n)$), среди них примерно столько же простых, сколько среди чисел Мерсенна, однако аналога критерия Люка вроде как нету.
М.б. есть что-то еще интересное - хотелось бы знать...
А само по себе выглядит довольно интересно. Странные какие-то свойства...

[Ascar]

$2^7>17$
17 мы рассматривать не можем!
условие $2^p<n$

может быть.... при $2^p>n$ для ПЕРВОГО свойства стоит рассматривать разность m и p, а не сумму.... ну это из числа догадок :)

делители у составных чисел имеют интересное своиство, пока сформулировать немогу четко
чисел для анализа маловато :) но напишу обязательно

доказательством заимитесь, для этого здесь и пишу, а я любитель эксперементатор

[Sonic86]

Ааа! Понятно...

(Оффтоп)

чистый экспериментатор в теории чисел - это очень мало. Говорю как бывший экспериментатор

[Ascar]

(Оффтоп)

я знаю ученье свет :) стараемся

интерес - конечно же наличие легкого способа факторизации :)

[Sonic86]

Короче так.
$2^{n-m-1} \equiv n-2^p \pmod n \Rightarrow 2^{n-m-1} \equiv -2^p \pmod n$, а поскольку $2^{n-1} \equiv 1 \pmod n$, то $2^{-m} \equiv -2^p \pmod n \Leftrightarrow 2^{m+p}+1 \equiv 1 \pmod n \Leftrightarrow 2^t+1 \equiv 0 \pmod n$ - 3 доказано.
$2^{2t} \equiv 1 \pmod n$ и $2^t \not \equiv 1 \pmod n$

$2^{n-1} \equiv 1 \pmod n \Rightarrow n \equiv 1 \pmod 2$
Поскольку $m =\lceil \log _2(n) \rceil$ и $n$ нечетно, то $m \leq \log _2(n)+1$. По условию $2^p < n \Leftrightarrow p < \log _2(n)$, откуда $t \leq 2 \log _2(n)$.
Для определенных нечетных чисел $n$ $t$ существует и + существует порядок $a$ числа 2 по модулю $n$. Докажем, что этот порядок равен $2t$. Предположим, что это не так. Тогда $a<2t$ Поскольку $2^{m-1} < n$, то $a \geq m$, и еще кстати $2m<2t \leq 4m$. $a$ - порядок 2 по модулю $n$, значит $a|2t, a<2t$, тогда из ограничений $a \geq m-1$ и $2m<2t \leq 4m$ получаем, что $\frac{2t}{a} = 1;2;3;4$. Но поскольку $2^t+1 \neq 0 \pmod n$, по предположению $a \neq 2t$, то $\frac{2t}{a} = 3;4$. Случай $\frac{2t}{a} = 4$ противоречит доказанному пункту 3. Остается случай $a=\frac{2t}{3}$, на котором я пока застрял, но видимо, уже нужно контрпример искать среди чисел $n:n \equiv 2 \pmod 3$ (еще подумаю...)

-- Сб янв 22, 2011 13:15:09 --

Ascar писал(а):

интерес - конечно же наличие легкого способа факторизации :)

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

[Ascar]

1. Для любого набора m и p, либо существет только одно значение n, либо такого значения нет.



-- Сб янв 22, 2011 14:58:19 --

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