2014 dxdy logo

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

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




 
 Размер минимального общего множителя
Сообщение10.05.2019, 13:06 
Аватара пользователя
Я изучаю физику (не математику), поэтому извините за промахи в терминологии.

Недавно у меня возник вопрос - какого размера должно быть число, которое делится на любой натуральный множитель от 2 до N включительно. В итоге получилась гипотеза, что натуральный логарифм этого "вседелящегося" числа стремится к N. Если результат давно известен - извиняюсь. По правилам форума, в этой ветке можно задавать вопросы, если не знаешь, стандартная ли задача.

В качестве генератора я использую Maxima, код в несколько строчек:
Код:
/* Проверочка на линейный закон для самых непростых чисел  */
load(functs)$
y:1;
with_stdout("lnlcm.out", for ix:1 thru 34999 do (
    y:lcm(y,ix),
    print(ix,1+float(log(bfloat(y))))
    )
);
/* конец программы */

Если запустить описанный выше скрипт, получаем отдельно текстовый файлик "lnlcm.out", в первом столбце которого N, а вот втором - натуральный логарифм числа, делящегося на все на натуральные делители, не превосходящие N. Обратите внимание на графике внизу, как ровно натуральный логарифм проходит через пересечения линий сетки. Если берём все делители от 1 до 35000, то и натуральный логарифм числа, делящегося на всё натуральное из интервала 2..35000, тоже будет очень близок к 35000. Впрочем, при любом раскладе хотелось бы доказать (или опровергнуть) самостоятельно. Если посоветуете книгу (учащую думать, а не справочник готовых ответов), буду признателен. Я бы тогда попробовал построить доказательство, хорошее-правильное, без кенгуриных прыжков, и здесь бы обсудили. Совпадение всё-таки непохоже на случайное.

Изображение

 
 
 
 Re: Размер минимального общего множителя
Сообщение10.05.2019, 13:29 
Эта последовательность есть в OEIS:A003418. Есть там и гипотеза об асимптотике, похожая на вашу:$|\ln a_n-n|<\sqrt{n}\ln^2 n$, правда, утверждается, что она эквивалентна гипотезе Римана. Можете попытаться доказать для начала более слабое утверждение, например, такое: $|\ln a_n-n|=o(n)$.

-- Пт май 10, 2019 13:32:23 --

Ах, да. Задача, конечно, относится к теории чисел, так что ищите учебники по ней. :-)

 
 
 
 Re: Размер минимального общего множителя
Сообщение10.05.2019, 13:38 
Добавлю, что оценка с $o(n)$ эквивалентна асимптотическому закону распределения простых чисел. Доказательство последнего нужно искать в учебниках по аналитической теории чисел. Например: Галочкин А.И., Нестеренко Ю.В., Шидловский А.Б. Введение в теорию чисел. М.: Изд-во МГУ, 1995.

 
 
 
 Re: Размер минимального общего множителя
Сообщение10.05.2019, 22:53 
Аватара пользователя
Sender, похоже, мне нашлось занятие. Есть ощущение, что оценку из OEIS, (которая $|\ln a_n-n|<\sqrt{n}\ln^2 n$), можно улучшить. Я понимаю, что первые 35 тысяч натуральных делителей - капля в море, и неизвестно, что там будет дальше. Но всё же оценка, кажется, растёт слишком быстро. Это, разумеется, личное субъективное ощущение, ничего больше.

Изображение Изображение

nnosipov, книгу по основам теории чисел разыскал, спасибо за подсказку.

Теперь надо немного подумать :|

 
 
 
 Re: Размер минимального общего множителя
Сообщение12.05.2019, 00:58 
Xmas в сообщении #1392253 писал(а):
Есть ощущение, что оценку из OEIS, (которая $|\ln a_n-n|<\sqrt{n}\ln^2 n$), можно улучшить.

Ну вы всё-таки почитайте ради интереса, что такое гипотеза Римана и насколько она проста в доказательстве. :-)
Sender в сообщении #1392137 писал(а):
утверждается, что она эквивалентна гипотезе Римана.

 
 
 
 Re: Размер минимального общего множителя
Сообщение12.05.2019, 08:56 
Аватара пользователя
Sender, с моим "уровнем" в теории чисел я, предположительно, неспособен доказать не менее 99% даже её известных теорем :-) Не говоря уже о недоказанных гипотезах, которые и от профессионалов-то ускользают. Я, собственно, заинтересовался этим вопросом для того, чтобы оценить площадь "белых пятен" в моих познаниях. Если их удастся чуть уменьшить - будет уже хорошо.

Экспериментально обнаружилось ещё одно свойство. Берём $a_n$ - число, делящееся на любое натуральное число до $n$ включительно. Берём $b_n$ - произведение всех простых чисел, не превосходящих $n$. Итог выглядит так, словно отношение их логарифмов в пределе на бесконечности равно единице. Вот график отношения логарифмов для $n$ до 100 000:

Изображение

Ниже единицы график опуститься не может никак, поскольку в $a_n$ имеются все простые числа, и некоторые со степенями. В $b_n$ те же простые числа, но в степени 1. Физико-интуитивное ощущение такое, словно небольшие составные числа "вынуждены" повторно использовать одни и те же простые числа из-за нехватки строительного материала. Позже, когда выбор расширяется, составные числа в основном образуются из разных простых чисел, взятых по одному разу. Напрашивается связь с энтропией, в которой логарифм - тоже одно из действующих лиц.

Надеюсь на продолжение беседы.

 
 
 
 Re: Размер минимального общего множителя
Сообщение12.05.2019, 09:33 
Xmas в сообщении #1392466 писал(а):
Экспериментально обнаружилось ещё одно свойство. Берём $a_n$ - число, делящееся на любое натуральное число до $n$ включительно. Берём $b_n$ - произведение всех простых чисел, не превосходящих $n$. Итог выглядит так, словно отношение их логарифмов в пределе на бесконечности равно единице.
Оценка $\ln{b_n}=n+o(n)$ также эквивалентна асимптотическому закону распределения простых чисел.

 
 
 
 Re: Размер минимального общего множителя
Сообщение12.05.2019, 11:39 
Аватара пользователя
Причём соотношение $\displaystyle\lim_{n\to\infty}\frac{\ln a_n}{\ln b_n}=1$ доказать гораздо проще, чем азрпч, ввиду тривиальных неравенств $\ln b_n\leqslant\ln a_n\leqslant\ln b_n +n^{1/2}\ln n$ (из оценок Чебышёва следует даже $\ln a_n=\ln b_n+O\left(n^{1/2}\right)$).
Кстати, логарифмы $a_n$ и $b_n$ — это стандартные функции Чебышёва: $\ln a_n=\psi(n)$, $\ln b_n=\theta(n)$.

 
 
 
 Re: Размер минимального общего множителя
Сообщение12.05.2019, 12:53 
Ну вот наконец назвали вещи своими именами. А то человек изобретает велосипед и прямо идёт по стопам Чебышева :-) Посмотрите асимптотические оценки Чебышева и функции Чебышева в теории чисел.

 
 
 
 Re: Размер минимального общего множителя
Сообщение12.05.2019, 17:02 
Логарифм наименьшего общего кратного ( первой вашей функции) есть пси- функция Чебышева. Поздно увидел RIP уже написал.

 
 
 
 Re: Размер минимального общего множителя
Сообщение12.05.2019, 17:22 
Аватара пользователя
Уважаемые участники, ну вот так сложились обстоятельства. Видимо, я похож на первоклассника, который первый раз увидел таблицу умножения и сообщает всем про своё открытие коммутативности умножения натуральных чисел. Хотелось бы, с вашей помощью, последовательно добраться до места, где начинается "глубина", на которую не рискуют нырять даже киты. В теории чисел, как представляется, подводная пропасть начинается совсем близко от берега.

Добавлено: о существовании пси-функции Чебышёва я не знал до момента публикации этой темы. Теперь услышал, и даже имею учебник по основам теории чисел, где она есть, но за сутки я до неё не добрался. Так что от форума прямая конкретная польза :-) Спасибо!

 
 
 
 Re: Размер минимального общего множителя
Сообщение13.05.2019, 13:07 
Xmas Обратите внимание, что обе функции Чебышева являются суммой других арифметических функций. К сумматорным арифметическим функциям также относятся функции Мертенса, Лиувилля, количества простых чисел и другие. На оценке асимптотик указанных функций основан асимптотический закон простых чисел, о котором говорили выше. На оценке асимптотик отклонений указанных функций основано большинство эквивалентных формулировок Гипотезы Римана, о которой.также говорилось выше. Погуглите сумматорные арифметические функции.

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


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