2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.



Начать новую тему Ответить на тему
 
 Сможете ли посчитать?
Сообщение19.06.2007, 15:12 


03/10/06
826
Вот aribas не смог посчитать
${(\frac{2^{2^{127} - 2} - 1}{2^{127} - 1} - \frac{2^{127} - 2}{2^7 - 1})} mod {(2^{127} - 1)}$ равно $0$ ?

"
==> ${(\frac{2^{2^{3} - 2} - 1}{2^{3} - 1} - \frac{2^3 - 2}{2^2 - 1})} mod {(2^3 - 1)}$.
-: $0$

==> ${(\frac{2^{2^{7} - 2} - 1}{2^{7} - 1} - \frac{2^7 - 2}{2^3 - 1})} mod {(2^7 - 1)}$.
-: $0$

==> ${(\frac{2^{2^{127} - 2} - 1}{2^{127} - 1} - \frac{2^{127} - 2}{2^7 - 1})} mod {(2^{127} - 1)}$.
**: arithmetic overflow
-: number expected: $break
div: number expected: $break
-: number expected: $break
mod: number expected: $break
-: error
"

 Профиль  
                  
 
 Re: Сможете ли посчитать?
Сообщение19.06.2007, 16:17 
Заслуженный участник
Аватара пользователя


01/03/06
13626
Москва
yk2ru писал(а):
Вот aribas не смог посчитать
((2**(2**127 - 2) - 1) div (2**127 - 1) - (2**127 - 2) div (2**7 - 1)) mod (2**127 - 1) равно 0 ?
:

"
==> ((2**(2**3 - 2) - 1) div (2**3 - 1) - (2**3 - 2) div (2**2 - 1)) mod (2**3 - 1).
-: 0

==> ((2**(2**7 - 2) - 1) div (2**7 - 1) - (2**7 - 2) div (2**3 - 1)) mod (2**7 - 1).
-: 0

==> ((2**(2**127 - 2) - 1) div (2**127 - 1) - (2**127 - 2) div (2**7 - 1)) mod (2**127 - 1).
**: arithmetic overflow
-: number expected: $break
div: number expected: $break
-: number expected: $break
mod: number expected: $break
-: error
"
Ваше сообщение не читаемо.

Добавлено спустя 1 час 51 секунду:

После редактирования мало что изменилось.

 Профиль  
                  
 
 
Сообщение19.06.2007, 22:07 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
yk2ru писал(а):
${(\frac{2^{2^{127} - 2} - 1}{2^{127} - 1} - \frac{2^{127} - 2}{2^7 - 1})} mod {(2^{127} - 1)}$

Полагаю, что имеется в виду что-то типа:

${(\frac{2^{(2^{(2^x-1)} - 2)} - 1}{2^{(2^x-1)} - 1} - \frac{2^{(2^x-1)} - 2}{2^x - 1})} \mod {(2^{(2^x-1)} - 1)}$

Или, положив $p = 2^x-1$ (простое), $q = 2^p-1$ (оно тоже простое), ${(\frac{2^{q-1} - 1}{q} - \frac{q-1}{p})} \mod {q}$

Вся любовь сводится к вычислению $2^q-1 \mod q^2$, что, собственно, скучно. Писать программу — лень, посмотрите Exponentiation by squaring

Добавлено спустя 12 минут 14 секунд:

А впрочем, да, 0.
Код:
p  = 2^127 - 1;
pwr[x_, n_, m_] :=
    Which[
       n == 0, 1,
       n == 1, x,
       EvenQ[n], Mod[pwr[x, n/2, m]^2, m],
       True, Mod[x pwr[x, (n - 1)/2, m]^2, m]
    ];
(pwr[2, p - 1, p^2]-1)/p-(p-1)/127


Доли секунды…

 Профиль  
                  
 
 
Сообщение20.06.2007, 14:28 


03/10/06
826
На чём это записано, какой програмный инструмент использовали?

 Профиль  
                  
 
 
Сообщение20.06.2007, 17:36 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Mathematica. Но это абсолютно не важно: я готов поспорить, что на Python это займет те же пол-страницы (или меньше), в отличии от проверки простоты $q$.

P.S. 1, 3, 5, 7, 13. Ваш следующий кандидат — 17.

 Профиль  
                  
 
 
Сообщение21.06.2007, 16:51 


03/10/06
826
Обобщим:
Пусть $C_0 = 2$, а $C_1 = 2^{C_0}-1$, $C_2 = 2^{C_1}-1$, $C_3 = 2^{C_2-1}$, ...,$C_n=2^{C_{n-1}}-1$
то есть имеем ряд чисел $2, 3, 7, 127$, ...
и пусть $D_n = \frac{C_n - 1}{C_{n-1}}$
и предыдущее тождество запишем как $$D_{n+1}-2D_n\mod C_n = 0$$
а далее ещё одно тождество вроде как есть $$\frac{D_{n+1}-2D_n}{C_n}-D_n(D_n-1)\mod C_n = 0$$

 Профиль  
                  
 
 
Сообщение21.06.2007, 17:22 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Думаю, что Ваше обобщение может быстро кончится. По крайней мере, $C_k$ будут не все (скорее всего) простыми, и поэтому делимость может оказаться проблематичной…

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

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



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

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


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

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