2014 dxdy logo

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

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


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


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Простое число, цифры которого образуют арифм. прогрессию
Сообщение13.08.2018, 10:34 
Аватара пользователя


01/12/11

8634
В книге «800 лучших олимпиадных задач по математике» предлагается следующая задача (мне не свойственны суеверия, но тем не менее она в этой книге идёт под номером 13):

Найти четырёхзначное простое число, цифры которого образуют арифметическую прогрессию.

У меня два вопроса в связи с этой задачей:

1) Допустим, участник олимпиады подозревает, что число 4567 удовлетворяет условию задачи. Как он станет доказывать простоту этого числа? Неужели делимость на каждое из простых чисел от 2 до 67 станет проверять?

2) Число 5867 - простое, а его цифры (5, 6, 7 и 8) образуют арифметическую прогрессию. Имею ли я право утверждать, что и это число удовлетворяет условию задачи?

 Профиль  
                  
 
 Re: Простое число, цифры которого образуют арифм. прогрессию
Сообщение13.08.2018, 10:53 
Аватара пользователя


01/11/14
1647
Principality of Galilee
Ktina в сообщении #1332134 писал(а):
Число 5867 - простое, а его цифры (5, 6, 7 и 8) образуют арифметическую прогрессию. Имею ли я право утверждать, что и это число удовлетворяет условию задачи?
Наверное, имеете. Условие не совсем чёткое. Если рассматривать цифры числа в любом порядке, то подходит ещё простое $2431$.
Если же цифры рассматривать в том порядке, в котором они составляют число, то подходящее только Ваше число 4567.
Я-то запустил маленькую программку, но перебрать в уме все простые делители до $67$ - дело 10 мин., не более.

 Профиль  
                  
 
 Re: Простое число, цифры которого образуют арифм. прогрессию
Сообщение13.08.2018, 11:09 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
По пункту 2. Разумеется, авторы задачи изначально подразумевали, что цифры числа должны образовывать прогрессию в том порядке, в котором они следуют в самом числе. Но они не указали этого явно, и потому сами себе злобные буратины, и участник соревнования имеет полное право это отапеллировать. И судьи, если они, конечно, не являются неадекватными баранами, должны апелляцию зачесть.

 Профиль  
                  
 
 Re: Простое число, цифры которого образуют арифм. прогрессию
Сообщение13.08.2018, 11:16 


05/09/16
11461
Ktina в сообщении #1332134 писал(а):
Как он станет доказывать простоту этого числа? Неужели делимость на каждое из простых чисел от 2 до 67 станет проверять?

Помойму доказать простоту можно только так.

Всего таких чисел $30$ из них $9$ репдиджитов, которые все очевидно делятся на $11$).
Из осташихся делятся на $2,3$ или $5$ -- $17 $чисел.
Остается $4$ кандидата:
$1357=23 \cdot 59$
$4567=$простое
$4321=29\cdot 149$
$7531=17 \cdot 443$
Думаю что кроме как факторизовать, выбора нет. Делимости на $11$ быть не может, так что на бумажке придется делить на остальные делители начиная с $7$, затем $13$ и далее по списку (ну особо умные в уму проверят на $7$ и какие-то еще). Ну а с другой стороны -- это ж олимпиада, хотя бы 10-15 минут на задачу должно уходить?

 Профиль  
                  
 
 Re: Простое число, цифры которого образуют арифм. прогрессию
Сообщение13.08.2018, 11:19 
Аватара пользователя


01/11/14
1647
Principality of Galilee
Aritaborian в сообщении #1332141 писал(а):
Разумеется, авторы задачи изначально подразумевали, что цифры числа должны образовывать прогрессию в том порядке, в котором они следуют в самом числе.
Aritaborian
Из чего следует Ваше "разумеется"?
Доводилось быть составителем олимпиадных задач, или, паче чаяния, членом судейского жюри?

 Профиль  
                  
 
 Re: Простое число, цифры которого образуют арифм. прогрессию
Сообщение13.08.2018, 11:38 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
Я с двухтысячного года играю в спортивное ЧГК, а ещё я трижды сдавал ЦТ (аналог российского ЕГЭ) по математике и физике. Разумеется, это не то же самое, что быть составителем олимпиадных задач или членом жюри, но данный опыт позволяет мне судить об образе мысли людей, составляющих такие задачи.

 Профиль  
                  
 
 Re: Простое число, цифры которого образуют арифм. прогрессию
Сообщение13.08.2018, 12:36 
Заслуженный участник
Аватара пользователя


09/09/14
6328
wrest в сообщении #1332142 писал(а):
так что на бумажке придется делить на остальные делители начиная с $7$, затем $13$ и далее по списку (ну особо умные в уму проверят на $7$ и какие-то еще).
Вы так шутите?! Да для любого четырёхзначного числа делимость на двузначное проверяется в уме двумя-тремя простыми действиями.

Например, на 67: отнимаете $4567-67=4500$ и делите на 100. С любым другим числом можно поступить точно так же -- избавиться от первой или от последней цифры. Например, на 53: $4567-53\cdot 80=327$ и 53 на 9 больше 327 (последнее вычислять не нужно, только сравнить).

 Профиль  
                  
 
 Re: Простое число, цифры которого образуют арифм. прогрессию
Сообщение13.08.2018, 19:54 


05/09/16
11461
grizzly в сообщении #1332177 писал(а):
Например, на 67: отнимаете $4567-67=4500$ и делите на 100. С любым другим числом можно поступить точно так же -- избавиться от первой или от последней цифры. Например, на 53: $4567-53\cdot 80=327$ и 53 на 9 больше 327 (последнее вычислять не нужно, только сравнить).

grizzly в сообщении #1332177 писал(а):
Например, на 53: $4567-53\cdot 80=327$ и 53 на 9 больше 327

А почему на 9? :shock: На 7 и на 8 - тоже больше :mrgreen: А... понял почему на 9.
Ну и скока надо посчитать в уму для сертификации $4567$ на простоту?
Во-первых, надо извлечь квадратный корень. Он равен упомянутому $67$, конечно, но его таки надо извлечь.
Затем надо выписать все простые до $67$ включительно, это $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67$ и быстренько по 2-3 действия посчитать. По скока секунд, вы думаете, надо потрать на каждое (начиная с $13$)? Ну еще плюс извлечение корня и выписывание их всех (чтоб никакое не пропустить и не забыть на котором остановился когда зачешется в носу). Думаю минут 10 (а то и больш) как раз и потратится.
Задача какая-то муторная и мне представляется, что Ktina тут прав(-а): на олимпиадность, кажись, не тянет. В самом деле: как можно НЕ решить эту задачу? Тока если времени не хватит на сертификацию простоты или таблица умножения позбылась.

 Профиль  
                  
 
 Re: Простое число, цифры которого образуют арифм. прогрессию
Сообщение13.08.2018, 20:55 
Заслуженный участник
Аватара пользователя


09/09/14
6328
wrest в сообщении #1332283 писал(а):
Во-первых, надо извлечь квадратный корень. Он равен упомянутому $67$, конечно, но его таки надо извлечь.
Нет, не нужно. Достаточно возвести 70 в квадрат (это ведь не очень сложно?) и взять все простые числа до 70.

Но я возражаю только против отдельный утверждений, что нужно что-то сложное считать. А задачу я тоже не могу счесть красивой. Даже если (сомневаюсь, но вдруг) можно придумать какое-то олимпиадное решение. Просто потому, что в лоб всё перепроверить займёт с оформлением минут 20. Поэтому глупо было бы на реальной олимпиаде пытаться искать не тупое решение.

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

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



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

Сейчас этот форум просматривают: Gg322, mihaild


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

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