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

Начать новую тему   Ответить на тему

Страница 2 из 3 Предыдущий  1, 2, 3  Следующий

Перейти вниз

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

Сообщение автор Михаил Полянский в Вс Ноя 29, 2009 5:27 pm

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

Вы меня друзья настрополили на эту задачу. А "мы не привыкли отступать".
Иду своим малообразованным путём. Но что-то уже вижу. Мож это и детский сад, но упражнения для мозгов - хорошие.
Почему ряды 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 естественно соответствуют простым.


Последний раз редактировалось: Михаил Полянский (Вс Июл 27, 2014 11:56 am), всего редактировалось 1 раз(а)
avatar
Михаил Полянский
Admin

Сообщения : 3292
АКТИВНОСТЬ : 8718
РЕПУТАЦИЯ : 25
Дата регистрации : 2009-09-16
Возраст : 56
Откуда : Москва

Вернуться к началу Перейти вниз


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

Сообщение автор ????? в Чт Дек 03, 2009 7:27 am

@Михаил Полянский пишет:6k+1=91
k=15
m=10
n=3
a=-5
b=-12

:о)))
Хе.:))
Так и я могу.
А поискать общее решение?

Кстати, Михаил, формула 6k+-1 берёт все простые?
Без исключений?

?????
Гость


Вернуться к началу Перейти вниз

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

Сообщение автор Михаил Полянский в Чт Дек 03, 2009 9:35 am

Гэм пишет: Так и я могу.
А поискать общее решение?
Погоди про общее. Ты мой намёк не понял. У тебя k отрицательное выходит.

Гэм пишет:Кстати, Михаил, формула 6k+-1 берёт все простые?
Без исключений?
Продемонстрировал уже этот факт в этой теме, несколькими постами выше.
Хорошо. Зайдём с другой стороны. Вот доказательство:
Докажем, что прогрессии 6k+-1 содержат все простые числа, кроме 2 и 3.
Весь натуральный ряд:
6k+0 - не может содержать простые
6k+1 - может содержать простые
6k+2=2(3k+1) - не может содержать простые
6k+3=3(2k+1) - не может содержать простые
6k+4=2(3k+2) - не может содержать простые
6k+5 - может содержать простые
Итого: может содержать простые - 6k+1, 6k+5,
а запись 6k+1, 6k+5 эквивалентна записи 6k+-1
avatar
Михаил Полянский
Admin

Сообщения : 3292
АКТИВНОСТЬ : 8718
РЕПУТАЦИЯ : 25
Дата регистрации : 2009-09-16
Возраст : 56
Откуда : Москва

Вернуться к началу Перейти вниз

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

Сообщение автор ????? в Чт Дек 03, 2009 10:01 am

@Михаил Полянский пишет:
Гэм пишет: Так и я могу.
А поискать общее решение?
Погоди про общее. Ты мой намёк не понял. У тебя k отрицательное выходит.

И что?
Не ндравится?
(великодушно:) )Ну ладно.
Применим другую подстановку
m=k-a
n=k-b
И вопрос снят.
Согласен?

Гэм пишет:Кстати, Михаил, формула 6k+-1 берёт все простые?
Без исключений?
Продемонстрировал уже этот факт в этой теме, несколькими постами выше.

Демонстрация отдельных фактов не является доказательством утверждения.
Спроси Михалыча.


Хорошо. Зайдём с другой стороны. Вот доказательство:
Докажем, что прогрессии 6k+-1 содержат все простые числа, кроме 2 и 3.
Весь натуральный ряд:
6k+0 - не может содержать простые
6k+1 - может содержать простые
6k+2=2(3k+1) - не может содержать простые
6k+3=3(2k+1) - не может содержать простые
6k+4=2(3k+2) - не может содержать простые
6k+5 - может содержать простые
Итого: может содержать простые - 6k+1, 6k+5,
а запись 6k+1, 6k+5 эквивалентна записи 6k+-1

Предлагаю всё-таки спросить Михалыча.
Мнение профессионала в этом вопросе весьма полезно.

?????
Гость


Вернуться к началу Перейти вниз

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

Сообщение автор Михаил Полянский в Чт Дек 03, 2009 10:07 am

Михалыч уже ответил в этой теме несколькими постами ранее:
Пусть M фиксировано.
Тогда любое натуральное n принадлежит одной из M арифметических прогрессий A(r)={Mk+r; k=...-1,0,1,2... }, а r - остаток от деления n на M (r = 0,1,...,M-1).
Ясно, что простые могут принадлежать только прогрессиям, у которых "идентификатор" r взаимно прост с М.
При M = 6 таких прогрессий две с r = 1, r=5.
Именно в них и лежат все простые.
avatar
Михаил Полянский
Admin

Сообщения : 3292
АКТИВНОСТЬ : 8718
РЕПУТАЦИЯ : 25
Дата регистрации : 2009-09-16
Возраст : 56
Откуда : Москва

Вернуться к началу Перейти вниз

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

Сообщение автор ????? в Чт Дек 03, 2009 11:09 am

Спасибо, Михаил.
Хотя доказательства, имхо, нет, но мне вполне достаточно того, что есть.

ЗЫ. Не сразу появляются ответы.
Так предусмотрено?
Во избежания спама?

?????
Гость


Вернуться к началу Перейти вниз

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

Сообщение автор Михаил Полянский в Чт Дек 03, 2009 11:15 am

Не знаю, почему - не сразу. У меня - всё сразу.
avatar
Михаил Полянский
Admin

Сообщения : 3292
АКТИВНОСТЬ : 8718
РЕПУТАЦИЯ : 25
Дата регистрации : 2009-09-16
Возраст : 56
Откуда : Москва

Вернуться к началу Перейти вниз

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

Сообщение автор Владимир Привалов в Чт Дек 03, 2009 11:34 am

Хоть бы чего я понимал в ваших разговорах...
И тем не менее, вопрос интересен.
Тем, что в этих простых прячется так называемая константа Лежандра. А я ни к чему... пока не ткнулся случайно сюда. Хотя и раньше видел это число 0.08366 ... но как-то значения не придавал. Моя гипотеза зависит от этого чила.

Владимир Привалов
Модератор

Сообщения : 1835
АКТИВНОСТЬ : 5554
РЕПУТАЦИЯ : 0
Дата регистрации : 2009-09-17
Возраст : 64
Откуда : Россия

http://privaloff.narod.ru/

Вернуться к началу Перейти вниз

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

Сообщение автор ????? в Чт Дек 03, 2009 12:26 pm

@Владимир Привалов пишет:Хоть бы чего я понимал в ваших разговорах...
И тем не менее, вопрос интересен.
Тем, что в этих простых прячется так называемая константа Лежандра. А я ни к чему... пока не ткнулся случайно сюда. Хотя и раньше видел это число 0.08366 ... но как-то значения не придавал. Моя гипотеза зависит от этого чила.
Как полагаете, Владимир, могу я чем-либо быть тебе(можно на "ты"?) полезен?

?????
Гость


Вернуться к началу Перейти вниз

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

Сообщение автор Владимир Привалов в Чт Дек 03, 2009 12:46 pm

Гэм пишет:
Как полагаете, Владимир, могу я чем-либо быть тебе(можно на "ты"?) полезен?
Конечно на ты. С Михаилом уже давно на ты.
Так все друг другу плоезны и так. Все решают какие-то задачи, по интересам.
Вот я и смотрю за вами (за дискуссией) тут, но нефига не понимаю. Знаю, что есть три приближения: Гаусса, Лежандра и Римана. Считается, что лучшее приближение по простым числам, приближение Римана.
Но Лежандр выдал такую константу... Она как бы в тень ушла, когда появилось приближение Римана (сложное выражение, не буду выписывать). А я её хочу вытащить на свет божий. Уточнить, то есть. Так что ваша дискуссия интересна. Только я бы хотел направить именно в это русло.

Владимир Привалов
Модератор

Сообщения : 1835
АКТИВНОСТЬ : 5554
РЕПУТАЦИЯ : 0
Дата регистрации : 2009-09-17
Возраст : 64
Откуда : Россия

http://privaloff.narod.ru/

Вернуться к началу Перейти вниз

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

Сообщение автор Михаил Полянский в Чт Дек 03, 2009 12:58 pm

@Владимир Привалов пишет:Хоть бы чего я понимал в ваших разговорах...
И тем не менее, вопрос интересен.
Тем, что в этих простых прячется так называемая константа Лежандра. А я ни к чему... пока не ткнулся случайно сюда. Хотя и раньше видел это число 0.08366 ... но как-то значения не придавал. Моя гипотеза зависит от этого чила.
Чтобы понять, напиши сначала, о какой зависимости простых от этой константы ведёшь речь. Ну в смысле ссылку дай на обозрение.

Извини, нашёл, в предыдущей теме ты давал эту ссылку :о)
avatar
Михаил Полянский
Admin

Сообщения : 3292
АКТИВНОСТЬ : 8718
РЕПУТАЦИЯ : 25
Дата регистрации : 2009-09-16
Возраст : 56
Откуда : Москва

Вернуться к началу Перейти вниз

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

Сообщение автор Владимир Привалов в Чт Дек 03, 2009 1:20 pm

Да и в этой, в слове СЮДА в предыдущем сообщении.
Полезная ссылочка.

Владимир Привалов
Модератор

Сообщения : 1835
АКТИВНОСТЬ : 5554
РЕПУТАЦИЯ : 0
Дата регистрации : 2009-09-17
Возраст : 64
Откуда : Россия

http://privaloff.narod.ru/

Вернуться к началу Перейти вниз

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

Сообщение автор Михаил Полянский в Чт Дек 03, 2009 1:32 pm

Мне думается, что лучше вот так делать:
http://artefact.sosbb.ru/forum-f8/tema-t74-20.htm#1416[u]
Во-первых, проскочил это слова сюда, не смекнув, что там ссылка.
Во-вторых, не видно, что там за ссылка и я 3 раза открыл одно и тоже.
avatar
Михаил Полянский
Admin

Сообщения : 3292
АКТИВНОСТЬ : 8718
РЕПУТАЦИЯ : 25
Дата регистрации : 2009-09-16
Возраст : 56
Откуда : Москва

Вернуться к началу Перейти вниз

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

Сообщение автор ????? в Чт Дек 03, 2009 4:55 pm

Михаил, повторяю вопрос: что мы ищем?
Простые или составные?
Если составные, то формула простых в этом случае не имеет смысла.
Так что ищем?

?????
Гость


Вернуться к началу Перейти вниз

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

Сообщение автор Владимир Привалов в Чт Дек 03, 2009 4:59 pm

Гэм пишет:Михаил, повторяю вопрос: что мы ищем?
Простые или составные?
Если составные, то формула простых в этом случае не имеет смысла.
Так что ищем?
Ищите всё.
И то и то. Только для составных отдельную тему, чтоб не путать.

Владимир Привалов
Модератор

Сообщения : 1835
АКТИВНОСТЬ : 5554
РЕПУТАЦИЯ : 0
Дата регистрации : 2009-09-17
Возраст : 64
Откуда : Россия

http://privaloff.narod.ru/

Вернуться к началу Перейти вниз

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

Сообщение автор Михаил Полянский в Чт Дек 03, 2009 5:24 pm

Гэм пишет:Михаил, повторяю вопрос: что мы ищем?
Простые или составные?
Если составные, то формула простых в этом случае не имеет смысла.
Так что ищем?
Составные. К ним и формулы. Простые - это то, что останется от составных.
Приближение по Лежандру предложенное пока не впитал, потому ничего определённого не могу ответить пока по Лежандру.
avatar
Михаил Полянский
Admin

Сообщения : 3292
АКТИВНОСТЬ : 8718
РЕПУТАЦИЯ : 25
Дата регистрации : 2009-09-16
Возраст : 56
Откуда : Москва

Вернуться к началу Перейти вниз

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

Сообщение автор ????? в Чт Дек 03, 2009 5:26 pm

" Простые - это то, что останется от составных"
Ну и за каким чёртом искать простые?

?????
Гость


Вернуться к началу Перейти вниз

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

Сообщение автор Михаил Полянский в Чт Дек 03, 2009 5:28 pm

А где я написал, что их ищу?
avatar
Михаил Полянский
Admin

Сообщения : 3292
АКТИВНОСТЬ : 8718
РЕПУТАЦИЯ : 25
Дата регистрации : 2009-09-16
Возраст : 56
Откуда : Москва

Вернуться к началу Перейти вниз

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

Сообщение автор ????? в Пт Дек 04, 2009 8:12 pm

@Михаил Полянский пишет:А где я написал, что их ищу?
Дык что даёт формула 6k+-1, если не простые?
Или она даёт ещё и составные?

А если и то, и это, то в чём её особенная ценнсть?

?????
Гость


Вернуться к началу Перейти вниз

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

Сообщение автор ????? в Пт Дек 04, 2009 8:26 pm

@Владимир Привалов пишет:
Гэм пишет:Михаил, повторяю вопрос: что мы ищем?
Простые или составные?
Если составные, то формула простых в этом случае не имеет смысла.
Так что ищем?
Ищите всё.
И то и то. Только для составных отдельную тему, чтоб не путать.
Я всегда искал только составные.
Это Михаил зачем-то приплёл сюда простые...:))

?????
Гость


Вернуться к началу Перейти вниз

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

Сообщение автор Михаил Полянский в Пт Дек 04, 2009 8:28 pm

Гэм пишет:Дык что даёт формула 6k+-1, если не простые?
Или она даёт ещё и составные?

А если и то, и это, то в чём её особенная ценность?

При разработке алгоритма факторизации важно знать свойсва простых. Ведь дольше всего факторизуется простое. Вот и есть такая задача - отделять простые от составных.
avatar
Михаил Полянский
Admin

Сообщения : 3292
АКТИВНОСТЬ : 8718
РЕПУТАЦИЯ : 25
Дата регистрации : 2009-09-16
Возраст : 56
Откуда : Москва

Вернуться к началу Перейти вниз

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

Сообщение автор ????? в Пт Дек 04, 2009 9:42 pm

Составлен справочный список простых.
Зачем их факторизовать?
Я такой задачи перед собой не ставлю.
А тебе зачем это надо?:)

?????
Гость


Вернуться к началу Перейти вниз

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

Сообщение автор Михаил Полянский в Пт Дек 04, 2009 10:36 pm

Теперь понял. Мы берём числа, которые не входят в справочник простых.
avatar
Михаил Полянский
Admin

Сообщения : 3292
АКТИВНОСТЬ : 8718
РЕПУТАЦИЯ : 25
Дата регистрации : 2009-09-16
Возраст : 56
Откуда : Москва

Вернуться к началу Перейти вниз

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

Сообщение автор ????? в Сб Дек 05, 2009 8:29 am

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

?????
Гость


Вернуться к началу Перейти вниз

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

Сообщение автор Михаил Полянский в Сб Дек 05, 2009 12:17 pm

Гэм пишет:Именно.
Причём наиболее "простые"-состоящие из произведения двух простых.
По определению.
Вполне можно взять числа, состоящие из произведения трёх и более простых чисел, но, на мой взгляд, задача в этом случае упрощается.
Достаточно искать меньший простой сомножитель. Мы перечисляем все эти банальности, воспользовавшись советом Привалова, не упускать ни одной банальности :о)
avatar
Михаил Полянский
Admin

Сообщения : 3292
АКТИВНОСТЬ : 8718
РЕПУТАЦИЯ : 25
Дата регистрации : 2009-09-16
Возраст : 56
Откуда : Москва

Вернуться к началу Перейти вниз

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

Сообщение автор ????? в Сб Дек 05, 2009 12:41 pm

"Достаточно искать меньший простой сомножитель."
Разумеется.
Сколько на это уходит времени при достаточно больших сомножителях?


"Мы перечисляем все эти банальности, воспользовавшись советом Привалова, не упускать ни одной банальности :о)"
Ты. Не мы.
Я давно отказался от этой тривиальности.
А что посоветует в этом случае Привалов?

?????
Гость


Вернуться к началу Перейти вниз

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

Сообщение автор Спонсируемый контент


Спонсируемый контент


Вернуться к началу Перейти вниз

Страница 2 из 3 Предыдущий  1, 2, 3  Следующий

Вернуться к началу


 
Права доступа к этому форуму:
Вы можете отвечать на сообщения