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
8858
Это сводится к тестированию на простоту чисел Ферма. Критерий простоты таких чисел известен.

 Профиль  
                  
 
 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
8858
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
8858
Для б) достаточно вычислить $\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
10626
Crna Gora

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

Любители олимпиадных задач часто интересуются, на какой олимпиаде была задача. Мне очень интересно, какое это имеет значение? Не сомневаюсь, что имеет, судя по постоянным вопросам "в каком городе давалась задача?", но какое именно?

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


01/12/11

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

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

Любители олимпиадных задач часто интересуются, на какой олимпиаде была задача. Мне очень интересно, какое это имеет значение? Не сомневаюсь, что имеет, судя по постоянным вопросам "в каком городе давалась задача?", но какое именно?

(Оффтоп)

У каждой страны (региона, города, ...) свои особенности, что отражается также на условиях и характере олимпиадных задач. Например, для олимпиадных задач Тайваня и Гонк-Конга характерны как перекос в сторону теории чисел, так и расчёт на эрудицию и чисто технические решения. А вот ленинградские олимпиады (особенно отборочный тур) - для особоозарённых. Польские и китайские - заковыристые, а всесоюзки рассчитаны на голый интеллект. В румынских много геометрии, а в американских - комбинаторики. В канадских и шведских почти половина задач - тривиальные (решаются в два-три действия). Французские отличаются заумными условиями. В условиях задач израильских олимпиад немало скоммунизжено с ленинградских и всесоюзных (сразу видно, кто составлял). Ну а маргоградские, как правило, рассчитаны на нестандартное мышление.

P. S.
А, ещё монгольские забыла упомянуть. Как-то читала статью о чемпионах мира по шахматам, в которой каждому чемпиону был поставлен в соответствие какой-нибудь эпитет. Каспаров - быстроменяющийся, Стейниц - экспериментатор, Полгар - убийца и т. п. Так вот, Таль был инопланетянин. Вот и монгольские олимпиады примерно такие же, ни в одни рамки не вписываются.

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


23/07/08
10626
Crna Gora

(Оффтоп)

Спасибо, жутко интересно! :P
Ktina писал(а):
В канадских и шведских почти половина задач - тривиальные (решаются в два-три действия).
Не зря мне в детстве казалось, что Швеция и Канада в каком-то труднообъяснимом смысле образуют пару (при этом я их вовсе не путал). Аналогично -- Польша и Франция, и третья пара -- Чехословакия и Югославия, ну, тут хоть немного понятно.

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


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

(Оффтоп)

What can you say about Bulgarian and Iranian math olympiads? I like them both :-) .

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


20/12/10
8858
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
8858
Ktina в сообщении #545919 писал(а):

(Оффтоп)

А секрет Полишинеля Вы мне в пику раскрыли? Вот теперь меня забанят и пойду топиться

(Оффтоп)

Нет, это произошло случайно, в порыве эмоций. Какое там забанят. Не дадим-с :D Кстати, про олимпиады неплохо написано. Мне вот вспоминаются вьетнамские неравенства, очень экзотичные и нетривиальные. И ещё одна Chinese Girls' Mathematics Olympiad с нехилыми задачами.

 Профиль  
                  
 
 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