Составные и простые.

Первое сообщение в теме :

Вы меня друзья настрополили на эту задачу. А "мы не привыкли отступать".
Иду своим малообразованным путём. Но что-то уже вижу. Мож это и детский сад, но упражнения для мозгов - хорошие.
Почему ряды 6K+-1?
- Потому, что без пропусков всех простых и всех составных, требующих факторизации.
- Потому, что мы можем перейти на другое решето по k (ведь без пропусков):
1. Для ряда 6k+1:
составные по модулю 7 (к7=1):
к=8,15,22,29,36...=7n+1=7n+k7
составные по модулю 13 (k13=2):
к=15,28,41,54...=13n+2=13n+k13
составные по модулю 19 (к19=3)
k=22,41,60,79...=19n+3=19n+k19
и т.д.
2. По ряду 6k-1 - аналогично...

Остальные k естественно соответствуют простым.

Гэм пишет:
А что посоветует в этом случае Привалов?

"А что по этому поводу скажет товарищ Жюков?" (с)

Я не математик. Как-то не очень в теме. Если увижу в виде результата какое-то настораживающее число...
А пока только слежу за вами.

Владимир Привалов пишет:

Гэм пишет:
А что посоветует в этом случае Привалов?

"А что по этому поводу скажет товарищ Жюков?" (с)

Я не математик. Как-то не очень в теме. Если увижу в виде результата какое-то настораживающее число...
А пока только слежу за вами.

Как понял, твой ход, Михаил.

Позвольте +5коп.

Достаточно искать меньший простой сомножитель.

Тестировать целые на простоту, ища их разложение (и не находя!) на множители, не просто нерационально, а безумно нерационально.
Дело в том, что тестирование на простоту - задача решаемая без попыток факторизации и СУЩЕСТВЕННО более быстро.
Предложение об определении простоты через факторизацию это типа "в Рязань из Мск через Кейптаун".
Можно конечно....

А вот задача, решения которой я не знаю, но которая имеет существенно более прикладную значимость, чем тестирование на простоту. По-моему она не решена.
ЗАДАЧА.
Как отличить числа, являющиеся произведением РОВНО двух простых от всех остальных, не прибегая к решению задачи факторизации?

ЗЫ. Рассуждения "на тему 6k+-1" можно опустить. То, что произведение двух чисел такого вида также имеет такой вид получается тривиально раскрытием скобок в произведении и перегруппировкой слагаемых. Будем считать, что это уже проехали.

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

Михаил Полянский пишет:Михалычу. В моих попытках ответить на простые вопросики, чтоб сохранить дискуссию, на примере простейшей прогрессии было усмотрено то, чего и не пытался декларировать. Ну да ладно, уже проехали. А задача тестирования на два сомножителя конешно интересная.

Господа!
Позвольте наивный вопрос.
Если некоторого числа нет среди ближайших простых чисел, то есть подозрение, что это число составное.
Лично я совершенно уверен в этом(может быть, зря).
Далее.
Я встречал утверждение, что разложить на множители составное число, в котором сомножителей больше, чем два, намного более просто, чем составное число, являющееся произведением двух простых.
Это так?

Гэм пишет:

Михаил Полянский пишет:Михалычу. В моих попытках ответить на простые вопросики, чтоб сохранить дискуссию, на примере простейшей прогрессии было усмотрено то, чего и не пытался декларировать. Ну да ладно, уже проехали. А задача тестирования на два сомножителя конешно интересная.

Господа!
Позвольте наивный вопрос.
Если некоторого числа нет среди ближайших простых чисел, то есть подозрение, что это число составное.
Лично я совершенно уверен в этом(может быть, зря).
Далее.
Я встречал утверждение, что разложить на множители составное число, в котором сомножителей больше, чем два, намного более просто, чем составное число, являющееся произведением двух простых.
Это так?

Понял. Мы переходим на подозрения. В стиле "это число подозрительно". Так именно этим и занята современная математика, работающая над составными. Мы же не собираемся с этой мащиной соревноваться? Предложение - на этом закончить, меня не устраивает!

Михаил Полянский пишет:

Гэм пишет:

Михаил Полянский пишет:Михалычу. В моих попытках ответить на простые вопросики, чтоб сохранить дискуссию, на примере простейшей прогрессии было усмотрено то, чего и не пытался декларировать. Ну да ладно, уже проехали. А задача тестирования на два сомножителя конешно интересная.

Господа!
Позвольте наивный вопрос.
Если некоторого числа нет среди ближайших простых чисел, то есть подозрение, что это число составное.
Лично я совершенно уверен в этом(может быть, зря).
Далее.
Я встречал утверждение, что разложить на множители составное число, в котором сомножителей больше, чем два, намного более просто, чем составное число, являющееся произведением двух простых.
Это так?

Понял. Мы переходим на подозрения. В стиле "это число подозрительно". Так именно этим и занята современная математика, работающая над составными. Мы же не собираемся с этой мащиной соревноваться? Предложение - на этом закончить, меня не устраивает!

Энто с какой ещё стати заканчивать?:))
Есть некоторая идея.
Оправдается-будет сногсшибательной.
Нет-суда нет.
Самочувствие пока неважное...

Идея - это всегда нормально. Но мы с тобой застряли протискиваясь через одну дверь.
Но мы ведь пока ищем путь - не правда ли?
Что-то ещё? Попробуем.

Михаил, отвечу позднее.
Когда приду к некоторым выводам.

Михалыч пишет:Позвольте +5коп.

Достаточно искать меньший простой сомножитель.

Тестировать целые на простоту, ища их разложение (и не находя!) на множители, не просто нерационально, а безумно нерационально.
Дело в том, что тестирование на простоту - задача решаемая без попыток факторизации и СУЩЕСТВЕННО более быстро.
Предложение об определении простоты через факторизацию это типа "в Рязань из Мск через Кейптаун".
Можно конечно....

А вот задача, решения которой я не знаю, но которая имеет существенно более прикладную значимость, чем тестирование на простоту. По-моему она не решена.
ЗАДАЧА.
Как отличить числа, являющиеся произведением РОВНО двух простых от всех остальных, не прибегая к решению задачи факторизации?

А почему нет таблицы чисел, удовлетворяющих условию двух простых сомножителей?
Мне тут отказали в поиске аналитического решения простоты числа. Есть мол таблицы. А мож помочь таблицы двухсомножительных помочь составить?

Михаил Полянский пишет:

Михалыч пишет:Позвольте +5коп.

Достаточно искать меньший простой сомножитель.

Тестировать целые на простоту, ища их разложение (и не находя!) на множители, не просто нерационально, а безумно нерационально.
Дело в том, что тестирование на простоту - задача решаемая без попыток факторизации и СУЩЕСТВЕННО более быстро.
Предложение об определении простоты через факторизацию это типа "в Рязань из Мск через Кейптаун".
Можно конечно....

А вот задача, решения которой я не знаю, но которая имеет существенно более прикладную значимость, чем тестирование на простоту. По-моему она не решена.
ЗАДАЧА.
Как отличить числа, являющиеся произведением РОВНО двух простых от всех остальных, не прибегая к решению задачи факторизации?

А почему нет таблицы чисел, удовлетворяющих условию двух простых сомножителей?
Мне тут отказали в поиске аналитического решения простоты числа. Есть мол таблицы. А мож помочь таблицы двухсомножительных помочь составить?

У меня вот какой наивный вопрос: чтоб факоризовать произведение двух достаточно больших чисел, компьютерам надо достаточно много времени.
Сколько надо запрашиваемх Вами таблиц, Плянский?
И сколько машинного времени уйдёт на их составление?

Гэм пишет:
У меня вот какой наивный вопрос: чтоб факоризовать произведение двух достаточно больших чисел, компьютерам надо достаточно много времени.
Сколько надо запрашиваемх Вами таблиц, Плянский?
И сколько машинного времени уйдёт на их составление?

Одну таблицу будем запрашивать. Во сколько раз она может оказаться больше таблицы простых? Это нужно посчитать, если такая работа нужна. Помнишь, что можно уменьшить объём таблицы в 100-ни раз?

Как понимаю, запрашиваемая таблица может быть больше таблицы простых практически в бесконечное число раз.
Что этому мешает?

"Помнишь, что можно уменьшить объём таблицы в 100-ни раз?"
Разъясни, наконец, каким образом?
Ты же так ничего и не пояснил...:(

Гэм пишет:Как понимаю, запрашиваемая таблица может быть больше таблицы простых практически в бесконечное число раз.
Что этому мешает?

Ни чего подобного. Открой таблицу простых. Числа двухсоставные лежат между двумя простыми. Далее надо вспомнить закон изменения простых чисел с ростом числа и посмотреть закон изменения количества двухсоставных.

"Помнишь, что можно уменьшить объём таблицы в 100-ни раз?"
Разъясни, наконец, каким образом?
Ты же так ничего и не пояснил...:(

Начал пояснять и в этой теме тоже. Но не интересны оказались мои пояснения на виде самой простой прогрессии.

"

Начал пояснять и в этой теме тоже. Но не интересны оказались мои пояснения на виде самой простой прогрессии.

Кому не интересны?
Ты к кому обращался?

Гэм пишет:"

Начал пояснять и в этой теме тоже. Но не интересны оказались мои пояснения на виде самой простой прогрессии.

Кому не интересны?
Ты к кому обращался?

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

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

Разумеется, интересно.
И всегда было интересно.
Охотно продолжу.

Где именно от своей "квадратной" задачи отказался?:о
Ссылку, плз.
Не мог я отказаться.
Так будь добр, дай ссылку на текст, который так своеобразно понял.

Разумеется, согласен на конкретную задачу.

Ну что, опять игра в молчанку?
Михаил, это становится скучным.

Гэм'у
Просьба обращать внимание на оформление цитат. Там в редакторе есть такая кнопочка, 4-я слева по счёту. Выделить цитируемый текст и на неё нажать. А то не понятно, где Ваши мысли, а где, цитируемого автора.

Владимир Привалов пишет:Гэм'у
Просьба обращать внимание на оформление цитат.

Там в редакторе есть такая кнопочка, 4-я слева по счёту. Выделить цитируемый текст и на неё нажать.

А то не понятно, где Ваши мысли, а где, цитируемого автора.

Благодарю за замечание.
Примерно так, как сделано?

Если есть неясности(или остались)-спросите.
Буду рад ответить.

Гэм пишет:Ну что, опять игра в молчанку?
Михаил, это становится скучным.

Владимир, пожалуйста, давай мне временную скидку на уплотнение активной фазы реальной жизни, Переезжал из лесу в город.
В задаче, которую ты слил на Ферма, только начинал разогреваться. Понял, что по факторизации по Ферма только налью воды. Поэтому предлагаю заняться другим. Мы сможем составить для людей таблицу двухсоставных?

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

Разумеется, интересно.
И всегда было интересно.
Охотно продолжу.

Где именно от своей "квадратной" задачи отказался?:о
Ссылку, плз.
Не мог я отказаться.
Так будь добр, дай ссылку на текст, который так своеобразно понял.

Разумеется, согласен на конкретную задачу.

Понятно, что действительно не совсем понимаем друг-друга. Ты не то, чтобы отказался обсуждать. Просто мне не давал новых предложений, что ещё порешать с пользой. Вот Михалыч дал интересную задачку двухсоставных. Но тут же отказался принимать участие в её решении. Вот и мне теперь скучно тоже. Не будет обоюдного интереса, то и мне тихо сам с собою - скучно.
Скажи, что тебе было бы интересно порешать в теории чисел - постараемся что-нибудь придумать.

Ну вот. Опять застрял. Буду теперь отсыпаться. :о)
Действительно, прав Михалыч. Против решения в общем виде - не попрёшь.
Итак. Рассмотрение прогрессий, которые дают полезный результат в намеченной схеме. Прогрессии детского вида 6k+-1 приводят к ряду прогрессий частного вида (30*2ⁱ)k+r, где i=0,1, 2, 3 ..., r=1,7,11,13,17,19,23,29... 30j... , где j=<i и j=0,1,2,3....
Могу сделать сокращение шагов перебора в 128 раз. Дальнейшее сокращение количества операций [(действий) программы] не удаётся... Всякое дальнейшее (по моей любительской схеме) уменьшение количества шагов действий над прогрессиями влечёт увеличение во столько же раз количество "действий" над остатками. Которые (остатки) выстраиваются заново в прежнем виде исследоваемого ряда... Что это такое, пока не понимаю - цикл...

Жила в том, что количество разных остатков для прогрессий с разностью Q, где могут жить простые, столько, сколько чисел, взаимно простых с Q.
Это количество взаимно простых допускает и явное выражение, но в любом случае оно равно cQ, где с = с(Q) - функция, зависящая от разложения Q на простые, причем 1/2 < c(Q) <1.
Неформально это означает, что с увеличением Q практически пропорционально возрастает и число осттков, подлежащих рассмотрению.
Так на так и получается :)

Спасибо, Михалыч. Количество чисел "взаимно простых с Q", где Q - разность прогрессий. То есть, достаточно искать в интервале ряда чисел, а не весь ряд копать. Интервал определять разностью прогрессий. Но главное - зависимость разнорядки по интервалам от [модуля, остатка, номера интервала ... - не знаю пока]. Пока вижу работу - это и есть главное...
Спасибо Вам - хорошая головоломка - интерес в жизни появился.... - лирика, извините.
Конечно, немного слукавил. Но не в том, что застрял, а в том, что напоролся на "цикль". Не очень осознаю. У этих чисел есть период. Периода составных (простых) - нет. Нет его при любом модуле (прогрессии). НО почему-то они (эти числа) поддаются рассмотрению "по разрядно". А ведь написание числа по разрядам - это ли не есть периодичная схема числа... - я что-то не могу никак увидеть, - а что? :о(