Математический факультетИнформация для студентовЭлектронная библиотека
Карта сайтаКарта сайта
Недавние измененияНедавние изменения
ПоискПоиск
  
Вы посетилиВы посетили
История страницыИстория страницы
  
Вход/выходВход


Содержание

71

Результат пpедлагаемой задачи учитывается дважды:
В Большом Маpафоне и в мини-конкуpсе арифметических задач.

Конкурсная задача №71 (А-1) (4 балла)

Назовем n-значное натуральное число «замечательным», если оно равно сумме n-х степеней своих цифр. Конечно ли множеcтво замечательных чисел?

Пpимечание:
Система счисления десятичная.

Решение

Самое маленькое n-значное число больше чем 10(n-1). Сумма n-х степеней цифр n-значного числа не превосходит n*9n.
Неравенство n*9^n < 10(n-1) равносильно неравенству 9*n < (10/9)(n-1). Поскольку показательная функция с основанием, большим 1, растет быстрее линейной, последнее неравенство верно для всех достаточно больших n (более точно, для всех натуральных n, больших 60). Таким образом, множество замечательных чисел конечно.

Обсуждение

Разумеется, оценка максимально возможного числа цифр замечательного числа, приведенная в решении, завышена. Ведь для чисел, значность которых превышает 60, уже самое маленькое из чисел с данным n превышает сумму n-х степеней цифр самого большого n-значного числа.

Предлагая эту задачу, я рассчитывал, что марафонцы не только докажут конечность множества замечательных чисел, но и перечислят все эти числа. Явно ставить вопрос о нахождении всех замечательных чисел я не стал, чтобы не превращать задачу из несложной математической в громоздкую (по времени расчетов) информатическую.
Однако к моменту обнародования задачи у меня была готова программка для нахождения замечательных чисел и имелась уверенность в том, что она завершит перебор за реальное (хотя и достаточно большое) время.

Но завершить перебор я не успел. В первые же часы после публикации Константин Кноп прислал мне ссылку на mathworld.wolfram.com (между прочим, часто посещаемый мной ресурс), где подробно обсуждаются замечательные числа. На самом деле, они называются нарциссическими числами или числами Армстронга (правда, иногда эти названия применяют лишь к трехзначным замечательным числам). Там же приведен и полный перечень этих чисел. Вот он:

n base-10 n-narcissistic numbers
1 1, 2, 3, 4, 5, 6, 7, 8, 9
3 153, 370, 371, 407
4 1634, 8208, 9474
5 54748, 92727, 93084
6 548834
7 1741725, 4210818, 9800817, 9926315
8 24678050, 24678051, 88593477
9 146511208, 472335975, 534494836, 912985153
10 4679307774
11 32164049650, 32164049651, 40028394225, 42678290603, 44708635679, 49388550606, 82693916578, 94204591914
14 28116440335967
16 4338281769391370, 4338281769391371
17 21897142587612075, 35641594208964132, 35875699062250035
19 1517841543307505039, 3289582984443187032, 4498128791164624869, 4929273885928088826
20 63105425988599693916
21 128468643043731391252, 449177399146038697307
23 21887696841122916288858, 27879694893054074471405, 27907865009977052567814, 28361281321319229463398, 35452590104031691935943
24 174088005938065293023722, 188451485447897896036875, 239313664430041569350093
25 1550475334214501539088894, 1553242162893771850669378, 3706907995955475988644380, 3706907995955475988644381, 4422095118095899619457938
27 121204998563613372405438066, 121270696006801314328439376, 128851796696487777842012787, 174650464499531377631639254, 177265453171792792366489765
29 14607640612971980372614873089, 19008174136254279995012734740, 19008174136254279995012734741, 23866716435523975980390369295
31 1145037275765491025924292050346, 1927890457142960697580636236639, 2309092682616190307509695338915
32 17333509997782249308725103962772
33 186709961001538790100634132976990, 186709961001538790100634132976991
34 1122763285329372541592822900204593
35 12639369517103790328947807201478392, 12679937780272278566303885594196922
37 1219167219625434121569735803609966019
38 12815792078366059955099770545296129367
39 115132219018763992565095597973971522400, 115132219018763992565095597973971522401

Этот же список можно обнаружить в онлайновой энциклопедии целочисленных последовательностей (http://www.research.att.com/~njas/sequences/A005188), а также во многих других местах.

В общем, я в очередной раз «изобрел велосипед».
Конечно, прежде чем предлагать эту задачку, мне следовало нбрать в поисковике, например, число 28116440335967 и получить несколько сотен ссылок на числа Армстронга.
Слабым оправданием мне может служить лишь такой факт:
Лет пять назад я несколько раз постил в RU.GOLOVOLOMKA письмо, в котором допытывался у All'а, чем интересна четверка чисел «153, 370, 371, 407». Но никто из подписчиков (а пять лет назад в RU.GOLOVOLOMKA крутилось народу поболее, чем сейчас) так и не отозвался.

Разумеется, 10, как основание системы счисления не уникально.
Вот перечень всех замечательных чисел для небольших оснований системы счисления b (но записанных в десятичной системе):

b base-b narcissistic numbers
2 1
3 1, 2, 5, 8, 17
4 1, 2, 3, 28, 29, 35, 43, 55, 62, 83, 243
5 1, 2, 3, 4, 13, 18, 28, 118, 289, 353, 419, 4890, 4891, 9113

Ясно, что однозначные числа будут замечательными в любой системе счисления.
Для b = 2 иных замечательных чисел не существует.

Возникает вопрос: есть ли другие натуральные основания b, для которых не существует неоднозначных замечательных чисел?

И еще вопрос: существуют ли натуральные числа, являющиеся неоднозначными замечательными сразу для нескольких оснований?

Награды

За правильное решение этой задачи Константин Кноп и Влад Франк получают по 5 призовых баллов. Они (разными путями) получили полный список замечательных чисел.
Сергей Аракчеев, Сергей Беляев, Дмитрий Бобровский, Андрей Богданов, Иван Козначеев, Алекс Кочарин, Евгений Машеров, Дмитрий Милосердов, Олег Полубасов, Виктор Филимоненков и Анатолий Казмерчук получают по 4 призовых балла.
За некоторые соображения по решению Стас Грицюк получает 1 призовой балл.

Эстетическая оценка задачи - 2.4 балла


 

 


Страница: [[marathon:problem_71]]

marathon/problem_71.txt · Последние изменения: 2015/10/20 10:26 — letsko
Powered by DokuWiki  ·  УКЦ ВГПУ 2006