Модифицировать программу (практическая помощь) : Программирование - Страница 22 fixfix
2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 19, 20, 21, 22, 23, 24, 25 ... 47  След.
 
 Re: Модифицировать программу (практическая помощь)
Сообщение19.07.2015, 13:44 


18/11/10
75
Nataly-Mak в сообщении #1038530 писал(а):
То есть паттерны с разностью больше 300 малоперспективны?

А можно сделать программу поиска кортежей сразу по нескольким заданным паттернам? Например, ввести в программу 10 разных паттернов и пусть она их все проверяет.

No, 10 patterns means 10 separate programs.

 Профиль  
                  
 
 Re: Модифицировать программу (практическая помощь)
Сообщение19.07.2015, 13:46 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Jarek
однако есть кортежи в очень широких диапазонах, например:

Код:
7318133876391223: 0 6 30 114 138 264 268 298 546 576 580 706 730 814 838 844
584594952562499: 0 32 68 158 170 228 260 350 510 600 632 690 702 792 828 860
3367680536652371: 0 36 168 186 200 212 302 408 440 546 636 648 662 680 812 848
9585616597901077: 0 76 90 130 142 186 364 412 474 522 700 744 756 796 810 886
12572752443521383: 0 54 114 124 364 390 400 406 444 450 460 486 726 736 796 850
19239181762421659: 0 168 252 264 310 384 390 414 448 472 478 552 598 610 694 862
13319464281880157: 0 42 140 272 294 360 372 440 486 554 566 632 654 786 884 926


-- Вс июл 19, 2015 14:50:24 --

Jarek в сообщении #1038533 писал(а):
No, 10 patterns means 10 separate programs.

Но почему?
Разве программа на может проверять одновременно несколько паттернов?
Например, введены два паттерна. Это означает две последовательные ветви программы:
1. проверка первого паттерна;
2. проверка второго паттерна

Конечно, можно сделать и две отдельные программы.

 Профиль  
                  
 
 Re: Модифицировать программу (практическая помощь)
Сообщение19.07.2015, 13:58 


18/11/10
75
Nataly-Mak в сообщении #1038534 писал(а):
Jarek
Jarek в сообщении #1038533 писал(а):
No, 10 patterns means 10 separate programs.

Но почему?
Разве программа на может проверять одновременно несколько паттернов?
Например, введены два паттерна. Это означает две последовательные ветви программы:
1. проверка первого паттерна;
2. проверка второго паттерна

Конечно, можно сделать и две отдельные программы.

Of course, you can always put 10 separate programs in one code and create one executable, but I find it more convenient to have a separate program for each pattern.

 Профиль  
                  
 
 Re: Модифицировать программу (практическая помощь)
Сообщение19.07.2015, 14:06 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Если мы имеем 10 отдельных программ, тогда нам нужен такой компьютер, на котором можно запускать одновременно 10 программ, а это не у всех имеется.
А если сделать проверку 10 паттернов в одной программе, тогда мы запускаем всего одну программу, что всем возможно сделать.

 Профиль  
                  
 
 Re: Модифицировать программу (практическая помощь)
Сообщение19.07.2015, 15:11 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Попробовала составить паттерн с разностью 252:

Код:
{0 12 30 42 60 72 90 102 126 150 162 180 192 210 222 240 252}

На странице проверки паттерн забраковали.
Конечно, я с потолка составила, алгоритма-то не знаю :?
Там и подкорректировали паттерн:

Код:
{0 12 30 42 60 72 90 102 126 150 164 182 192 210 222 240 254}

Но теперь нарушена симметричность :-(

 Профиль  
                  
 
 Re: Модифицировать программу (практическая помощь)
Сообщение19.07.2015, 16:04 


10/07/15
286
Nataly-Mak в сообщении #1038522 писал(а):
Begemot82
если можно, расскажите, пожалуйста, как вы составляли паттерны, по какому алгоритму. Ваши паттерны оказались хорошими :-)

Второй вопрос на засыпку :wink:
вы можете написать программу поиска реальных наборов по заданным паттернам :?:

Брал пятнашки
5348080416833681: 0 18 30 48 60 66 90 108 126 150 156 168 186 198 216
5531524424792777: 0 12 36 66 102 162 180 186 192 210 270 306 336 360 372
добавлял с краев числа кратные 6, проверял на остатки.
Из первой получилось с добавлением 12 и 24, из второй 18.
Очень удачно получилась минимальная с диаметром 240.
На втором вопросе засыпался.

 Профиль  
                  
 
 Re: Модифицировать программу (практическая помощь)
Сообщение19.07.2015, 16:12 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Begemot82
спасибо за алгоритм.
А я вот пытаюсь подбором сделать из паттернов с диаметром 240 паттерн с диаметром 252.
И нифига не получается :-(

Почему на втором вопросе засыпались? Потому что он на засыпку? :-)
Надо взять исходник whitefox и модифицировать в нём проверку, генерация простых остаётся.

-- Вс июл 19, 2015 17:16:58 --

Например, такой сочинила:

Код:
{0 18 36 48 66 78 84 108 126 144 168 174 186 204 216 234 252}

Проверка бракует последний элемент и заменяет его на 254 :-(

 Профиль  
                  
 
 Re: Модифицировать программу (практическая помощь)
Сообщение19.07.2015, 16:27 


10/07/15
286
Nataly-Mak в сообщении #1038614 писал(а):
Проверка бракует последний элемент и заменяет его на 254

Конечно, потому что полный букет для остатков на 5. Двойка в последнем остатке единственная, заменяем на присутствующую уже четверку и оп-ля. Про симметричность проверка не знает.
+
Выложил в облако результаты поиска КПППЧ длиной 16
https://cloud.mail.ru/public/GMPY/4XTn3AEJi

 Профиль  
                  
 
 Re: Модифицировать программу (практическая помощь)
Сообщение19.07.2015, 16:39 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Begemot82 в сообщении #1038622 писал(а):
Конечно, потому что полный букет для остатков на 5. Двойка в последнем остатке единственная, заменяем на присутствующую уже четверку и оп-ля. Про симметричность проверка не знает.

Это всё понятно. Как сделать хороший паттерн(ы) с разностью 252 :?:

 Профиль  
                  
 
 Re: Модифицировать программу (практическая помощь)
Сообщение19.07.2015, 18:26 
Заслуженный участник


20/08/14
11886
Россия, Москва
Вам перечислить ВСЕ паттерны для КПППЧ длиной 17 и разницей 252? Их есть у меня.
Вот три основных:
0 12 30 36 42 90 96 120 126 132 156 162 210 216 222 240 252
0 6 12 42 72 90 96 120 126 132 156 162 180 210 240 246 252
0 6 12 30 42 90 96 120 126 132 156 162 210 222 240 246 252
И плюс из вот этой КПППЧ длиной 19 можно получить ещё 6 разных паттернов удалением симметричной пары внутренних чисел:
0 6 12 30 42 72 90 96 120 126 132 156 162 180 210 222 240 246 252

Итого будет всего 9 разных паттернов для КПППЧ длиной 17 и разницей 252.

-- 19.07.2015, 18:39 --

Паттерны с большей разницей чем минимальная более вероятно найдутся раньше последней. Это было и с 13, и с 15 (которая с минимальной разницей не найдена вообще), и с 16, и с 20, и с 22. Не вижу причин для 17-ки изменить этому эмпирическому правилу.

С другой стороны, чем больше разница, тем больше возможных паттернов, в частности из-за увеличения количества паттернов, получаемых из КПППЧ большей длины. А для разницы в 408 уже возможны и КПППЧ длиной 25, из каждой из которых можно наделать до 7920 разных паттернов для КПППЧ длиной 17. На самом деле разных паттернов будет конечно сильно меньше, но всё равно сотни (могу и точно подсчитать, но лень).

-- 19.07.2015, 18:48 --

Использовать primesieve и искать не все КПППЧ, а лишь проверять на паттерны - будет сильно медленее. Primesieve за секунду генерит все простые числа в интервале до миллиарда, паттерны же будут встречаться никак не реже одного на каждый миллион. Сейчас проверка на КПППЧ занимает не больше 10% общего времени, если даже с паттернами она будет мгновенной (чего точно не будет), общее ускорение работы не превысит тех самых 10%.

А запускать primesieve для получения простых чисел только в районах возможного нахождения паттернов тем более лишено смысла: 2000 запусков даже для просеивания интервала длиной 400 будет в сотни раз (!) медленнее одного запуска для просеивания интервала 2млрд, как сейчас сделано. Можете убедиться в этом лично: запустите программу whitefox-а с фактором f2000 (для уменьшения размера интервала до 1млн) и посмотрите на скорость ...

 Профиль  
                  
 
 Re: Модифицировать программу (практическая помощь)
Сообщение19.07.2015, 19:45 
Заслуженный участник


20/08/14
11886
Россия, Москва
Begemot82 в сообщении #1038622 писал(а):
Выложил в облако результаты поиска КПППЧ длиной 16
https://cloud.mail.ru/public/GMPY/4XTn3AEJi
Спасибо!
Перепроверил их на реальную длину КПППЧ, оказалось 742шт имеют длину 18, 42шт имеют длину 20, одна длину 22 и одна длину 24 (её приводил сам Begemot82). Покажу здесь 20-ки и 22-ки (18-ки выложу по запросу, файл 63К):

(КПППЧ длиной 20)

(КПППЧ длиной 22)



-- 19.07.2015, 20:06 --

Nataly-Mak в сообщении #1038539 писал(а):
Если мы имеем 10 отдельных программ, тогда нам нужен такой компьютер, на котором можно запускать одновременно 10 программ, а это не у всех имеется.
Такой компьютер имеется у ВСЕХ уже лет так 30. У Вас тоже такой. Уже Windows 1.0 в 1985-м году имела поддержку многозадачности и соответственно могла запускать одновременно хоть 10 программ, хоть 10000 (если памяти у компьютера хватило бы). Все последующие версии Windows лишь улучшали поддержку многозадачности.

Другое дело, что на однопроцессорных одноядерных однопотоковых системах (а много ли таких осталось на руках? не думаю, уже даже телефоны все многоядерные :-) ) запуск одновременно нескольких вычислительных программ не приводит к ускорению всей работы (т.е. уменьшению времени выполнения всего задания) (кроме некоторых исключительных случаев). Но запускать всё равно МОЖНО! Не вводите людей в заблуждение.

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

-- 19.07.2015, 20:20 --

Dmitriy40 в сообщении #1038671 писал(а):
А для разницы в 408 уже возможны и КПППЧ длиной 25, из каждой из которых можно наделать до 7920 разных паттернов для КПППЧ длиной 17. На самом деле разных паттернов будет конечно сильно меньше, но всё равно сотни (могу и точно подсчитать, но лень).
Ошибся, подсчитал точно, из двух возможных КПППЧ длиной 25 с разницей 408 всего можно получить 11880 уникальных паттерна для КПППЧ длиной 17 и разницей 408. Не сотни, а почти 12 тысяч однако.

 Профиль  
                  
 
 Re: Модифицировать программу (практическая помощь)
Сообщение19.07.2015, 20:26 


10/07/15
286
Dmitriy40 в сообщении #1038671 писал(а):
Вот три основных:
0 12 30 36 42 90 96 120 126 132 156 162 210 216 222 240 252
0 6 12 42 72 90 96 120 126 132 156 162 180 210 240 246 252
0 6 12 30 42 90 96 120 126 132 156 162 210 222 240 246 252
Почему эти основные? Вторая и третья тоже получаются из КПППЧ длиной 19. Уточните, пожалуйста.

 Профиль  
                  
 
 Re: Модифицировать программу (практическая помощь)
Сообщение19.07.2015, 20:34 
Заслуженный участник


20/08/14
11886
Россия, Москва
Begemot82
Да, это моя неверная терминология, плюс недостаток в программе, она сначала выдала эти три КПППЧ длиной 17, а потом уже КПППЧ длиной 19. Из которой получаются 8 разных паттернов, два из которых совпадают с этими двумя КПППЧ длиной 17.
На самом деле "основная" КПППЧ тут получается одна первая, не получаемая из КПППЧ большей длины с той же разницой, Вы правы. Но возможно она входит в какую-то КПППЧ большей длины и с большей разницой, это проверить трудно.

-- 19.07.2015, 20:45 --

Да, можно не трудиться проверять вычеты моих паттернов по 2, 3, 5, 7, 11, 13 - все такие числа из паттернов исключены самим принципом построения паттернов. ;-) Вот делимость на 17 и 19 я проверял сам руками/глазами. Делимость (вычеты) на бОльшие числа для КПППЧ 17 и 19 проверять нет необходимости вообще (надеюсь понятно почему).

-- 19.07.2015, 21:11 --

Nataly-Mak в сообщении #1038376 писал(а):
Нашла из английской Википедии выход на страницу, где паттерны проверяются на допустимость.
http://primes.utm.edu/glossary/includes/ktuple.php
Мне кажется тут проверяют на k-tuple, а не на КПППЧ, это очень разные вещи. И получить КПППЧ из k-tuple возможно лишь для тех k-tuples (для k от 16 до 50 включительно), что я указывал выше:
Dmitriy40 в сообщении #1035841 писал(а):
КПППЧ длиной 16 возможны вообще лишь для k-tuplets размером 33, 34, 39, 40, 42, 47. Для первых двух разница в КПППЧ будет 74 (6 разных вариантов), для остальных 82 (10 разных вариантов). Ни из одной из этих КПППЧ нужный квадрат не собирается.
Нечётной длины КПППЧ из них получаются лишь длиной не более 3, об этом тоже писал выше.

-- 19.07.2015, 21:18 --

Nataly-Mak в сообщении #1038381 писал(а):
Я понимаю так, что с разностью 300-400 практически невозможно сочинить подходящий паттерн для нашей задачи;
Вполне возможно и даже совсем не трудно, из КПППЧ длины 25 с разницей 396 можно сочинить 7920 паттернов для КПППЧ длиной 17 (с той же разницей 396). А из второй КПППЧ длиной 25 с разницей 396 можно добавить ещё несколько тысяч паттернов. Выбирайте любой (любые).
Плюс можно рассмотреть и КПППЧ меньшей длины, с меньшей разницей, не получаемые из этих двух КПППЧ длиной 25.
В общем десяток тысяч допустимых паттернов получить вполне легко.

-- 19.07.2015, 21:28 --

Dmitriy40 в сообщении #1038703 писал(а):
Но возможно она входит в какую-то КПППЧ большей длины и с большей разницей, это проверить трудно.
А, нет, не трудно: она входит в КПППЧ длиной 33 с разницей 588. Соответственно и во все КПППЧ меньшей длины (с отрезанными краями).
КПППЧ длиной более 33 я просто не выводил в файл, т.к. малоинтересны.

 Профиль  
                  
 
 Re: Модифицировать программу (практическая помощь)
Сообщение20.07.2015, 07:06 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Эксперимент

Беру два паттерна для КПППЧ длины 17, найденные Begemot82:

Код:
{0 12 30 42 60 72 78 102 120 138 162 168 180 198 210 228 240}
{0 24 42 54 72 84 90 114 132 150 174 180 192 210 222 240 264}

Генерирую простые числа в интервале [1000000, 2000000].
Сгенерировался массив из 70435 простых чисел.
Организую проверку чисел данного массива на наличие КПППЧ, соответствующих заданным паттернам.
Если не напортачила в программе (чем проще программа, тем легче наделать в ней ошибок :-) ), для первого паттерна максимум соответствия - 5 элементов КПППЧ:

Код:
1204669  1204681  1204699  1204711  1204729

для второго - всего 4 элемента:

Код:
1506317  1506341  1506359  1506371

Конечно, выведено только по одному решению, решений с таким количеством соответствий, думаю, будет много; у меня программа работает до первого решения.
И это всё!
Как выполняется процедура проверки, всем понятно. Выше я немного писала об этом.
Алгоритм совершенно прозрачен.
Но вот генератор primesieve я прикрутить не умею :oops:

-- Пн июл 20, 2015 08:28:02 --

Продолжила выданный программой набор из 5 элементов для первого паттерна:

Код:
1204669 1204681 1204699 1204711 1204729 1204741 1204747 1204771 1204789 1204807 1204831 1204837 1204849 1204867 1204879 1204897 1204909

Решение с дырками :D сколько дырок (не простых чисел), не проверяла.

Вполне себе симметричная 17-ка, только... не все числа в ней простые.

 Профиль  
                  
 
 Re: Модифицировать программу (практическая помощь)
Сообщение20.07.2015, 09:42 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Повторила эксперимент в интервале [2000000, 5000000].
Сгенерировался массив из 199580 простых чисел.
Паттерны те же. Для обоих паттернов максимум соответствий - 5 элементов (первые решения):

Код:
3695539  3695551  3695569  3695581  3695599
2429899  2429923  2429941  2429953  2429971

Ну, а сколько будет соответствий в массиве, например, из миллиона простых чисел :?:

Конечно, напасть на КПППЧ, соответствующую заданному паттерну, непросто.
Но что-то надо пытаться делать.
По программе whitefox тоже ведь непросто. Сколько уже крутим и... ни одной 17-ки не найдено!
К тому же, известен опыт Jarek, он ищет кортежи по заданному паттерну и находит их.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 695 ]  На страницу Пред.  1 ... 19, 20, 21, 22, 23, 24, 25 ... 47  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group