2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 27, 28, 29, 30, 31, 32, 33 ... 41  След.
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение05.11.2021, 03:24 


01/07/19
240
Pphantom в сообщении #1537750 писал(а):
дождитесь какой-нибудь реакции от собеседников

Ок. Жду

 Профиль  
                  
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение06.11.2021, 13:35 


30/03/21
5
Во-первых интервалы могут быть сколь угодно большими. Во-вторых, вычислять их мы не умеем, не находя всех интересующих нас простых чисел, поскольку разбросаны они довольно хаотично. А простые числа быстрее всего искать Быстрым Решетом Эратосфена за O(n)

 Профиль  
                  
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение06.11.2021, 21:52 


23/02/12
2816
hitler

(Оффтоп)

Зачем выбрали такой ник?

 Профиль  
                  
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение06.11.2021, 22:27 


01/07/19
240
hitler в сообщении #1537921 писал(а):
Во-первых интервалы могут быть сколь угодно большими.

Интервалы для каждого праймориала ограничены соответствующим значением функции Якобсталя.
Или вы про другое?
Цитата:
Во-вторых, вычислять их мы не умеем, не находя всех интересующих нас простых чисел, поскольку разбросаны они довольно хаотично. А простые числа быстрее всего искать Быстрым Решетом Эратосфена за O(n)

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

Но вот такая мысль.
Таблица цепочек для какого-то конкретного праймориала позволяет делать перебор в несколько приемов.
Посмотрите, пожалуйста, таблицу для 37#, d=66
https://docs.google.com/spreadsheets/d/ ... sp=sharing
- я вынес в отдельный файл этот случай. 37#

Если оставить числа (оранжевые) только в строках 5 и 7, а в ячейках с D6 по D13 удалить, то в ячейке F2 появится число 13. Это количество пустых столбцов на интервале, не вычеркнутых 5 и 7.
Я перебрал все варианты взаимных расположений пятерок и семерок (т.е., различные числа в ячейках D4 и D5). И только два варианта из них позволяют получить минимум F2=13
Две "ветки" - D4=1; D5=2 и D4=1; D5=3.

Теперь включим следующую строку. Перебираем значения в ячейке D6
Минимум F2=11 у нас достигается только при наборах D4=1; D5=2; D6=3 и D4=1; D5=2; D6=5
А для второй ветви возможен только один минимум - D4=1; D5=3; D6=9

В данном простом случае - 37#, мы легко найдем два известных варианта с помощью такого рода подходящих прикидок.

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

-- 07.11.2021, 00:08 --

И еще одно замечание - по случаю 37#
Две ветки имеют такие особенности:
И в одном, и в другом случае, интервалы Якобсталя "вместились" внутрь пятерок. Т.е., и самое левое число интервала, и самое правое делится на 5. Строка пятерок как бы осталась неподвижной при смещении всех строк. Столбцы 1, 4, 11, 14, 21.

Также, остался неподвижным столбец номер 13 - относительно пятерок. В нем может находиться любая свободная единица, но не попадают цепочечные числа.

Будут ли разветвления в следующих праймориалах обладать подобными особенностями?
Не понятно.

 Профиль  
                  
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение07.11.2021, 11:28 


31/12/10
1553
В интервале d = 282 среди цепочек нет свободных простых, но есть два,
у которых цепочка из 2-х вычетов, один их которых не свободен.
Эти числа не самые большие в модуле ПСВ и их можно считать
условно свободными.

 Профиль  
                  
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение07.11.2021, 20:01 


01/07/19
240
vorvalm в сообщении #1538026 писал(а):
В интервале d=282 среди цепочек нет свободных простых, но есть два,
у которых цепочка из 2-х вычетов, один их которых не свободен.
Эти числа не самые большие в модуле ПСВ и их можно считать
условно свободными.


89 одним вычетом пересекается с 29 (цепочка из 4 вычетов).
97 одним вычетом пересекается с 5 (цепочка из 19 вычетов).

Их как-то можно поменять местами между собой (как это получается со свободными единицами)?
Я не пойму, как это можно сделать.

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

Чтобы его заполнить мы не сможем сдвинуть 97 на позицию 60, так как и у 97 второй вычет непредсказуемо уедет

upd
Увидел свою ошибку. Надо менять местами не те вычеты, которые под верхними цепочками, а те которые свободны. Тогда получается.
Единственное, за чем надо следить - чтобы при смещении строк, один из вычетов не попадал на ограничительный пустой столбец (в данном случае столбец номер 94).

 Профиль  
                  
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение07.11.2021, 20:30 


31/12/10
1553
Yury_rsn в сообщении #1538119 писал(а):
Положение любой цепочки, даже всего лишь из двух элементов, жестко детерминировано в таблице.
Если мы, допустим, поместим число первое число 89 в столбец 6 (где сейчас расположено число 97), то у нас сразу освободится столбец 60 - там, где сейчас находится вторая 89-ка.
Чтобы его заполнить мы не сможем сдвинуть 97 на позицию 60, так как и у 97 второй вычет непредсказуемо уедет

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

 Профиль  
                  
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение07.11.2021, 20:38 


01/07/19
240
vorvalm в сообщении #1538132 писал(а):
Несвободные вычеты цепочки при перемещении свободных могут занять
любое положение в интервале. Это не отразится на остальных цепочках.


Да, спасибо. Я уже увидел.

Значит, для случая n=27, d=282 разветвление не требуется. Количество различных интервалов совпадает с таблицей Циллера. Всего таких интервалов для 103# будет 4 шт.

Кстати, надо тогда посмотреть и другие праймориалы. Может еще где-то этот эффект срабатывает.

 Профиль  
                  
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение07.11.2021, 22:02 


01/07/19
240
До 27 нигде не возникает условно свободных двоек.
Для n=28, 29 нижние строки - условно свободны.
Для n=30 - строка 71.

Пересчитал эти четыре случая. С таблицей Циллера совпало только для n=27 и 30

 Профиль  
                  
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение08.11.2021, 10:59 


23/02/12
2816
Yury_rsn в сообщении #1538160 писал(а):
Пересчитал эти четыре случая. С таблицей Циллера совпало только для n=27 и 30
Значит гипотеза не проходит.

 Профиль  
                  
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение08.11.2021, 13:30 


01/07/19
240
vicvolf в сообщении #1538189 писал(а):
Yury_rsn в сообщении #1538160 писал(а):
Пересчитал эти четыре случая. С таблицей Циллера совпало только для n=27 и 30
Значит гипотеза не проходит.

Наоборот.
Это означает, что в случаях 28 и 29, например, должно быть разветвление.
В таблице Циллера число больше, чем по свободным единицам

 Профиль  
                  
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение08.11.2021, 16:52 


23/02/12
2816
Я правильно понял, что неполный перебор при нахождении максимальных интервалов возможен только при наличии разветвлений? О наличии разветвлений в праймориале Вы узнаете только с использованием таблицы Циллера. А как находить максимальные интервалы для праймориалов больше, чем указаны в таблице Циллера?

 Профиль  
                  
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение08.11.2021, 21:57 


01/07/19
240
vicvolf в сообщении #1538241 писал(а):
Я правильно понял, что неполный перебор при нахождении максимальных интервалов возможен только при наличии разветвлений?

Наверное, надо еще раз сказать, что мы имеем в виду под "разветвлениями".
Пока что мы достоверно знаем только об одном разветвлениии. При 37# -
post1517825.html#p1517825

Разветвление при 37# означает, что для этого праймориала существуют две несовпадающие раскладки чисел по таблице вычетов. Их нельзя перевести друг в друга какой-то взаимной перестановкой расположения вычетов в столбцах между собой. Эта невозможность обуславливается наличием так называемых "цепочек" - это когда в строке вмещается два и больше вычетов. В приведенных выше примерах цепочки образуются в строках 5, 7, 11, 13, 17, 19, 23. И как видно, в каждом из примеров, числа из этих цепочек расположены в разных столбцах, кроме пятерок.

А одиночные числа в строке (свободные единицы) - находятся в строках 29, 31, 37.
Если мы поменяем мысленно местами (т.е., сдвинем их в другие столбцы) эти три числа, то это будут другие интервалы, но "конструкция" их останется прежней - самое левое число интервала будет кратно 5, второе слева - кратно 7, третье слева - кратно 23... И так далее, за исключением столбцов 10, 13, 15.
Сейчас в этих столбцах находятся соответственно числа 37, 31, 29.
И если мы расположим в этих столбцах 31,37,29 или 29,37,31 или 29,31,37 и т.д., то полученный интервал лишь сместится по числовой оси, но на вид останется таким же самым. Следовательно, всего интервалов такого вида для 37# будет 3!, т.е., 6 шт. А также столько же будет "зеркальных" - еще 6 шт.
Но как вычислил Дмитрий, на самом деле, для 37# имеется всего не 12, а 24 различных интервалов длины d=66.

Как выяснилось, это означает, что существует еще одна "ветка". Интервалы, где цепочки располагаются совершенно по-другому. Эти интервалы очень похожи на первую ветку. Цепочки есть в строках с 5 до 23, а свободные единицы тоже располагаются в строках 39,31,37. Но только в других столбцах.
И этих интервалов точно по такой же логике всего будет 12.
Итого, суммарно - 24.

Цитата:
О наличии разветвлений в праймориале Вы узнаете только с использованием таблицы Циллера.

Да, таблица Циллера подсказывает гипотезу, что в некоторых строках должны возникнуть несколько веток. Аналогично 37#.
Но мы пока даже их найти не можем. Слишком большие вычисления требуются.
Цитата:
А как находить максимальные интервалы для праймориалов больше, чем указаны в таблице Циллера?

Пока никак. Нужны "большие" компьютеры.

 Профиль  
                  
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение10.11.2021, 00:18 


23/02/12
2816
У Гербича таблица максимальных интервалов ПСВ до праймориала 57-ого по порядку простого числа.

Однако Dmitriy40 в другой теме считал максимальные интервалы для ПСВ гораздо больших праймориалов. Полным перебором это не сделаешь.

Интересно, какие свойства ПСВ он использовал?

 Профиль  
                  
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение10.11.2021, 01:24 
Заслуженный участник


20/08/14
9596
Россия, Москва
Чтобы понять дайте ссылку где считал.
Скорее всего там были очень сильно ограниченные варианты, потому и можно посчитать дальше. Чем ограниченней, тем дальше.
И вероятно считал не сами максимальные интервалы, а лишь их оценку снизу. Припоминаю даже что сразу же специально это оговаривал, что точные значения на самом деле немного больше.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 615 ]  На страницу Пред.  1 ... 27, 28, 29, 30, 31, 32, 33 ... 41  След.

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

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