Решето Сундарама и его следствия

[freeot]

Я заинтересовался проблемой Гольдбаха (представление четного суммой двух простых), и в процессе переоткрыл, как оказалось, решето Сундарама
Сейчас я параллельно занимаюсь
1) изучением мат.аппарата для придания строгости своему доказательству,
2) способами поиска больших простых чисел, и
3) поиском легкого способа разложения большого числа на множители.

По вопросу поиска больших простых я нашел вычислительно элементарный способ (сам способ будет чуть ниже).

Вводная:
1. Все простые числа - нечетные.
2. Любое нечетное число либо простое, либо составное.
3. Любое нечетное $Z$ можно представить как $(2z+1)$, где $z$ - натуральное.
4. Нечетное является составным, только если его можно представить как произведение двух нечетных $(2z+1)=(2x+1)(2y+1)$.
5. Нечетное является составным, только если уравнение $z=2xy+x+y$ имеет решение в натуральных $x$ и $y$.

Это и есть решето "мое" и Сундарама
Если из натурального ряда вычеркнуть значения, которые принимает $z$ для любых натуральных $x$ и $y$, то оставшиеся числа будут четными основаниями простых (простое получается умножением на 2 и прибавлением единицы).
Первые значения $z$ выглядят так - 4, 7, 10, 12, 13, 16, 17, 19, 22, 25, 27, 28, 31, 32, 34, 37 и т.д.
Что соответствует нечетным $(2z+1)$, которые не являются простыми - 9, 15, 21, 25, 27, 33 и т.д.


В отношении бинарной проблемы Гольдбаха можно показать:

6. Любое четное число $Z=2z$ можно представить суммой двух нечетных $Z=2z=(2z_1+1)+(2z_2+1)$.
7. Область решений уравнения $z=z_1+z_2$ является последовательной частью ряда натуральных чисел (Например, 22 можно представить как (21+1), (19+3), (17+5), (15+7), (13+9), (11+11). Соответственно, $z_1$ и $z_2$ будут (10,0), (9,1), (8,2), (7,3), (6,4), (5,5). И даже можно продолжить до (4,6), (3,7), (2,8), (1,9), (0,10) - это не будет помехой).
8. Для существования простых $(2z_1+1)$ и $(2z_2+1)$ из п.6, необходимо для каждого из них отсутствие решений уравнения из п.5.
9. Предположим утверждение обратное проблеме - для любой пары нечетных чисел, образующих в сумме четное число $Z$, хотя бы одно из них не является простым.
10. Тогда (для натуральных $x$ и $y$) область значений функции $z=2xy+x+y$ должна совпадать с областью значений функции $z=x+y$ (т.е., фактически, покрывать весь натуральный ряд).
11. А это не так (вопрос о строгом сравнении функций открыт здесь: post621314.html#p621314). Следовательно, предположение в п. 9 является неверным. Следовательно, всегда существует такая пара нечетных чисел, образующих в сумме четное число $Z$, оба из которых являются простыми.
ЧТД


Что касается разложения большого числа на множители, то здесь можно предложить алгоритм (об эффективности судите сами), основанный на том же уравнении $z=2xy+x+y$.
Если мы приведем уравнение к виду $z=2x(y+1)+y$ и будем последовательно фиксировать $y$ (y=1,2,3,4,5...), то получим выражения вида
$z=3x+1$, или $z-1=3x$,
$z=5x+2$, или $z-2=5x$,
$z=7x+3$, или $z-3=7x$,
$z=9x+4$, или $z-4=9x$,
$z=11x+5$, или $z-5=11x$,
$z=13x+6$, или $z-6=13x$,
$z=15x+7$, или $z-7=15x$,
и т.д.

Когда перед нами стоит специфическая задача по большому числу $Z$ определить из каких двух простых множителей $X$ и $Y$ оно состоит (криптозадача), то можно воспользоваться таким алгоритмом:
1. из $Z=2z+1$ получаем $z$.
2. открываем цикл по натуральному $k$
3. последовательно вычитаем $k$ из $z$ (фактически уменьшаем $z$ на единицу на каждом цикле) и проверяем делимость числа $(z-k)$ на число $(2k+1)$.
Все
Как только нашли делимость, наши простые множители будут $X=2k+1$ и $Y$ - это частное от деления $(z-k)$ на $(2k+1)$ на последнем шаге.

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

-- 20.09.2012, 15:19 --

Продолжение тут: topic62421.html
А то пропадает почему-то все.

[freeot]

Начало тут: topic62419.html
А то пропадает почему-то все.

Ну, и наконец, самое вкусное - элементарное нахождение любых больших простых чисел

Допустим, мы хотим найти простые числа порядка $10^{10000}$ (или $10^{10^{1000000000}}$ - без разницы)

Шаг -2. Возьмем "удобное число" $2\cdot10^{10000}+1$ соответствующее искомому порядку. Это нечетное число, которое можно представить в том же, упомянутом выше, виде $Z=2z+1$.
Шаг -1. Выделим его четное основание $z=\frac{Z-1}2$ и назовем его $E$. У нас оно будет равно $10^{10000}$. Это наше основание. Это нижняя граница области в которой мы получим большие простые числа.
Шаг 0. Зададим верхнюю границу области больших простых чисел, как дельту $D$. Например, 1000 ($10^3$). Т.е., мы задали диапазон $(E; E+D)$.

Теперь вспомним еще раз, что если мы приведем уравнение к виду $z=2x(y+1)+y$ и будем последовательно фиксировать $y$ (y=1,2,3,4,5...), то получим выражения вида
$z=3x+1$, или $z-1=3x$,
$z=5x+2$, или $z-2=5x$,
$z=7x+3$, или $z-3=7x$,
$z=9x+4$, или $z-4=9x$,
$z=11x+5$, или $z-5=11x$,
$z=13x+6$, или $z-6=13x$,
$z=15x+7$, или $z-7=15x$,
и т.д.

Наше число $E$ ($10^{10000}$) - это число вида 10000....0000, т.е., сумма его цифр равна "1". Соответственно, число $(E-1)$ - делится на "3".
Мы нашли $(z-1)=3x$.
Возьмем $E_0=z=E$ ($E_0$ определяется как число, которое делится на $(2k+1)$, плюс $k$, где $k$ - номер шага итерации) и "пойдем прибавлять" наш первый шаг равный 3. Получим $E+3$, $E+6$, $E+9$ и т.д. Заполняя "вычеркиванием" таблицу от $E$ до $(E+D)$. Т.е., $E_i=E_0+3i$. Видите, величина самого $E$ нас не волнует - мы работаем в области от 1 до $D$
На следующем шаге, используя признак делимости на 5, мы можем найти $(z-2)=5x$ - это само число $E$. Откуда новое $E_0=E+2$. Если хотим, можем взять $E_0$ "за пределами области $(E; E+D)$": $E_0=E+2-5$. И снова "пошли прибавлять" $E_i=E_0+5i$, получая $E+2$, $E+7$, $E+12$, $E+17$ и т.д.
Используя признаки делимости и благодаря тому, что мы взяли "удобное число" можно "просеять" нашу область решетом из первых нечетных чисел.

А что с большими нечетными?
А очень просто.
Вот, взяли мы на шаге "209" очередное нечетное число "419". (метод будет одинаков для любой разрядности числа)
Нам не надо искать особые способы проверки делимости какого-то большого числа около $E$ на 419.
Мы просто:
1) выделяем в этом числе степень 10 (определяем разрядность числа - p). $419 = 4,19\cdot10^2$
2) домножаем это число на степень $10^{10000-p-1} = 10^{9997}$. Получаем число $4,19\cdot10^{9999}$. Это число точно делится на 419 и находится "недалеко" от $E$.
3) насколько "недалеко"? Представляем его как $10\cdot10^{9999}-4,19\cdot10^{9999} = (10-4,19)\cdot10^{99999} = 5,81\cdot10^{9999}$. Получится число 581000000... (с 9997 нулями).
дальше, пока, для простоты, предположим, что нас такая близость "устроила".
4) берем "смещение" этого числа, равное шагу итерации, т.е., "209". Получаем $5,81\cdot10^{9999} + 209$, т.е., 5810000...(9994 нуля)...0000209. Это наше новое $E_0$. И опять "пошли складывать" по 419 $E_i=E_0+419i$. При этом проверяя, сначала старшие разряды - пока сумма не достигла $E$, нас число не интересует. Когда сумма стала больше $E$ на некоторое $Q$, берем новое $E_0=E+Q$ и продолжаем "просеивать" нашу искомую область $(E; E+D)$. Естественно, что как только $E_i>D$, то с данной итерацией мы закончили и переходим к следующей.

Этот алгоритм универсален для любой разрядности, поэтому признаками делимости на 3, 5 и т.п. можно и не "заморачиваться".

"Просеянная" область от 1 до $D$ содержит невычеркнутые четные основания простых. Прибавьте к ним наше $E$ (которое у нас было "за скобками"), домножьте их на 2 и прибавьте 1 - вот ваш "улов" простых. И в нем, думаю, далеко не одна "рыбка" (да не золотая, а самая что ни на есть простая!)

Данный алгоритм не использует ничего, кроме сложения (единственное вычитание - это дополнение до следующего разряда 10 и может быть реализовано через сложение). С точки зрения обычных приложений на домашнем компьютере мы ограничены разрядностью чисел над которыми можно делать операции стандартными средствами. Но можно использовать специальные программные библиотеки для работы с большими числами или реализовать поразрядное сложение в строковом виде. А число операций сравнительно невелико.
Таким образом, даже на домашнем компьютере можно за приемлемое время получить очень большие простые в заданном диапазоне, не требующие дополнительных проверок.

Ну, а теперь вернемся к шагу 3. Здесь есть место для оптимизации.
Когда мы получили $4,19\cdot10^{9999}$, в нем $10^{9997}$ разрядов одних нулей, которые мы будем вынужденно "пробегать" сложением по 419.
Эту задачу можно упростить в двух направлениях.
1. Мы можем циклически прибавить к $4,19\cdot10^{9999}$ более младшие степени $4,19\cdot10^{9998} + 4,19\cdot10^{9997} + 4,19\cdot10^{9996} + 4,19\cdot10^{9995} + ... + 4,19\cdot10^3 + 4,19\cdot10^2$.
Т.е., мы из числа вида "70000000000000000000" можем сразу получить число вида "77777777777777777777", которое будет ближе к $E$ на целых.. на много, в общем, ближе
2. Мы можем "проапгрейдить" алгоритм более сложными операциями, если будем высчитывать - насколько нацело делится $E$ на очередное число нашей итерации и брать остаток от деления $R$, представляя $E_0=E-R+k$ (где $k$ - шаг нашей итерации).

Степень вычислительной сложности первого и второго способа лучше оценят более сведущие специалисты, чем я
Возможно оптимальнее всего будет использовать сочетание этих алгоритмов.

Да, и количество итераций у нас будет не $E$, конечно
Если в уравнении $z=2xy+x+y$, $x=y$, то $z=2x^2+2x$, откуда грубая оценка для $x$, при больших $z$ такова, что $x = \sqrt{\frac z2}$. Если точнее, то $x = \sqrt{\frac z2-x}$, но достаточно взять целую часть от $\sqrt{\frac z2}$ в качестве номера последней итерации.


Ну, и на самый конец

Если найдется математический аппарат, с помощью которого можно быстро качественно показать имеет ли решение уравнение $z=2xy+x+y$ для заданного $z$ в натуральных $x$ и $y$, то перед нами - самый простой тест на простоту любого числа

Вот, таково наше с Сундарамом решето

[Toucan]

Темы объединены

[freeot]

Ок.
Вот здесь можно посчитать решение уравнения $z=2xy+x+y$ для достаточно больших z (четных оснований) - 5-6 десятков знаков:
http://www.wolframalpha.com/input/?i=2x ... 0%2C+y%3E0

Но здесь есть мгновенный факторизатор чисел до 60 знаков:
http://ru.numberempire.com/numberfactorizer.php

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

-- 20.09.2012, 15:46 --

Еще забыл отметить, что в алгоритме поиска больших простых чисел - та дельта $D$, которую мы задаем для поиска, может меняться в сторону значительного увеличения весьма с небольшим увеличением вычислительно-ресурсной сложности. Т.е., найти простые на диапазоне в $10^5$ чисел будет практически столь же быстро, как и на диапазоне $10^3$!

-- 20.09.2012, 16:01 --

А еще данный алгоритм поиска простых идеален для распараллеливания вычислений - каждую итерацию (или пакет итераций от шага $k_i$ до $k_{i+t}$) можно выполнять независимо, сохраняя на выходе диапазон $(E; E+D)$ с "вычеркнутыми" числами

-- 20.09.2012, 16:17 --

Нашел опечатку.

Строку:
4) берем "смещение" этого числа, равное шагу итерации, т.е., "209". Получаем $5,81\cdot10^{9999} + 209$, т.е., 5810000...(9994 нуля)...0000209. Это наше новое $E_0$.
Надо читать так:
4) берем "смещение" этого числа, равное шагу итерации, т.е., "209". Получаем $4,19\cdot10^{9999} + 209$, т.е., 4190000...(9994 нуля)...0000209. Это наше новое $E_0$.

Эта опечатка вызвана тем, что я сначала хотел обойтись без залезания далеко от $E$, поэтому и высчитывал разность между $E$ и ближайшим числом типа $4,19\cdot10^{9999}$. Но чтобы никого не путать, я от этого отказался $E_0=4,19\cdot10^{9999} + 209$ - это правильное $E_0$.

[nnosipov]

freeot в сообщении #621388 писал(а):

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

Ну, попробуйте получить 100-значное простое число при помощи своего алгоритма.

[freeot]

nnosipov в сообщении #621408 писал(а):

Ну, попробуйте получить 100-значное простое число при помощи своего алгоритма.

Я попробую
Но у меня "под рукой" доступен только очень медленный инструмент - 1С
А вы можете что-то предметно сказать о ресурсоемкости данного алгоритма (в цифрах)?
Я, конечно, не большой специалист в этом, но мне кажется, "навскидку", что это уж точно эффективней расчетов той группы, которая занимается расчетами чисел Мерсенна (те, кто самые большие числа "открывает" используя распределенные вычисления)
Сколько, по вашему, требуется времени компьютеру для того, чтобы используя метод "1+1=2, 2+1=3, 3+1=4 и т.д." дойти до 100-значного числа?

[nnosipov]

freeot в сообщении #621412 писал(а):

Сколько, по вашему, требуется времени компьютеру для того, чтобы используя метод "1+1=2, 2+1=3, 3+1=4 и т.д." дойти до 100-значного числа?

Вот сами и подсчитайте. Предположите, что в Вашем расположении самый мощный компьютер в мире.

[venco]

(опускаю банальности про решето Сундарама)

freeot в сообщении #621383 писал(а):

9. Предположим утверждение обратное проблеме - для любой пары нечетных чисел, образующих в сумме четное число $Z$, хотя бы одно из них не является простым.
10. Тогда (для натуральных $x$ и $y$) область значений функции $z=2xy+x+y$ должна совпадать с областью значений функции $z=x+y$ (т.е., фактически, покрывать весь натуральный ряд).

Что-то я не могу понять логику этого вывода. Можно поподробнее?

[Cash]

Цитата:

Я, конечно, не большой специалист в этом, но мне кажется, "навскидку", что это уж точно эффективней расчетов той группы, которая занимается расчетами чисел Мерсенна (те, кто самые большие числа "открывает" используя распределенные вычисления)
Сколько, по вашему, требуется времени компьютеру для того, чтобы используя метод "1+1=2, 2+1=3, 3+1=4 и т.д." дойти до 100-значного числа?

Видно, что не специалист.
Группа, которая занимается "расчетами чисел Мерсенна", работает на текущий момент с десятимиллионнозначными числами. Проверка одного числа на простоту на i5 занимает двое суток и более.
Вам предложена "детская" задача: получить всего лишь стозначное число. Даже с очень медленным инструментом, если ваш алгоритм так крут - он должен щелкать такое как семечки.
Но не будет. По одной простой причине. Для того чтобы просеять числа в диапазоне $[10^{100};10^{100}+D]$ вам нужно перебрать все простые до $10^{50}$. А их больше, чем $8 \cdot 10^{47}$. Даже если брать по миллиарду в секунду - сравнить с возрастом Вселенной?
Да что там 100-значные. Этим способом даже 30-значное не получить...

[freeot]

venco в сообщении #621428 писал(а):

freeot в сообщении #621383 писал(а):

9. Предположим утверждение обратное проблеме - для любой пары нечетных чисел, образующих в сумме четное число $Z$, хотя бы одно из них не является простым.
10. Тогда (для натуральных $x$ и $y$) область значений функции $z=2xy+x+y$ должна совпадать с областью значений функции $z=x+y$ (т.е., фактически, покрывать весь натуральный ряд).

Что-то я не могу понять логику этого вывода. Можно поподробнее?

Я попытаюсь. Но в силу того, что я не математик, это, скорее всего, получится наукообразно, но в чем-то наверняка не корректно Надеюсь, вы сможете извлечь из этого хотя бы смысл.
Если мы берем произвольное натуральное четное $Z$, и рассматриваем два определения которые мы придаем $Z$ в предположении из п. 9, то это будут:
1. Представление $Z$ как любой пары нечетных чисел, в сумме дающих $Z$.
Это соответствует такой функции, областью определения которой является множество натуральных чисел, ограниченное "сверху" $Z$, т.е., - множество (0, 1, 2, 3... $Z$), а областью значений множество таких множеств, состоящих из двух элементов, в котором один элемент задается функцией $X$, а другой функцией $Z-Y$. (Или $Z-X$? В общем, мы берем из натурального ряда одно нечетное и дополняем его вторым, "рассчитанным" или "выраженным" как $Z$ минус первое).
Единственный момент, - мы эквивалентно трансформируем условие четного $Z$ в виде пары двух нечетных $Z_1$ и $Z_2$, "спускаясь" на уровень их "четных оснований", представляя это условие как $z=z_1+z_2$, где $z=\frac Z2$, $z_1=\frac {(Z_1-1)}2$, $z_2=\frac {(Z_2-1)}2$.
Это удобно, т.к., значения $z_1$ и $z_2$ мы таким образом берем "напрямую" из последовательного натурального множества, не "переводя" их в образ нечетных чисел.
Т.е., вместо того, чтобы говорить что областью определения наших функций будет последовательное множество (1, 2, 3, 4, 5... $Z$), откуда мы берем в качестве аргументов только "нечетные", мы говорим что областью определения наших функций будет последовательное множество (1, 2, 3, 4, 5... $z$) (ограниченное $z$ маленькое, где $z=\frac Z2$), откуда мы берем в качестве аргументов любые значения - это и есть "четные основания" всех нечетных чисел из множества (1, 2, 3, 4, 5... $Z$).
Так вот, по сути, у нас для этого условия две функции:
$z_1=x$
и
$z_2=x$
Так, что каждая выбирает любое значение из множества (1, 2, 3, 4, 5... $z$). Наверное правильным будет для функции $z_2$ выбрать аргументом $y$, а не $x$, показывая, что в общем это функции независимых аргументов.
Но "соединяем" мы их попарно используя функцию $z=z_1+z_2$. Это и будет зависимость функций $z_1$ и $z_2$
Так как каждая из функций $z_1$ и $z_2$ является простой функцией вида $f(x)=x$, то и возвращать в качестве значений они будут то же множество, на котором они определены. Т.е., весь натуральный ряд, ограниченный сверху $z$.
2. Второе определение, которое мы накладываем на $Z$ в предположении из п. 9, это то, что либо функция $z_1$, либо функция $z_2$ (в принципе, без разницы - так как мы уже показали, что эти функции одного вида, с одной и той же областью определения и областью значения) будут представимы в виде $z_2=2xy+x+y$ или $z_1=2xy+x+y$ (что означает, что нечетное слагаемое, вида $(2z_1+1)$ которое мы взяли для получения числа $Z$, является произведением двух нечетных чисел $(2x+1)$ и $(2y+1)$) и данная функция имеет решение для той же области определения $x$ и $y$ - на множестве (1, 2, 3, 4, 5... $z$).

Мы получаем противоречие. По первому накладываемому определению мы получаем функции вида $z_1=x$, или $z_1=z-x$, или $z=x+y$ (какая бы из них ни была правильной) областью значений которых является то же натуральное множество, что определено для них как область значений. А по второму определению, мы получаем функцию вида $z_1=2xy+x+y$, область значений которой гораздо более разрежена, по сравнению с рядом натуральных чисел. Они не могут одновременно являться функциями описывающими $z_1$ (для $z_2$ - аналогично).

Как-то так

[vorvalm]

freeot
"Ваше" решето Сундарама ни чем не отличается от решета Эратосфена.
Оно закамуфлировано уравнением
$z=2xy+x+y$,
что создает дополнительные сложности в процесс вычеркивания составных чисел.
Кстати, у вас пропущено $z=24.$
Если зафиксировать $y$, то получим:
$y=1,\;z=3x+1=(x^{++})=4,7,10,13,....$
$y=2,\;z=5x+2=(x^{++})=7,12,17,22,...$
$y=3,\;z=7x+3=(x^{++})=10,17,24,31...$ и т.д.
И мы получим числа, кратные соответственно $p=3,\;5,\;7,...$

[freeot]

Cash в сообщении #621456 писал(а):

Видно, что не специалист.
Группа, которая занимается "расчетами чисел Мерсенна", работает на текущий момент с десятимиллионнозначными числами. Проверка одного числа на простоту на i5 занимает двое суток и более.
Вам предложена "детская" задача: получить всего лишь стозначное число. Даже с очень медленным инструментом, если ваш алгоритм так крут - он должен щелкать такое как семечки.
Но не будет. По одной простой причине. Для того чтобы просеять числа в диапазоне $[10^{100};10^{100}+D]$ вам нужно перебрать все простые до $10^{50}$.

Я вас понял.
Алгоритм, конечно, на простых вообще никак не завязан, кроме того, что он их ищет, но... "четных оснований" для 100-значного числа перебрать надо примерно того же порядка - $10^{47}$

Cash в сообщении #621456 писал(а):

А их больше, чем $8 \cdot 10^{47}$. Даже если брать по миллиарду в секунду - сравнить с возрастом Вселенной?

Я уже нашел оценку возраста вселенной как $5\cdot10^{17}$

А в 1С я попробовал просто производительность - пустой счетчик полчаса работал и дошел только до миллиарда

Как я написал в самом начале, я начал с нечетных Гольдбаха, а к простым перешел уже "сопутственно"
Есть у меня еще желание найти способ поиска больших простых на основе принципа распределения простых, что-то такое "в голове крутится"

-- 20.09.2012, 19:22 --

vorvalm в сообщении #621474 писал(а):

freeot
"Ваше" решето Сундарама ни чем не отличается от решета Эратосфена.

Решето не только "мое" но и индийского студента Сундарама, который его открыл в 1934 году

Только с решетом Эратосфена у них общий только принцип самого "решета", а область приложения и вкладываемый смысл - разный.
Решето Эратосфена "вычеркивает" числа в натуральном ряду, который включает и четные тоже. Например, по кратности "3" оно вычеркнет ряд 6, 9, 12, 15, 18, 21...
Решето Сундарама "вычеркнет" числа не в общем натуральном ряду, а только в ряду "четных оснований" нечетных чисел, причем не перебором всех возможных делителей, а нахождением корней всего одной функции, которая однозначно определяет: "простое число или нет" - сравните сами предыдущий ряд с рядом - 4,7,10,13..., который даст нам ряд - 9, 15, 21...

vorvalm в сообщении #621474 писал(а):

Кстати, у вас пропущено $z=24.$

Это - да. Пропустил

[venco]

freeot в сообщении #621472 писал(а):

Мы получаем противоречие. По первому накладываемому определению мы получаем функции вида $z_1=x$, или $z_1=z-x$, или $z=x+y$ (какая бы из них ни была правильной) областью значений которых является то же натуральное множество, что определено для них как область значений. А по второму определению, мы получаем функцию вида $z_1=2xy+x+y$, область значений которой гораздо более разрежена, по сравнению с рядом натуральных чисел. Они не могут одновременно являться функциями описывающими $z_1$ (для $z_2$ - аналогично).

Во первых, не "гораздо более разрежена", а лишь малая доля всех чисел не представима в виде $2xy+x+y$.
Во вторых, вы совсем не то доказываете. В вашем втором представлении тоже получаются все числа, кроме нескольких первых, т.к. это по сути - составное+любое. А надо рассматривать простое+простое.

-- Чт сен 20, 2012 11:30:55 --

freeot в сообщении #621480 писал(а):

Решето Эратосфена "вычеркивает" числа в натуральном ряду, который включает и четные тоже. Например, по кратности "3" оно вычеркнет ряд 6, 9, 12, 15, 18, 21...
Решето Сундарама "вычеркнет" числа не в общем натуральном ряду, а только в ряду "четных оснований" нечетных чисел, причем не перебором всех возможных делителей, а нахождением корней всего одной функции, которая однозначно определяет: "простое число или нет" - сравните сами предыдущий ряд с рядом - 4,7,10,13..., который даст нам ряд - 9, 15, 21...

Исключение чётных чисел ускоряет алгоритм в два раза, ничуть не меняя его вычислительную сложность. Ну сможете вы искать простые числа не до $10^{10}$, а до $2\cdot 10^{10}$, это всё равно очень мало по сравнению с более умными алгоритмами.

[freeot]

venco в сообщении #621483 писал(а):

Во первых, не "гораздо более разрежена", а лишь малая доля всех чисел не представима в виде $2xy+x+y$.

Я понимаю, что "чем дальше в лес", т.е., чем дальше в область больших чисел мы залезаем, тем более редко будут встречаться простые.
НО... Рассматривая любое четное $Z$, каким бы большим оно не было, мы рассматриваем диапазон для представления его в виде суммы двух нечетных все равно от 1 до $Z$. Поэтому мы с успехом и можем разложить четное на два простых, как показывает эксперимент.

venco в сообщении #621483 писал(а):

Во вторых, вы совсем не то доказываете. В вашем втором представлении тоже получаются все числа, кроме нескольких первых, т.к. это по сути - составное+любое. А надо рассматривать простое+простое.

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

venco в сообщении #621483 писал(а):

Исключение чётных чисел ускоряет алгоритм в два раза, ничуть не меняя его вычислительную сложность. Ну сможете вы искать простые числа не до $10^{10}$, а до $2\cdot 10^{10}$, это всё равно очень мало по сравнению с более умными алгоритмами.

Да, я понял, что преодолеть вычислительную сложность для компьютера мне не удалось. Я исходил из того наивного представления, что раз операции с большими числами трудоемки, то если все свести к операции сложения, то сложность будет преодолена.

Но все равно, мне кажется что мои результаты довольно замечательны: не обладая какой-то глубокой математической базой, располагая блокнотом и ручкой (и температурой 38), отталкиваясь от того, что 1 - нечетное, 1+1=2 - четное, 2+1=1+1+1=3 - снова нечетное, я открыл решето Сундарама и, за несколько дней поиска, изучения и осмысления дополнительных данных, самостоятельно разработал неплохие (пусть и устаревшие) алгоритмы для двух важных задач

[venco]

freeot в сообщении #621496 писал(а):

не обладая какой-то глубокой математической базой, располагая блокнотом и ручкой (и температурой 38), отталкиваясь от того, что 1 - нечетное, 1+1=2 - четное, 2+1=1+1+1=3 - снова нечетное, я открыл решето Сундарама

Это говорит лишь о том, что решето Сундарама ничего особенного не представляет по сравнению с решетом Эратосфена. Эта оптимизация приходит в голову самостоятельно практически любому, кто пользуется решетом для поиска простых чисел. Я уверен, что и задолго до Сундарама этим пользовались разные люди, и не очень понимаю, чем Сундарам заслужил упоминания в Википедии.