PP wrote: Насчет 1/3 это Хайдук настаивает, а я как раз сомневаюсь. Среднее количество множителей в числе с ростом N растет очень-очень медленно, видимо, как двойной логарифм. Поэтому, чтобы в среднем число имело 1000 простых множителей (не обязательно разных), необходимо N просто несусветной величины. Даже просто число N = 2¹⁰⁰⁰ колоссально велико. Я провел эксперимент со случайной выборкой в 100 тысяч чисел из N = 10 млн чисел. Среди этих 100 000 чисел оказалось всего 8 чисел с числом множителей, превосходящим не то что 1000, а всего 15 (правда, этих множителей и не может быть больше log₂ N = 23):

2¹⁴х13х29,
2¹⁵х5х31,
2¹²х3²х5х43,
2¹⁴х3х11,
2¹⁶х47,
2¹²х5х7³,
2¹³х3⁴х11,
2¹⁴х5х47.

Взял N = 100 млн и 1000 случайных чисел, нашлось всего одно число, у которого число множителей больше 15: 2¹²х3х5х7х137.

Проблема в том, что прежде я завожу массив длиною N, чтобы найти в нем все простые числа методом решета. И уже N = 1 миллиард не влезает моему компьютеру в память.

я исхожу из того, что любые разложения с любыми степенями можно повторить любыми другими простыми множителями, благо бесконечность натуральных стерпит все ; как-будто подобные вопросы не стОят утруждаться, НЕ "существенные", так сказать

Хайдук wrote: Мы работаем не сразу с бесконечностью, но с конечным отрезком и только потом переходим к бесконечности. А с конечным отрезком этот номер с повторением не проходит.

самоед2 wrote: Так точно ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE...9A%D0%B0%D1%86%D0%B0
самоед2 wrote: А зачем. Разве нет готовых таблиц? Но да, я посмотрел длиной в тысячу нереально конечно получается. Видимо числено не пощупать эту задачу.

PP wrote: Я, правда, имею в виду ВСЕ простые множители, с учетом их кратности, а не только различные (в теореме по ссылке). Всех, понятно, больше, чем различных, но рост все равно, видимо, как повторный логарифм будет. И программа для различных будет работать быстрее, поскольку делить для проверки на простое число достаточно будет один раз, а не пока делится. То, что именно ВСЕ, - это мне важно.

PP wrote: там уже пощупали что можно, тот же Эндрю Одлызко давно кружит компом вокруг гипотезы Римана . Недаром как раз трудность нахождения простых множителей больших чисел обеспечивает шифрование номеров кредитных карточек и вообще всего тайного трафика по Интернету. Не знаю что будет, когда додумаются до квантового компа, однако: ведь квантовый алгоритм нахождения простых множителей сих уже состряпан и с нетерпением выжидает остепенения такой же железяки

самоед2 wrote: ... для чего?

самоед2 wrote: что не проходит это ясно, зато царь Хаос в формировании натуральных из простых подавляет кромешностью: к примеру, какие из меньших N простых состряпывают НЕ превосходящие N числа?

Хайдук wrote: Чтобы ответить на вопрос: если каждое простое число покрашено так, как покрашено, то какого цвета натуральный ряд в целом? Такого же цвета, как и множество простых чисел, или другого?

всегда ли сможете определить общий цвет, несмотря на повторения цветов отдельных простых?

З.Ы. не знаю какое отношение к математике может поиметь такое раскрашивание...

Чтобы определить цвет в целом, нужно знать доли, или веса, его составляющих (базовых цветов красный - зеленый - синий). И все повторы чисел входят в вес.

Можете ничего не раскрашивать, а обходиться 0, -1 и +1. А операцию их "смешения" обозначать *. Правда, веса все равно придется рассматривать. Да, все это можно сформулировать в терминах барицентрических координат.

самоед2 wrote: ну да, матемАтиками слывём все-таки

самоед2 wrote: На этот счет есть другая теорема.

Хайдук wrote: самоед2 wrote: поскольку простые можно покрасить произвольным образом произвольным числом цветов, то как-будто лучше поставить вопрос так: какой будет (асимтотическая) доля натуральных с некоторым фиксированным простым в представлении произведением простых?

Первое натуральное с простым [tex]p[/tex] в разложении простыми будет [tex]2p[/tex]. Дальше простое [tex]p[/tex] будет строить/помечать "свои" натуральные НЕ хуже других простых, меньших или бОльших; у [tex]p[/tex] НЕ будет только шанса построить лишь конечное число натуральных меньших [tex]2p[/tex], что асимптотическую долю "своих" натуральных НЕ колышет, однако. Вопрос в том, можно ли полагать, что доли такие для любых простых будут одинаковыми?

З.Ы. Харди с Рамануджаном и Литтлвудом развлекались на досуге подобными задачками

самоед2 wrote: PP wrote: какая?

ОказываетсяХайдук wrote: Да, правильно. Оказывается, доля конкретного р на отрезке [1, N] асимптотически равна 1/(p - 1). Ряд из этих слагаемых расходится, конечно. Но это не беда, беда не это.

кто такая эта доля 1/(p - 1), самоед, я же поимел в виду все те бесконечно многие натуральные, чьим множителем простое p является? такие доли складывать нельзя, ибо пересекаются общими натуральными

Хайдук wrote:
Возьмем, например, простое число р = 23. Среди натуральных чисел до N = 1 млн, 10 млн, 100 млн, 1000 млн оно в качестве множителя содержится соответственно

45453, 454542, 4545451, 45454542 раза,

т.е. при N, стремящемся к бесконечности, это будет 454545454545... от 10000000000000..., или 1/22 = 1/(р - 1). И так для любого простого р.

это повторение группы 45 застает меня врасплох, неужели 1/(p - 1) доказано?

Хайдук wrote: Я этого нигде не нашел, а просто проверил на компьютере. Это очень легко проверяется. Берешь, допустим, N = 1 000 000 000 и простое р = 997. И прямо делишь каждое n от р до N на р, пока делится без остатка, одновременно увеличивая на 1 счетчик. А в завершение делишь на этот счетчик само N и получаешь 996,000063744004 = р - 1. Всего за 25 секунд.

Теперь бы надо оценить погрешность этого приближения, и тогда можно считать искомые доли опосредованно, просто суммируя нужный ряд, хотя считать можно и без оценки погрешности, конечно. Правда, ряд из этих 1/(р - 1) расходится. Но нам-то нужен не он сам, а доли от него. И вся проблема только в том, что расходится он очень-очень медленно, как повторный логарифм, поэтому нужно иметь много-много простых чисел, у меня же их всего примерно 10 миллионов, маловато.

Вы меня удивляете, самоед, как-бы через чур беспечным, что ли, отношением к шлепанью экспериментам с компом . Как раз с простыми нужно быть особо осторожным, потому что они выпрыгивают случайно с ростом N, а также нужна огромная, ущучивающая даже компы численная статистика. В частности, доли 1/(p - 1) выглядят довольно подозрительно, дабы спешить с обзыванием их асимптотическими: асимптотику компом НЕ состряпаешь, её приходится (строго) доказывать

чёрт, видимо я забыл про "неторопливые, ползущие" (вслед за скромным +1) аддитивные свойства натуральных . Большие простые множители будут перепрыгивать над такими же большими сворами натуральных, кои можно состряпать произведениями лишь меньших простых; стало быть, чем бОльше простое, тем меньше будет доля натуральных им (как множителем) "построенных"

самоед2 wrote: откуда пришло в башку делить N на счётчик, а не наоборот? ведь наоборот получите как раз долю, а так хз что получаете, хр*н какой-то встал чуть ниже пояса исходного простого. И даже округляете, не моргнуф, 996,000063744004 = р - 1. Ничего себе "математика" у Вас, однако...

самоед2 wrote: зачем суммировать 1/(р - 1), когда эти эмпирические доли НЕ чистые и наверняка пересекаются на общих натуральных?

Хайдук wrote: Пару слов насчет точности. Я просчитал искомые доли для log₁₀ N = 4 +/- 2 двумя способами и приблизил эти доли гиперболами. Первым способом подсчитал их непосредственно, они более светлые, а вторым - опосредованно, суммируя слагаемые 1/(р - 1). Разница, как мы видим, невеликая. Грубо, округляя до сотых, получаем асимптотические доли красных, зеленых и синих простых множителей соответственно: 0.25, 0.44 и 0.31. А в целом натуральный ряд, с данной точностью, выходит оттенка RGB(255, 249, 212) = #FFF9D4, не буду пока изображать его явно.

все это вызывает улыбку, самоед, видимо не имеете даже мало-мальского представления о том, что такое (логически выдержанная) математика . Находите персоналкой некоторые локальные (для пары-другой милльярдов натуральных) приближения и без доли сомнения объявляете их якобы асимптотическими на всю необозримую бесконечность

Хайдук wrote:
"Логически выдержанная" математика в таких случаях не обзывается, а приводит контрпример. Приведите контрпример.

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

самоед, поиск и прикидки компом способствуют выработке всего лишь правдоподобных гипотез насчет асимптотического поведения бесчисленных простых. На бесконечности комп бессилен и потому только башка с логикой могут правильно прикинуть что там будет . Тогда можно будет вычислить (обычно сходящимися методами) асимптотические значения, но НЕ сосчитать их перебором/проверкой (сколь угодно) больших массивов чисел

самоед2 wrote: а когда учитывать-то будем кратность/степени простых множителей для каждого натурального?

Хайдук wrote: При непосредственном подсчете мы учитываем это автоматически, а при опосредованном подсчете кратность учитывается слагаемым 1/(р - 1), смысл которого именно в этой кратности и состоит.

Изменил программу нахождения простых чисел. Работает в 15-20 раз медленнее, зато требует в 10 раз меньше памяти.