2014 dxdy logo

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

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





Проводя рассуждения в уме, выберите пару простых чисел
1999, 19999 23%  23%  [ 3 ]
2^7-1, 2^91-1 38%  38%  [ 5 ]
4$\cdot$11^40647-1, 4$\cdot$11^40749-1 31%  31%  [ 4 ]
4$\cdot$11^40647+1, 4$\cdot$11^40749+1 8%  8%  [ 1 ]
Всего голосов : 13
 
 Интуиция на простые числа
Сообщение23.08.2017, 01:56 
Не так давно была тема "физическая интуиция" http://dxdy.ru/topic119622.html. Можно сказать, что эта тема создана по мотивам.

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

 
 
 
 Re: Интуиция на простые числа
Сообщение23.08.2017, 12:59 
Аватара пользователя
Это не интуиция, это простенький расчёт. В первом надо проверять делимость на 7 через 1001, во втором - тоже на 7, только не у самого числа, а у показателя степени, в остальных - на 3.

 
 
 
 Re: Интуиция на простые числа
Сообщение23.08.2017, 13:36 
В третьем примере как помогает проверка делимости на 3?

 
 
 
 Re: Интуиция на простые числа
Сообщение23.08.2017, 14:28 
Аватара пользователя
Никак. Зато помогает в четвёртом, что оставляет единственный вариант.

 
 
 
 Re: Интуиция на простые числа
Сообщение23.08.2017, 18:04 
А я думал второй...

 
 
 
 Re: Интуиция на простые числа
Сообщение23.08.2017, 20:34 
Рассуждения, приводящие к верному ответу, расписал ИСН.

kotenok gav в сообщении #1242581 писал(а):
А я думал второй...

Во втором, как мне казалось, сразу бросается в глаза, что $91=7\cdot 13$. Поэтому число $2^{91}-1$ делится на $2^7-1$, а также на $2^{13}-1$. На этом базируется известный факт, что простые числа Мерсенна должны иметь простой показатель.

Простые из пункта 3 были найдены при тестировании алгоритма быстрого вычисления линейных рекуррентных последовательностей 2-го порядка в детерминированном тесте простоты. Немного был удивлён, что в OEIS они отсутствуют, хотя размеры чисел, по современным меркам, весьма скромные и найти их можно меньше чем за сутки. Вероятно, это связано с отсутствием интереса к простым вида $4\cdot 11^p-1$.

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group