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


Содержание

MM77

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

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

Каждое из n натуральных чисел, идущих подряд, имеет ровно k натуральных делителей. Какое наибольшее значение может принимать n, если:
1) k = 2;
2) k = 3;
3) k = 4;
4) k = 6;
5) k = 8?

Решение

Обозначим через t(n) количество натуральных делителей натурального числа n, а через d(k) наибольшее количество идущих подряд натуральных чисел, имеющих ровно k делителей.
Известно (и тривиально выводится), что t(n) равно произведению увеличенных на 1 показателей степени различных простых множителей в каноническом разложении n.

1. k = 2
Ровно два натуральных делителя имеют простые числа и только они. Но среди простых есть лишь одно четное - 2. Поскольку 3 тоже простое, d(2) = 2.

2. k = 3
Ровно 3 натуральных делителя имеют квадраты простых чисел. Но они не могут идти подряд. Поэтому d(3) = 1.

3. k = 4
Среди четырех идущих подряд натуральных чисел одно делится на 4. Если оно не делится на 8, то t(n) кратно 3 и не может равняться 4. Если же оно кратно 8, но не равно 8, то t(n) больше 4. Соседи числа 8 не имеют четырех натуральных делителей. Поэтому d(4) < 4. В то же время, числа 33, 34, 35 имеют по 4 натуральных делителя, поэтому d(4) = 3.

5. k = 8
Среди восьми идущих подряд натуральных чисел одно делится на 4, но не делится на 8. Количество делителей такого числа кратно 3 и не может равняться 8. Поэтому d(8) < 8. С помощью небольшого комьпютерного перебора легко найти 7 идущих подряд чисел, имеющих ровно по 8 делитетелей. Например,
171893 = 19*83*109;
171894 = 2*3*28649;
171895 = 5*31*1109;
171896 = 23*21487;
171897 = 3*11*5209;
171898 = 2*61*1409;
171899 = 7*13*1889.
Таким образом, d(8) = 7.

4. k = 6
Самый трудный пункт.
Среди шести идущих подряд натуральных чисел - три четных. Если одно из них кратно 8, то оно не может иметь ровно 6 делителей (исключение состваляет число 32, но его соседи не имеют по шесть делителей). Если же кратных 8 нет, то четные числа должны иметь вид 2p2, 4q, 2r2, где p,q,r - простые. Но квадраты простых чисел не могут отличаться на 4. Поэтому d(6) < 6.

Допустим, числа n, n+1, n+2, n+3, n+4 имеют по 6 делителей. Тогда n+1 и n+3 - четны и одно из них имеет вид 2p2, а другое - 4q. Докажем, что кратно четырем именно n+3.
В самом деле, если наоборот 4q +2 = 2p2, то 2q = (p-1)*(p+1), что невозможно при нечетых простых p и q.

Далее, докажем, что n+2 должно быть кратно 3.
Действительно, если n+2 не кратно 3, то кратно 3 одно из четных чисел, но рассмотрение соседей чисел 18 и 12, показыает, что они не образуют искомых пятерок.

Далее, n+4 обязано быть кратно 5.
Рассмотрение соседей чисел 50, 75, 45, 3125 и 20 показывает, n+1, n+2 и n+3 не кратны 5. Если допустить, что n кратно 5, то 2p2 == 1 (mod 5) и p2 == 3 (mod 5). Но 3 не является квадратичным вычетом по модулю 5.

Наконец, несложно убедиться, что искомая пятерка не может содержать пятых степеней простых чисел.
В самом деле, соседи чисел 243 и 3125 не дают искомых пятерок (хотя 243 входит в четверку). Если же n = s5, то 2p2 = (s-1)*(s4+s3+s2+s+1), что невозможно для простого s, большего 3.

Таким образом, искомая пятерка имеет вид sv2, 2p2, 3r2 (9r), 4q, 5u2 (25u), где p,q,r,s,u,v - простые числа, бОльшие 5.

Учитывая, что большое натуральное с гораздо большей вероятностью имеет вид 9r, чем 3r2, где r простое, а 25u встречается чаще 5u2, я искал пятерки вида sv2, 2p2, 9r, 4q, 25u.

Вот наименьшая из них:
10093613546512321 = 72*205992113194129;
10093613546512322 = 2*710408812;
10093613546512323 = 32*1121512616279147;
10093613546512324 = 22*2523403386628081;
10093613546512325 = 52*403744541860493.

В обсуждении показано, как искать такие пятерки, используя совсем небольшой перебор.

Итак d(6) = 5.

Обсуждение

Далеко не впервые в истории Марафона придуманная мной задача оказалась придуманной задолго до меня. Как указал мне Константин Кноп, проблема нахождения d(n) не нова. В частности, Эрдёшем еще в начале 50-х годов прошлого века высказана гипотеза (на сегодняшний день не поменявшая своего статуса), что для любого натурального n найдется k такое, что d(k) >= n. Подробности можно найти на http://www.primepuzzles.net/problems/prob_020.htm или на http://www.cosc.brocku.ca/~duentsch/archive/equidiv.pdf
Самая длинная из известных на сегодяшний день цепочка идущих подряд натуральных чисел, имеющих одинаковое число делителей, начинается с числа 17796126877482329126044. Это число и последующие восемь имеют по 48 делителей каждое.

Ясно, что для всех нечетных k d(k) = 1. Точные значения d(k) для четных известны лишь для некоторых k. Это k, рассмотренные в задаче. Кроме того известно, что d(10) = d(14) = 3, d(16) = 7.
Для других небольших четных k известны лишь оценки сверху. Так, доказано, что d(12) не превышает 23. В то же время самая длинная из известных цепочек чисел, имеющих по 12 делителей, состоит всего из 5 чисел.


Вернусь к алгоритмам поиска пятерок чисел, имеющих ровно по 6 делителей. Моя цель - доказать, что это в гораздо большей степени математика, нежели информатика.
Будем искать пятерку чисел вида 49s, 2p2, 9r, 4q, 25u
Для ускорения поиска можно наступать только на те p, для которых число n = 2p2 -1 будет кратно 49, n+2 - кратно 9, n+3 - кратно 4, а n+4 - кратно 25. Число n+3 = 2p2 + 2 будет кратно 4 при любом нечетном p.
Сравнение 2p2 - 1 == 0 (mod 49) имеет два решения p == 5 (49) и p == 44 (49).
Аналогично p == 2 (9) и p == 7 (9) - решения сравнения 2p2 + 1 == 0 (mod 9),
а p == 6 (9) и p == 19 (25) - решения сравнения 2p2 + 3 == 0 (mod 25)
Китайская теорема об остатках гарантирует нам на каждом участке натурального ряда длиной 22050 = 2*9*25*49 восемь (два в кубе) подходящих p.
Например, для p == 1 (2), p == 5 (49), p == 2 (9), p == 6 (25) получаем p == 1181 (22050).
В общем случае имеем p == pp (22050), где pp берется из A = {1181,3719,4219,9119,12931,17831,18331,20869}.
Значит, искомые p имеют вид 22050k+pp. Соответственно s = (2(22050+pp)2 - 1)/49;
r = (2(22050k+pp)2 + 1)/9;
q = (2(22050k+pp)2 + 2)/4;
u = (2(22050k+pp)2 - 1)/25.
Остается подобрать такое k, чтобы p(k), q(k), r(k), s(k) и u(k) одновременно были простыми.
Наименьшее такое k = 3221 (совсем маленькое число для компьютерного перебора) достигается при pp = 17831 и дает пятерку, указанную в решении.

Приведу наименьшие пятерки для других значений pp:

pp = 4219, n = 14414905793929921 (k = 3850)
72*294181750896529, 2*848967192, 32*1601656199325547, 22*3603726448482481, 52*576596231757197;

pp = 1181, n = 266667848769941521 (k = 16560)
72*5442200995304929, 2*3651491812, 32*29629760974437947, 22*66666962192485381, 52*10666713950797661;

pp = 20869, n = 562672865058083521 (k = 24054)
72*11483119695062929, 2*5304115692, 32*62519207228675947, 22*140668216264520881, 52*22506914602323341;

pp = 9119, n = 1841337567664174321 (k = 43515)
72*37578317707432129, 2*9595148692, 32*204593063073797147, 22*460334391916043581, 52*73653502706566973;

pp = 12931, n = 2737837351207392721 (k = 53061)
72*55874231657293729, 2*11700079812, 32*304204150134154747, 22*684459337801848181, 52*109513494048295709.

pp = 3719, n = 4993613853242910721 (k = 71661)
72*101910486800875729, 2*15801287692, 32*554845983693656747, 22*1248403463310727681, 52*199744554129716429.

pp = 18331, n = 5174116847290255921 (k = 72944)
72*105594221373270529, 2*16084335312, 32*574901871921139547, 22*1293529211822563981, 5*2*206964673891610237.

Для построения пятерок, у которых первое число не кратно 7, достаточно заменить модуль в сравнении 2p2 - 1 == 0 (mod 49). Главное, чтобы соответствующее сравнение было разрешимо.

Вот примеры таких пятерок:

172*82576713384315889, 2*34543212192, 32*2651630018674143547, 22*5966167542016822981, 52*954586806722691677.

232*2522652702286041649, 2*258310208812, 32*148275919945479559147, 22*333620819877329008081, 52*53379331180372641293.

312*21284060796218161, 2*31979667312, 32*2272664713907294747, 22*5113495606291413181, 52*818159297006626109.

472*5670898437755243569, 2*791423232192, 32*1391890516555703671547, 22*3131753662250333260981, 52*501080585960053321757.

1032*725691722009087872369, 2*19619968754812, 32*855429275421601470884747, 22*1924715869698603309490681, 52*307954539151776529518509.

А вот пятерка 41-значных монстров:

n = 97240500430391295011491324622290102308721 = 72*1984500008783495816561047441271226577729,
n+1 = 2*2205000004879719892692,
n+2 = 32*10804500047821255001276813846921122478747,
n+3 = 22*24310125107597823752872831155572525577181,
n+4 = 52*3889620017215651800459652984891604092349.

Для построения этой пятерки не применялось какой-либо специальной техники. Просто стартовое k было достаточно велико.

Я пробовал обнаружить пятерки, в которых третье число имеет вид 3r2 либо пятое имеет вид 5u2. Для этого я решил диофантовы уравнения 2p2 + 1 = 3r2 и 2p2 + 3 = 5u2.
Множество натуральных решений первого из этих уравнений задается начальными значениями p_0 = r_0 = 1 и рекуррентными соотношениями
p_{i+1} = 5*p_i + 6*r_i, r_{i+1} = 4*p_i + 5*r_i.
Множество решений второго уравнения является объединением двух серий, задаваемых одними и теми же рекуррентными соотношениями
p_{i+1} = 19*p_i + 30*u_i, u_{i+1} = 12*p_i + 19*u_i, но с разными парами начальных значений (1, 1) и (11, 7).
К сожалению, пары чисел, являющиеся решениями этих диофантовых уравнений, крайне редко состоят из двух простых чисел. Я нашел всего по одной такой паре для каждого уравнения, хотя были рассмотрены все решения, в которых числа не превосходят 10^5000 (сделать это было не так трудно, поскольку решения быстро растут).

Влад Франк нашел оценку сверху для d(k). Пусть m - наименьшее простое, не делящее k. Среди 2^m идущих подряд чисел обязательно найдется число n, делящееся на 2m-1, но не делящееся на 2m. Тогда t(n) не может равняться k. Поэтому d(k) < 2m.

В то же время Влад привел краткий набросок доказательства гипотезы Эрдёша о том, что при подходящем k, d(k) будет больше любого наперед заданного числа. Процесс построения нужной цепочки похож на описанный выше алгоритм для отыскания пятерок.
Гарантии существования значений k, при которых все значения всех нужных полиномов будут простыми, основано на гипотезе Бейтмана-Хорна, точнее на утверждении, вытекающем из этой гипотезы:
Пусть f_1(x), f_2(x),…, f_s(x) - неприводимые полиномы с целыми коэффициентами, такие что для любого простого p существует натуральное n, что p не делит значение произведения данных полиномов в точке x = n. Тогда существует такое k, что f_1(k), f_2(k),…, f_s(k) одновременно просты.
(Более того, из гипотезы Бейтмана-Хорна вытекает, что множество таких k бесконечно и даже имеет неулевую плотность в натуральном ряду.)
Что касается самой гипотезы, насколько я знаю (если же я чего-то не знаю, буду рад узнать), она остается гипотезой, но серьезные математики не сомневаются в ее справедливости.

Награды

За верное решение задачи и ее обобщение Влад Франк получает 11 призовых баллов. За правильное решение задачи Константин Кноп и Анатолий Казмерчук получают по 8 призовых баллов. За верные, но неполные (в разной степени) решения Олег Полубасов получает 7 призовых баллов, Виктор Филимоненков - 6 баллов, а Галина Крюкова - 5 баллов.

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


Приложение


 

 


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

marathon/problem_77.txt · Последние изменения: 2019/02/13 18:01 — letsko
Powered by DokuWiki  ·  УКЦ ВГПУ 2006