fixfix
2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Простые вида n^n+1
Сообщение06.03.2012, 12:29 
Аватара пользователя


01/12/11

8634
а) Найти все простые числа вида $n^n+1$ (где $n$ - натуральное), содержащие не более 19 цифр в своей десятичной записи.

б) Тот же вопрос для 616 цифр.

 Профиль  
                  
 
 Re: Простые вида n^n+1
Сообщение06.03.2012, 12:41 
Заслуженный участник


20/12/10
9179
Это сводится к тестированию на простоту чисел Ферма. Критерий простоты таких чисел известен.

 Профиль  
                  
 
 Re: Простые вида n^n+1
Сообщение06.03.2012, 13:11 
Аватара пользователя


01/12/11

8634
nnosipov в сообщении #545779 писал(а):
Это сводится к тестированию на простоту чисел Ферма. Критерий простоты таких чисел известен.

Тест Пепина?

 Профиль  
                  
 
 Re: Простые вида n^n+1
Сообщение06.03.2012, 14:43 
Заслуженный участник


20/12/10
9179
Ktina в сообщении #545787 писал(а):
Тест Пепина?
Он самый. Но работает он, конечно, если только число цифр не слишком велико. Несколько сотен цифр на обычном компьютере не проблема.

 Профиль  
                  
 
 Re: Простые вида n^n+1
Сообщение06.03.2012, 15:16 
Аватара пользователя


01/12/11

8634
nnosipov в сообщении #545810 писал(а):
Ktina в сообщении #545787 писал(а):
Тест Пепина?
Он самый. Но работает он, конечно, если только число цифр не слишком велико. Несколько сотен цифр на обычном компьютере не проблема.

Но на олимпиаде компов нет. Поэтому нужно:

а) доказать, что число $16^{16}+1$ - составное

б) доказать, что в числе $256^{256}+1$ более 616 цифр.

 Профиль  
                  
 
 Re: Простые вида n^n+1
Сообщение06.03.2012, 16:03 
Заслуженный участник


20/12/10
9179
Для б) достаточно вычислить $\lg{2}$ до трёх знаков. А вот а) поинтереснее будет. Во всяком случае, наименьший простой делитель $p=2^8k+1$ получается только при $k=1071$. А на какой олимпиаде это было?

 Профиль  
                  
 
 Re: Простые вида n^n+1
Сообщение06.03.2012, 17:01 
Аватара пользователя


01/12/11

8634
nnosipov в сообщении #545824 писал(а):
Для б) достаточно вычислить $\lg{2}$ до трёх знаков. А вот а) поинтереснее будет. Во всяком случае, наименьший простой делитель $p=2^8k+1$ получается только при $k=1071$. А на какой олимпиаде это было?

Первый пункт - на маргоградской, а второй я придумала в силу того, что первый показался мне чересчур тривиальным.

 Профиль  
                  
 
 Re: Простые вида n^n+1
Сообщение06.03.2012, 17:09 
Заслуженный участник
Аватара пользователя


23/07/08
10910
Crna Gora

(Откройте тайну!)


 Профиль  
                  
 
 Re: Простые вида n^n+1
Сообщение06.03.2012, 17:39 
Аватара пользователя


01/12/11

8634
svv в сообщении #545840 писал(а):

(Откройте тайну!)


(Оффтоп)


 Профиль  
                  
 
 Re: Простые вида n^n+1
Сообщение06.03.2012, 17:47 
Заслуженный участник
Аватара пользователя


23/07/08
10910
Crna Gora

(Оффтоп)


 Профиль  
                  
 
 Re: Простые вида n^n+1
Сообщение06.03.2012, 19:27 
Аватара пользователя


13/10/07
755
Роман/София, България

(Оффтоп)


 Профиль  
                  
 
 Re: Простые вида n^n+1
Сообщение06.03.2012, 21:30 
Заслуженный участник


20/12/10
9179
Ktina в сообщении #545813 писал(а):
Но на олимпиаде компов нет. Поэтому нужно:

а) доказать, что число $16^{16}+1$ - составное
Ксения, какого, пардон, ...!? Вы считали количество цифр в числе $16^{16}+1$? Я вот только сейчас сообразил подсчитать, их оказалось 20!!! А перед этим битый час пытался понять, в чём фокус. Короче, без компа нельзя.

 Профиль  
                  
 
 Re: Простые вида n^n+1
Сообщение06.03.2012, 23:22 
Аватара пользователя


01/12/11

8634
nnosipov в сообщении #545903 писал(а):
Ktina в сообщении #545813 писал(а):
Но на олимпиаде компов нет. Поэтому нужно:

а) доказать, что число $16^{16}+1$ - составное
Ксения, какого, пардон, ...!? Вы считали количество цифр в числе $16^{16}+1$? Я вот только сейчас сообразил подсчитать, их оказалось 20!!! А перед этим битый час пытался понять, в чём фокус. Короче, без компа нельзя.

Я знаю, чем я Вас запутала. Надо было вместо "а" и "б" написать "1" и "2", так как и $16^{16}$, и $256^{256}$ относятся к пункту б) и только к нему. Однако я была уверена в том, что для Вас очевидно, что в числе $16^{16}$ более 19 цифр, ведь тут даже логарифм не нужен: $16^{16}=2^{64}=2^{60}\cdot 16>10^{18}\cdot 16$

(Оффтоп)


 Профиль  
                  
 
 Re: Простые вида n^n+1
Сообщение07.03.2012, 06:07 
Заслуженный участник


20/12/10
9179
Ktina в сообщении #545919 писал(а):

(Оффтоп)

(Оффтоп)


 Профиль  
                  
 
 Re: Простые вида n^n+1
Сообщение07.03.2012, 12:55 


11/02/12
36
A= n^n+1
так как если степень имет нечетный делитель,то число сотавное, чтобы проверить до 616 знака достаточно проверить на простоту при n=2^1,2^2,...,2^8, но все A при таких n будут давать остаток 3 при делении на 6, но простое числа дает только 1 и -1 остаток

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

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



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

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


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

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