2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Размер минимального общего множителя
Сообщение10.05.2019, 13:06 
Аватара пользователя


18/12/17
126
Я изучаю физику (не математику), поэтому извините за промахи в терминологии.

Недавно у меня возник вопрос - какого размера должно быть число, которое делится на любой натуральный множитель от 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 


14/01/11
3042
Эта последовательность есть в 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 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Размер минимального общего множителя
Сообщение10.05.2019, 22:53 
Аватара пользователя


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

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

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

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

 Профиль  
                  
 
 Re: Размер минимального общего множителя
Сообщение12.05.2019, 00:58 


14/01/11
3042
Xmas в сообщении #1392253 писал(а):
Есть ощущение, что оценку из OEIS, (которая $|\ln a_n-n|<\sqrt{n}\ln^2 n$), можно улучшить.

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

 Профиль  
                  
 
 Re: Размер минимального общего множителя
Сообщение12.05.2019, 08:56 
Аватара пользователя


18/12/17
126
Sender, с моим "уровнем" в теории чисел я, предположительно, неспособен доказать не менее 99% даже её известных теорем :-) Не говоря уже о недоказанных гипотезах, которые и от профессионалов-то ускользают. Я, собственно, заинтересовался этим вопросом для того, чтобы оценить площадь "белых пятен" в моих познаниях. Если их удастся чуть уменьшить - будет уже хорошо.

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

Изображение

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

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

 Профиль  
                  
 
 Re: Размер минимального общего множителя
Сообщение12.05.2019, 09:33 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Размер минимального общего множителя
Сообщение12.05.2019, 11:39 
Заслуженный участник
Аватара пользователя


11/01/06
3826
Причём соотношение $\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 


23/02/12
3363
Ну вот наконец назвали вещи своими именами. А то человек изобретает велосипед и прямо идёт по стопам Чебышева :-) Посмотрите асимптотические оценки Чебышева и функции Чебышева в теории чисел.

 Профиль  
                  
 
 Re: Размер минимального общего множителя
Сообщение12.05.2019, 17:02 


23/02/12
3363
Логарифм наименьшего общего кратного ( первой вашей функции) есть пси- функция Чебышева. Поздно увидел RIP уже написал.

 Профиль  
                  
 
 Re: Размер минимального общего множителя
Сообщение12.05.2019, 17:22 
Аватара пользователя


18/12/17
126
Уважаемые участники, ну вот так сложились обстоятельства. Видимо, я похож на первоклассника, который первый раз увидел таблицу умножения и сообщает всем про своё открытие коммутативности умножения натуральных чисел. Хотелось бы, с вашей помощью, последовательно добраться до места, где начинается "глубина", на которую не рискуют нырять даже киты. В теории чисел, как представляется, подводная пропасть начинается совсем близко от берега.

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

 Профиль  
                  
 
 Re: Размер минимального общего множителя
Сообщение13.05.2019, 13:07 


23/02/12
3363
Xmas Обратите внимание, что обе функции Чебышева являются суммой других арифметических функций. К сумматорным арифметическим функциям также относятся функции Мертенса, Лиувилля, количества простых чисел и другие. На оценке асимптотик указанных функций основан асимптотический закон простых чисел, о котором говорили выше. На оценке асимптотик отклонений указанных функций основано большинство эквивалентных формулировок Гипотезы Римана, о которой.также говорилось выше. Погуглите сумматорные арифметические функции.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group