Методика определения делимости чисел

[Someone]

Iosif1 в сообщении #1206417 писал(а):

Вы утверждаете, что всё это известно.
Позвольте ссылку.

У меня есть книжка для школьников:

Б. А. Кордемский. Математическая смекалка. Издание четвёртое, стереотипное. Государственное издательство технико-теоретической литературы. Москва, 1957.

Первое издание, как можно понять из аннотации, вышло в начале пятидесятых годов XX столетия.

Хочу обратить ваше внимание на задачу 357, которая называется «Новое "решето" для простых чисел». В тексте задачи сообщается, что

Цитата:

немногим более двадцати лет назад одно из новых "решёт" придумал студент-математик С. П. Сундарам (Индия)***):

$$\begin{array}{rrrrrrr} 4&7&10&13&16&19&\ldots\\ 7&12&17&22&27&32&\ldots\\ 10&17&24&31&38&45&\ldots\\ 13&22&31&40&49&58&\ldots\\ 16&27&38&49&60&71&\ldots\\ .\ .&.\ .&.\ .&.\ .&.\ .&.\ .&\ldots \end{array}$$

***) Два новых "решета" письмом прислал мне инженер-связист М. Соукуп (Чехословакия).

Правила использования этой таблицы такие: если натуральное число $N$ есть в таблице, то число $2N+1$ составное; если же числа $N$ в таблице нет, то число $2N+1$ простое.

Идея тут достаточно элементарная и доступная школьникам. Чётные числа, за исключением числа $2$, все составные. Нечётное число $n$ всегда можно записать в виде $n=2N+1$. Если оно составное, то оно является произведением двух нечётных чисел, бóльших $1$: $2N+1=(2x+1)(2y+1)$. Раскрывая скобки и упрощая, получим $N=2xy+x+y$. Вот эти числа и записаны в таблице, причём, $x$ и $y$ — это номер строки и номер столбца таблицы, на пересечении которых располагается число $N$. Естественно, если число $2N+1$ простое, то его нельзя представить в виде произведения двух чисел, бóльших $1$, и числа $N$ в таблице не будет.

Ну, Вы делали ещё один шажок: исключили числа, делящиеся на $3$. Число $n$, которое больше $1$ и не делится ни на $2$, ни на $3$, можно записать в виде $n=6N\pm 1$. Если оно составное, то его можно представить в виде произведения двух чисел, бóльших $1$; естественно, они также не будут делиться ни на $2$, ни на $3$, поэтому их можно записать в таком же виде, поэтому $n=(6x\pm 1)(6y\pm 1)$. Здесь возможны $4$ комбинации знаков:
$6N+1=(6x+1)(6y+1)\Rightarrow N=6xy+x+y$,
$6N+1=(6x-1)(6y-1)\Rightarrow N=6xy-x-y$,
$6N-1=(6x+1)(6y-1)\Rightarrow N=6xy-x+y$,
$6N-1=(6x-1)(6y+1)\Rightarrow N=6xy+x-y$.
Последние два случая, по существу, одинаковые (отличаются только обозначениями $x$ и $y$).
Составляем соответствующие таблицы, и так далее.

Я не знаком с соответствующей литературой и не дам гарантии, что всё это не опубликовано в каком-нибудь журнале типа "Математика в школе" за какой-нибудь "-дцатый" год. Идея-то совсем простая.

Можно продолжить эти построения, исключая числа, делящиеся на следующие простые числа. Ну и что? Зачем это?
Вряд ли на этом пути можно получить существенно более эффективный алгоритм, чем решето Эратосфена.

Также хотел бы обратить ваше внимание на то, что в настоящее время для того, чтобы метод проверки числа на простоту был кому-то интересен, он должен быть эффективен для чисел порядка $10^{1000}$ и более, а метод факторизации — для чисел порядка $10^{100}$ (возможно, я уже отстал от событий). Ваш метод ни для того, ни для другого не пригоден.

Iosif1 в сообщении #1206438 писал(а):

А Вы не смогли бы мне помочь, сделать это, как соавтор?

Для профессионального математика, коим является Brukvalub, упражнения на школьном уровне интереса не представляют.

[Dmitriy40]

Iosif1
Вот я выбрал число $p$, проверил что оно не делится ни на $2$, ни на $3$, что дальше делать? Конкретно, без непонятно как построенных таблиц (да и нету её такой огромной), какое действие применить к числу $p$? Как определить те два числа $x,y$, которые должны дать равенство $p=6xy \pm x \pm y$? Для примера возьмём $p=1111111111111111111=(10^{19}-1)/9$. Итак, что дальше делать с этим числом? Умножать, делить, складывать, вычитать, остаток от деления на что считать?

[Iosif1]

Someone в сообщении #1206443 писал(а):

Для профессионального математика, коим является Brukvalub, упражнения на школьном уровне интереса не представляют.

Во-первых, спасибо за ваш пост.
Мне нужно заинтересовать математика, не обязательно, Brukvalub(а).
Не могу не удержаться, чтобы не сказать, что очень приятно читать информационный пост.
Однако, в чём соль методики?
На основании формализованных выражений чисел, показанных Вами, факторизация числа посредством методики уже не является решетом.
Число любой величины, принадлежащее конкретному формализованному выражению из возможных вариантов, подчиняется одним и тем же числовым закономерностям.
Правда, с учётом чётности х и у, и сопоставимости их величин.
То есть, все числа, не содержащие сомножителей 2 и 3 могут быть распределены на 16 вариантов.
А числа каждого из вариантов подчиняются одним и тем же расчётным закономерностям.
То есть определив, или предположив принадлежность рассматриваемого числа к конкретному варианту, мы расчётным путём получаем возможность получения, либо подтверждение этого, либо опровержение.
Максимальное количество вариантов, подлежащих проверке - четыре.
Используя мод 6 и 4, мы обеспечиваем увеличение интервала просчёта до 24.
Это, конечно, для эффективности факторизации является чепухой.
Но существующие закономерности позволяют кратно увеличивать интерва просчёта.
Существование такой возможности подтверждена.
Однако признаюсь, что я опробывал только единственный вариант чисел.
Только расчёты выявляют закономерности.
А без программы, это непосильный труд.
Определение простоты числа, априори, также не зависит от величины числа.
Если, конечно, не считать трудоёмкости при определении остатков по мод 6 и мод 4.
Но, а возможность решения квадратных уравнение посредством линейных зависимостей, разве не заслуживает внимания.
Вот и хочется кому то передать, профессиональному математику, или любителю, такому как я, но подготовленному получше к существующим рифам.
По моему мнению, он найдёт не мало "интересностей и полезностей".
Очень был бы благодарен за содействие в нахождении искомого.

-- Вт апр 04, 2017 15:33:45 --

Dmitriy40 в сообщении #1206450 писал(а):

Iosif1
Вот я выбрал число $p$, проверил что оно не делится ни на $2$, ни на $3$, что дальше делать? Конкретно, без непонятно как построенных таблиц (да и нету её такой огромной), какое действие применить к числу $p$? Как определить те два числа $x,y$, которые должны дать равенство $p=6xy \pm x \pm y$? Для примера возьмём $p=1111111111111111111=(10^{19}-1)/9$. Итак, что дальше делать с этим числом? Умножать, делить, складывать, вычитать, остаток от деления на что считать?

Определяем, к какому вспомогательному числовому ряду принадлежит данное число.
Вспомогательных числовых рядов два.
Первый, если число (р-1) делится на 6 без остатка
Второй, если число (р+1) делится на 6 без остатка.
Третий вариант невозможен.
Частное отделения является номером рассматриваемого числа.
Это даёт нам возможность исключить 8 вариантов расчёта.
И утверждать, что, если это число не простое, оно принадлежит либо первому квадранту, либо третьему.
Далее, определяется остаток при делении номера числа, снова, на мод 6.
Если номер числа чётный, остаток, также чётный.
При предположении, что число принадлежит первому квадранту - остаток рассматривается со знаком +.;
если к третьему квадранту - со знаком (-).
Отпадают ещё четыре проверочных варианта.
Если номер числа чётный, то и х, и у имеют эдентичную чётность.
Почему это важно!
Потому, что корреляционные зависимости между координатами числа х и у, по мод 6 и по мод 4 зависят от чётности координат. (И также, от соотношения величин х и у.
На основании остатка при делении номера числа на 6 с интервалом 6, строим числовой ряд возможных значений величины (х+у).
Аналогично, строим числовой ряд возможных значений (х+у), определяемых по мод 4. (с интервалом 4)
При этом, заранее не гарантируя знаки перед координатами.
Далее, на основании расчётных формул осуществляем перевод значений числового ряда (х+у), рассчитанный по мод 6 в возможные значения суммы или разности координат, рассчитанных по мод 4.
Ищем первое совпадение....

[Someone]

Iosif1 в сообщении #1206452 писал(а):

Мне нужно заинтересовать математика, не обязательно, Brukvalub(а).

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

Iosif1 в сообщении #1206452 писал(а):

То есть определив, или предположив принадлежность рассматриваемого числа к конкретному варианту, мы расчётным путём получаем возможность получения, либо подтверждение этого, либо опровержение.

Iosif1 в сообщении #1206452 писал(а):

Определение простоты числа, априори, также не зависит от величины числа.

Наивный человек. Ну возьмите число

Dmitriy40 в сообщении #1206450 писал(а):

$p=1111111111111111111=(10^{19}-1)/9$

Или возьмём число поменьше: $858993463$. И сравните трудоёмкость с каким-нибудь небольшим числом, например, $3293$.

Iosif1 в сообщении #1206452 писал(а):

На основании формализованных выражений чисел, показанных Вами, факторизация числа посредством методики уже не является решетом.

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

Iosif1 в сообщении #1206452 писал(а):

Вот и хочется кому то передать, профессиональному математику, или любителю, такому как я, но подготовленному получше к существующим рифам.
По моему мнению, он найдёт не мало "интересностей и полезностей".

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

Dmitriy40 в сообщении #1206450 писал(а):

без непонятно как построенных таблиц

Там в каждой строчке и в каждом столбце — арифметические прогрессии.

-- Вт апр 04, 2017 14:37:14 --

Iosif1 в сообщении #1206452 писал(а):

Ищем первое совпадение....

Ну ищите, ищите…

Да, не забудьте, если совпадение найдётся, то это даст и факторизацию числа на два множителя.

[Iosif1]

Someone в сообщении #1206457 писал(а):

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

Я знаю, что Вас не стоит переубеждать. Хотя и хотелось бы.
В подтверждение своей правоты скажу, что опыт, и программа Белых С.А., и собственные расчёты подтверждают ЭФФЕКТИВНОСТЬ МЕТОДИКИ.
Уверяю Вас, как не пародоксально, но то, на чём построена методика я знаю глубоко.

Someone в сообщении #1206457 писал(а):

Там в каждой строчке и в каждом столбце — арифметические прогрессии.

Ну и что? При управляемом интервале просчёта.
Уважаемый Someone, почему Вы не замечаете открывающуюся возможность решение квадратных уравнений посредством линейных зависимостей. Не верите, или это известный "фокус".
Вы человек очень обогащённый знаниями.
Поэтому хочется услышать ваше мнение.

[Lia]

Iosif1
У Вас уже целая коллекция этих мнений. Проблема с тем, чтобы услышать.
Или Вам хочется услышать мнение, совпадающее с Вашим?

Iosif1 в сообщении #1206460 писал(а):

расчёты подтверждают ЭФФЕКТИВНОСТЬ

И где они, расчеты? Вас уже спрашивали об оценке сложности алгоритма. Чему она равна? Не надо слов писать, как это все круто. Напишите оценку.

[Iosif1]

Lia в сообщении #1206466 писал(а):

У Вас уже целая коллекция этих мнений. Проблема с тем, чтобы услышать.
Или Вам хочется услышать мнение, совпадающее с Вашим?

Я хочу оценочного мнения.
Если можно так сказать.
Оценить методику, хотя бы, по одному формализованному варианту чисел.
Или это не допустимо.
Методика выложена в интернете.
Да я могу её и продублировать.
Или это не возможно?

Lia в сообщении #1206466 писал(а):

И где они, расчеты? Вас уже спрашивали об оценке сложности алгоритма. Чему она равна? Не надо слов писать, как это все круто. Напишите оценку.

Не знаю, как обеспечивается оценка сложности алгоритма.
Кто то сказал, что для этого необходима написанная программа.
Я понимаю, какое у Вас складывается мнение обо мне.
Он даже этого не может.
Я, поэтому и ищу соавтора, который более продвинут, чем я.
Если нельзя у Вас на сайте, скажите, я человек законопослушный.
Обратиться вновь на форум мне позволила публикация на Хабрахабре,
Где, как мне показалось, было какое то понимание.

[Dmitriy40]

Someone в сообщении #1206457 писал(а):

Там в каждой строчке и в каждом столбце — арифметические прогрессии.

Да это понятно. Непонятно почему таблиц больше одной и почему кроме $\bmod 6$ используется $\bmod 4$, а не $30$ или не $210$ (т.е. праймориалы). Вообще проверка по модулю 4 выглядит глупостью или как минимум неоптимальной.

Iosif1
Итак, я взял число $p=1111111111111111111$, разделил его на 6, получилось что $p-1 \equiv 0 \mod 6$, новое значение $p_1=185185185185185185$.

Iosif1 в сообщении #1206452 писал(а):

Это даёт нам возможность исключить 8 вариантов расчёта.
И утверждать, что, если это число не простое, оно принадлежит либо первому квадранту, либо третьему.

Не вижу никаких квадрантов, никаких вариантов расчёта. Только три числа: $p, p_1, -1$.

Iosif1 в сообщении #1206452 писал(а):

Далее, определяется остаток при делении номера числа, снова, на мод 6.

Остаток нечётный: $p_1 \equiv 3 \mod 6$. И что дальше с этим делать?

Iosif1 в сообщении #1206452 писал(а):

Если номер числа чётный, остаток, также чётный.
При предположении, что число принадлежит первому квадранту - остаток рассматривается со знаком +.;
если к третьему квадранту - со знаком (-).
Отпадают ещё четыре проверочных варианта.
Если номер числа чётный, то и х, и у имеют эдентичную чётность.

Номер числа (т.е. $p_1$) нечётный, остаток тоже нечётный - и о чём это говорит? Никаких ни квадрантов, ни вариантов всё ещё не вижу. Про чётность $x,y$ тоже пока сказать ничего нельзя т.к. число получилось не чётным.

Что теперь делать с числом $p_1=185185185185185185$?

-- 04.04.2017, 16:44 --

Iosif1 в сообщении #1206474 писал(а):

Методика выложена в интернете. Да я могу её и продублировать.

Дублировать не нужно. Нужно объяснить понятным языком как именно проверить произвольное число (например два хороших примера выше: $1111111111111111111$ и $858993463$) и что получится в результате. А уж потом думать про сложность и программы.

PS. ToAll. Я понимаю что ничего полезного тут не обнаружится, но вдруг получится показать это автору при разборе конкретных примеров? А когда наконец добьёмся конкретного алгоритма действий - интересно посмотреть не обнаружатся ли контрпримеры к нему.

[Iosif1]

Dmitriy40
Давайте свяжимся по Skype : iosif705.
Если сотрудничество не обеспечиться, я не буду Вам надоедать.

[Dmitriy40]

Iosif1
Я на (со)авторство не претендую, пишите для всех.
Пока не потребовалось ничего сложнее калькулятора Windows.

[Deggial]

Тема перемещена из форума «Дискуссионные темы (М)» в форум «Карантин»
Причина переноса: тема не удовлетворяет требованиям дискуссионного раздела: описание алгоритма чётко не сформулировано, доказательство того, что алгоритм проверяет число на простоту, отсутствует

Iosif1, приведите Ваше последнее описание алгоритма в соответствии с требованиями дискуссионного раздела.
1. Сформулируйте алгоритм полностью формально.
2. Докажите, что он определяет простоту числа.
3. Дайте его асимптотическую оценку.
Все формулы и термы набирайте $\TeX$ом.
См. также тему Что такое карантин, и что нужно делать, чтобы там оказаться.
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.