2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Операции с ЦНЧ
Сообщение24.07.2018, 15:40 
Аватара пользователя


01/12/11

8634
С ЦНЧ (Целым Неотрицательным Числом) разрешается производить следующие операции:
1) Умножать на составное число, 2) Прибавлять или отнимать простое число.

Докажите, что из нуля можно получить любое ЦНЧ не более чем за 3 операции, и найдите наименьшее ЦНЧ, которое нельзя получить из 0 не более чем за 2 операции.

 Профиль  
                  
 
 Re: Операции с ЦНЧ
Сообщение24.07.2018, 16:32 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
Простые числа получаются за один шаг, составные - не более чем за $3$: $0 \to 3 \to 1 \to 1 \cdot x$.
За $2$ операции гарантированно можно получить все (небольшие) четные (гипотеза Гольдбаха), все простые, все нечетные вида $p \pm 2$. Наименьшим числом не такого вида является $93 = 3 \cdot 31$. Его нельзя получить меньше чем за $3$ операции: последняя операция - это либо прибавление / вычитание простого (тогда перед ней у нас было составное число - либо четное, либо $91$ или $95$, а составные числа не получаются за $1$ шаг), либо умножение на составное - тогда перед ней было $1$, а $1$ тоже не получается за $1$ шаг.

 Профиль  
                  
 
 Re: Операции с ЦНЧ
Сообщение24.07.2018, 22:57 
Аватара пользователя


01/12/11

8634
mihaild
Большое спасибо!
Бонусный вопрос (который следовало в самом начале задать): С олимпиады какого года эта задача? :P

 Профиль  
                  
 
 Re: Операции с ЦНЧ
Сообщение25.07.2018, 15:01 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
Ну, видимо, 1993-го или конца 1992-го. Это хоть как-то её оправдывает.

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

Модератор: Модераторы



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

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


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

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