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


Содержание

MM180

Конкурсная задача ММ180 (13 баллов)

Назовем натуральное число «трижды нечетным», если само число, сумма его делителей и сумма делителей суммы его делителей нечетны. Может ли «трижды нечетное» число быть кратно 821?

Решение

Приведу решение Олега Полубасова.

Обсуждение

Эта задачка - побочный продукт другой, сформулированной в обсуждении ММ141. В попытке отыскать натуральные n>1, для которых 2σ(σ(σ(n)))<3n и возникли «трижды нечетные числа». Трудность задачи отыскания чисел, нарушающих «правило трех сигм» :-) вызвана следующими обстоятельствами: Пусть искомое n кратно 3. Тогда n = 9m (для нечетности σ(n) число n должно быть кратно 9). Если (m,3) = 1, то σ(n)≥13σ(m). Тогда уже σ(σ(n))>14σ(m)>1.5n. Аналогичная оценка проходит и для случая, когда n кратно большей четной степени 3.
Значит, искомое n не должно быть кратно 3.
Точно так же σ(n) не должно быть кратно 3.
Но как это обеспечить? Как известно, искомое n должно быть произведением четных степеней простых чисел. Однако, если среди сомножителей будет хотя бы один вида p2, где p≡1(mod3), σ(n) станет кратным трем.

Один способ справиться с указанной бедой - допускать в n исключительно сомножители вида p2, где p≡2(mod3). Но для p, сравнимых с 2 по модулю 3, σ(p2) будет сравнимо с 1. Подобрав другие сомножители так, чтобы σ(p2) вошло в разложение σ(n) во второй степени мы инициируем появление множителя 3 у σ(σ(n)), что не оставляет практических шансов на выполнение искомого неравенства. Я пытался найти такие n, что все простые множители входят в разложение σ(n) в степенях, не сравнимых 2 по модулю 3, но тщетно.

Другой способ - изначально рассматривать такие n, в разложение которых простые множители входят не во вторых, а в бОльших четных степенях. Но тогда простые множители σ(n) очень быстро растут и к ним очень тяжело подбирать пары, чтобы сделать σ(n) квадратом. Кроме того, это никак не гарантирует от появления множителя 3 у σ(σ(n)).

Некоторые участники высказали мнение, что цена ММ180 завышена. Вполне допускаю, что так оно и есть: я подсознательно спроецировал на нее усилия и потуги, кратко описанные выше , но имеющие к ММ180 лишь косвенное отношение.

Однако, вернемся к ММ180. Откуда взялось число 821? Дело в том, что трижды нечетные числа представлены в OEIS. Это нечетные члены эверестовской последовательности A008848. 821 - наименьший простой множитель, отсутствующий в A008848 и входящий в трижды нечетные из моей коллекции.

Приведу несколько рекордных трижды нечетных чисел, кратных 821: Самое большое -
2153829155085255043614891212240804954296290781551228459130025646030373396031813892179848131295024231966337511684848286216390330422 798784638792856220500360869569340697854169364206477035521273548548065039909123747445604084225. В этом монстре 223 десятичных знака. Самым маленьким (не в смысле величины, а в смысле количества простых сомножителей в n) из найденных является число 6888943998606321712473704540351139273889 = 8212·24588672·27061672·151932.

Как и ряд участников, я тоже попытался найти трижды нечетные числа, кратные 821, в каноническом разложении которых присутствуют лишь два сомножителя, т.е найти решение диофантова уравнения p2+p+1=(8212+821+1)z2, где p - простое, а z>1. Это уравнение легко (домножением на 4 и заменой y=2z, x=2p+1 сводится к обобщенному уравнению Пелля x2-674863y2=-3 (1). В отличие от обычного уравнения Пелля, обобщенное разрешимо не всегда. Но это замечание не относится к уравнениям вида x2-σ(q2)y2=-3. Ведь у них всегда есть тривиальное решение x=q, y=1, а значит и бесконечное множество решений.

В частности, для уравнения (1) имеется целых две бесконечных серии решений:
xi+1=6809342162640134046028986727xi+5593877694950442290679646272108yi
yi+1=8288908556181687676876116xi+6809342162640134046028986727yi
Для одной серии x0=6216683144343733667351755, y0=7567473755238950514866. В этой серии нет подходящих решений, поскольку (xi-1)/2 всегда кратно 3. Для другой серии x0=1643, y0=2. В ней не наблюдается каких либо закономерностей среди делителей чисел (xi-1)/2 и я надеялся обнаружить среди решений подходящие. Но проверив первые 600 чисел (xi-1)/2 (последние имеют по несколько десятков тысяч десятичных цифр) не нашел ни одного простого.

Решая аналогичные уравнения, но не для числа 821, а, например, для чисел 7, 13, 31, 37 (для 37 удалось найти сразу 4 подходящих решения) можно получить трижды нечетные числа, являющиеся произведением квадратов двух простых чисел. Например, 103840047102169317666339040296372132 или 21107814372372. Все простые числа, для которых нашлось решение, имеют вид 6k+1. У меня уже было сложилось впечатление, что это вовсе не случайно, а специально для того чтобы затруднить поиск чисел, для которых 2σ(σ(σ(n)))<3n :-) Но в этот момент я нашел нетривиальное решение уравнения x2=σ(592)y2 с простым (x-1)/2. Найти точное значение σ(σ(σ(n)))/n для 2433-значного n я не смог, но оценка ≈1.64 - рекорд для трижды нечетных n.

Под занавес обсуждения выделю вопросы, связанные с ММ141 и ММ180, ответы на которые пока не удалось найти:

1. Является ли равенство σ(34)=112 единственным нетривиальным примером соотношения σ(pk)=qs?
(Кое-что, относящееся к этому вопросу есть в OEIS). 2. Существуют ли n>1, для которых 2σ(σ(σ(n)))<3n?
3. Существуют ли «четырежды нечетные» числа?

Награды

За ММ180 Олег Полубасов получает 15 призовых баллов, Виктор Филимоненков, Анатолий Казмерчук, Алексей Волошин, Николай Дерюгин, Евгений Гужавин и Сергей Половинкин - по 13 призовых баллов.

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


 

 


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

marathon/problem_180.txt · Последние изменения: 2019/08/09 08:56 — letsko
Powered by DokuWiki  ·  УКЦ ВГПУ 2006