Головоломка Купца

Купец, который был среди паломников, отличался тем, что "курс экю высчитывать умел и знатно на размене наживался" и "... так искусно вел свои расчеты, Что пользовался ото всех почетом". Однажды утром, когда вся компания двигалась по дороге, Рыцарь и Сквайр, ехавшие рядом с Купцом, напомнили ему, что он все еще не порадовал компанию своей головоломкой.


- В самом деле? - оживился купец. - Тогда вот вам числовая головоломка, которую я предложу всей честной компании, когда мы остановимся отдохнуть. Сегодня утром нас движется по дороге тридцать человек. Мы можем двигаться один за другим, что называется, гуськом, или пара за парой, или тройка за тройкой, или пятерка за пятеркой, или шестерка за шестеркой, или десятка за десяткой, или, наконец, все тридцать в ряд. Ехать каким-либо иным способом, так, чтобы в каждом ряду всадников было поровну, мы не можем. А вот некая компания паломников способна ехать шестьюдесятью четырьмя способами. Скажите мне, сколько в этой компании должно быть паломников.
Купец, очевидно, имел в виду наименьшее число всадников, которые могут ехать шестьюдесятью четырьмя способами.

Ответ

Эта головоломка сводится к нахождению наименьшего числа, обладающего 64 делителями, включая 1 и само число. Таким наименьшим числом будет 7560. Следовательно, паломники могут ехать гуськом, пара за парой, тройка за тройкой, четверка за четверкой и т. д. 64 способами, причем последним способом будет 7560 всадников в ряд. Купец был осторожен, не упомянув, по какой дороге ехали всадники.
Для того чтобы найти число делителей данного числа N, положим


..., где a, b, c - простые числа. Тогда число делителей, куда включены 1 и само N, будет равно (p + 1) (q + 1) (r + 1)...
Таким образом, в случае головоломки Купца


степени - 3 3 1 1
следовательно, всего имеется 4х4х2х2= 64 делителя.
Чтобы найти наименьшее число с данным числом делителей, мы должны воспользоваться методом проб и ошибок. Однако важно порой следить за тем, чтобы число имело данное число делителей, но не большее. Например, наименьшим числом с 7 делителями будет 64, хотя 24 обладает 8 делителями, а тем самым и 7. Требование "не большее" в данном случае необязательно, поскольку не существует чисел, меньших 7560 и обладающих чис- лом делителей, превышающим 64.