2014 dxdy logo

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

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




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

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

 
 
 
 Re: Операции с ЦНЧ
Сообщение24.07.2018, 16:32 
Аватара пользователя
Простые числа получаются за один шаг, составные - не более чем за $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 
Аватара пользователя
mihaild
Большое спасибо!
Бонусный вопрос (который следовало в самом начале задать): С олимпиады какого года эта задача? :P

 
 
 
 Re: Операции с ЦНЧ
Сообщение25.07.2018, 15:01 
Аватара пользователя
Ну, видимо, 1993-го или конца 1992-го. Это хоть как-то её оправдывает.

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


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