Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
 Воскресная задачка. Числа Ферма с одной степенью  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
В вики есть числа Ферма 2^2^n+1.
https://ru.wikipedia.org/wiki/Число_Ферма

Но нет информации о числах более простых 2^n+1.

Что о них известно?

Можно ли найти среди них простые числа?
6 июл 19, 07:01    [21921910]     Ответить | Цитировать Сообщить модератору
 Re: Воскресная задачка. Числа Ферма с одной степенью.  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Оказывается, можно.

Если числа Мерсенна обозначаются как Мр, то обозначим числа Ферма с одной степенью 2^n+1 как Fр.

Числа Fр имеют в своём составе только 5 простых чисел (числа Ферма).

Но если Fр разложить на простые множители, то получается интересная картина.

Если взять множество простых чисел р, то на диапазоне р от 1 до 200 (больше не позволяет аппарат) можно определить 19 простых чисел.
Для этого необходимо разделить Fр на 3.
Назовем эти простые числа как Fр/3.


Простые числа Fр/3 получаются на диапазоне р от 1 до 200 для
р = 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 43, 61, 79, 101, 127, 167, 191, 199.

Если сравнивать Мр и Fр/3,
то на диапазоне от 1 до 200 имеется только 12 простых чисел Мр.

Можно предположить, простых чисел Fр/3 будет больше простых чисел Мр на любом диапазоне.

Предлагается в задачке:
Попробовать найти следующие простые числа Fр/3.


Если простые числа Мр находятся сравнительно легко с помощью теста Люка-Лемера, то для простых чисел Fр/3 теста пока нет
6 июл 19, 09:22    [21921926]     Ответить | Цитировать Сообщить модератору
 Re: Воскресная задачка. Числа Ферма с одной степенью.  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Можно найти ещё простые числа другим способом.

Находится остаток от деления (Fр -1) на р.
Пусть этот остаток равен а.

Тогда определяется число q = а + 1.

И определяются числа Fр/q.

В результате, кроме простых чисел, определяемых в сообщении 21921926, получаем дополнительные простые числа для значений р:
р = 2, 4, 6, 8, 16, 20, 28 (р = 2, 4, 8, 16 – простые числа Ферма).

Можно найти ещё 2 простых числа, если продолжить операцию деления:
Fр/q/q.

Тогда находим ещё простые числа для значений
р = 9, 10.
8 июл 19, 07:40    [21922413]     Ответить | Цитировать Сообщить модератору
 Re: Воскресная задачка. Числа Ферма с одной степенью.  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Нашел ещё два простых числа Fр/3 для

р = 313, 337.
10 июл 19, 07:53    [21923898]     Ответить | Цитировать Сообщить модератору
 Re: Воскресная задачка. Числа Ферма с одной степенью.  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Нашел ещё простые числа Fр/3 = (2^р+1)/3 для

р = 701, 1709, 2617, 3539, 5807.

Всего получается 26 простых чисел Fр/3 .
10 июл 19, 16:27    [21924290]     Ответить | Цитировать Сообщить модератору
 Re: Воскресная задачка. Числа Ферма с одной степенью.  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Ранее на топике рассматривались 2 последовательности чисел: Мр и Fр/3.

Попробуем представить эти последовательности в другом виде:
Мр – это (М-1)р, а Fр/3 – это (М+1)р.

Тогда можно создавать другие последовательности в виде (М+k)р, а именно:
2^р – k, где k – произвольное нечётное целое число, либо положительное, либо отрицательное.
13 июл 19, 19:49    [21926215]     Ответить | Цитировать Сообщить модератору
 Re: Воскресная задачка. Числа Ферма с одной степенью.  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Попробуем составить последовательность чисел вида (М-3)р.

Оказывается, среди этих чисел есть простые числа, которые получаются
для р = 2, 3, 4, 5, 6, 9, 10, 12, 14, 20, 22, 24, 29, 94, 116, 122, 150, 174, 545, 689, 694, 850, 1736, 2321, 3237.

Итого, найдено 26 простых чисел в последовательности (М-3)р.

Кроме того, имеется ещё ряд чисел этой последовательности, которые, аналогично (М+1)р, состоят из произведения числа 5 и простого числа.

К таким числам относятся числа последовательности (М-3)р
для р = 11, 15, 23, 35, 71, 95, 183, 579, 759, 1519.
Всего 10 простых чисел, получающихся из деления чисел последовательности (М-3)р на 5.

То есть, можно с помощью последовательности (М-3)р найти 36 простых чисел на диапазоне р от 1 до 3500.
13 июл 19, 20:13    [21926223]     Ответить | Цитировать Сообщить модератору
 Re: Воскресная задачка. Числа Ферма с одной степенью.  [new]
d7i
Member

Откуда:
Сообщений: 445
Gennadiy Usov,
вот Вы, наверное, любите математические задачи.
Подумайте над следующей:
1. Имеется гибкое (пускай резиновое) кольцо с многогранным сечением (правильный N-гранник).
Кольцо имеет N-граней (каждую даже можно окрасить в разный цвет).
Т.е. имеем кольцо с N поверхностями.
2. Разрежем кольцо, повернем на одну грань (пусть по часовой стрелке) и снова совместим.
Получится 1 грань, т.е. односторонняя поверхность (Мёбиуса).
3. Продолжим повороты. Число поверхностей всё время будет разным.

Требуется выяснить формулу (правило) для определения числа поверхностей при M-повороте N-гранника в виде вышеупомянутого
кольца. Значения N=1,2 можно откинуть, там всё и так ясно. Начните с N=3 (трехгранное сечение).

Я ответ знаю, но дошел до него эмпирическим путем, так как и близко не математик и математикой никогда не интересовался...
13 июл 19, 21:20    [21926245]     Ответить | Цитировать Сообщить модератору
 Re: Воскресная задачка. Числа Ферма с одной степенью.  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
d7i,

математических задач так много, что за всеми не угнаться.

Пока рассматриваю задачу с последовательностями (М-k)p.

Если хотите, чтобы на форуме решали Вашу задачку, то открывайте СВОЙ топик с этой задачкой, и нет проблем.
13 июл 19, 21:28    [21926250]     Ответить | Цитировать Сообщить модератору
 Re: Воскресная задачка. Числа Ферма с одной степенью.  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
d7i, для классической ленточки Мёбиуса ваша задача звучала-бы

N=2, M=1

Две грани. Один разворот. И есть одна поверхность. Верно?
13 июл 19, 22:05    [21926267]     Ответить | Цитировать Сообщить модератору
 Re: Воскресная задачка. Числа Ферма с одной степенью.  [new]
d7i
Member

Откуда:
Сообщений: 445
mayton
d7i, для классической ленточки Мёбиуса ваша задача звучала-бы
N=2, M=1
Две грани. Один разворот. И есть одна поверхность. Верно?

Для N=2 верно. Это простая лента Мёбиуса.
Я не нашел жесткой формулы, нашел только правило.
Могу дополнительно сообщить, что многогранник с числом граней, равным простому числу, при всех M (кроме M=N),
дает в результате 1 (одну поверхность).
3-,5-,7-,11- и т.д. гранники всегда дают 1 поверхность. Можете проверить, если найдете жруг-кольцо треугольного сечения.
При M>N все последовательности циклически повторяются, поэтому нет смысла проверять варианты при M>N.

В любом случае, я знаю сколько поверхностей будет, к примеру, в результате 3 поворота 12-гранника...
14 июл 19, 00:27    [21926313]     Ответить | Цитировать Сообщить модератору
 Re: Воскресная задачка. Числа Ферма с одной степенью.  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Возможно задача сводится к проверке взаимной простоты M, N.
14 июл 19, 11:29    [21926352]     Ответить | Цитировать Сообщить модератору
 Re: Воскресная задачка. Числа Ферма с одной степенью.  [new]
d7i
Member

Откуда:
Сообщений: 445
mayton, почти горячо.
Задача имеет отношение к простым числам, но самое интересное в ней то, что её можно проверить
экспериментально, физическим, так сказать, методом.
Просто сделайте бумажную развертку жгута многогранного сечения.
Возьмите полоску бумаги и разлинейте её нужным числом граней (полос). Пометьте каждую грань
(номером или цветом).
Соедините в кольцо, совместив грани. А потом сдвиньте на 1 грань (поворот).
Проследите, какие грани переходят в другие (те, что повисли в воздухе, переходят друг в друга.
Запишите переходы.
Проанализировав их, вы увидите, что получилась одностороняя поверхность.
Сдвигайте дальше и анализируйте.
Я провел такой эксперимент до 20-гранника и увидел закономерность.
14 июл 19, 11:41    [21926356]     Ответить | Цитировать Сообщить модератору
 Re: Воскресная задачка. Числа Ферма с одной степенью.  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Я думаю что нам не нужна будет бумага и карандаши.
14 июл 19, 11:55    [21926360]     Ответить | Цитировать Сообщить модератору
 Re: Воскресная задачка. Числа Ферма с одной степенью.  [new]
d7i
Member

Откуда:
Сообщений: 445
mayton
Я думаю что нам не нужна будет бумага и карандаши.

Возможно. Я знаю решение. Можно даже сделать простую программку, строк на 10-15.
А вот как доказать всё это чисто математически, не знаю.
14 июл 19, 13:07    [21926375]     Ответить | Цитировать Сообщить модератору
 Re: Воскресная задачка. Числа Ферма с одной степенью.  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
d7i
mayton
Я думаю что нам не нужна будет бумага и карандаши.
Возможно. Я знаю решение. Можно даже сделать простую программку, строк на 10-15.
А вот как доказать всё это чисто математически, не знаю.
А зачем доказывать?

Есть такое понятие, как эвристика (есть в вики):
проверил на последовательности малых чисел, значит, годится и на больших числах.

Чем больше малых чисел, тем больше уверенности!

Например, на эвристике построено определение решений при расстановке ферзей.
14 июл 19, 13:13    [21926377]     Ответить | Цитировать Сообщить модератору
 Re: Воскресная задачка. Числа Ферма с одной степенью.  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Давайте рассуждать логически.

В вики написано:
… «Поэтому простые числа Мерсенна давно удерживают лидерство как самые большие известные простые числа.»
При этом самым большим известным простым числом является 2^82 589 933-1.

Здесь интересно не само число, а интервалы между предыдущими простыми числами.

Получается, что следующее простое число из чисел Мерсенна будет не скоро, где-то около
2^85 000 000-1.
И это расстояние современная очень быстрая ЭВМ не может преодолеть в разумное время.

А если у нас есть другие последовательности простых чисел, которые по количеству простых чисел на определённых интервалах не уступают простым числам Мерсенна.

У каждой из этих последовательностей то же имеется свой «интервал появления» простых чисел.

И может оказаться, что следующее простое число у одной из этих последовательностей будет простое число, немного больше, чем 2^82 589 933-1.
И для этого числа будет хватать времени на его определения на ЭВМ.

При этом можно будет получить простое число, которое превышает 2^82 589 933-1.

Конечно, такие последовательности должны быть построены на степени числа 2 (а может быть и не 2), поскольку лучше работать со степенями чисел, чем с самими числами.

Жду обсуждения...
14 июл 19, 13:19    [21926379]     Ответить | Цитировать Сообщить модератору
 Re: Воскресная задачка. Числа Ферма с одной степенью  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Теперь рассмотрим последовательность (М+3)р из серии 21926215

Оказывается, среди этих чисел есть простые числа, которые получаются
для р = 3, 4, 6, 7, 12, 15, 16, 18, 28, 30, 55, 67, 84, 228, 390, 784, 1110, 1704, 2008, 2139, 2191, 2367, 2370, 4002, 4060.
Всего 25 чисел.

Кроме того, имеется ещё ряд чисел,
р = 40, 76, 220,
из которых получаются простые числа с помощью деления на 19.
15 июл 19, 09:04    [21926555]     Ответить | Цитировать Сообщить модератору
 Re: Воскресная задачка. Числа Ферма с одной степенью  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
d7i
mayton
Я думаю что нам не нужна будет бумага и карандаши.

Возможно. Я знаю решение. Можно даже сделать простую программку, строк на 10-15.
А вот как доказать всё это чисто математически, не знаю.

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

Типа.
N123456
1
21
3
4


Когда мы ее заполним - то мы скорее всего увидим закономерность.
Взаимная простота и прочее.
15 июл 19, 13:29    [21926750]     Ответить | Цитировать Сообщить модератору
 Re: Воскресная задачка. Числа Ферма с одной степенью  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton,

Вы втягиваетесь в задачу "расстановка ферзей" ( в данном случае - ладей), в то, от чего Вы меня регулярно пытаетесь отвернуть.

Поворот на 1 грань - расстановка ладей на соседних вертикалях на следующей горизонтале
Поворот на 2 грани - расстановка ладей на соседних вертикалях через 1 горизонталь
Поворот на 3 грани - расстановка ладей на соседних вертикалях через 2 горизонтали
и т.д.

Повторы ладей на горизонталях означает, что нет одной грани, а есть несколько граней.
15 июл 19, 14:00    [21926774]     Ответить | Цитировать Сообщить модератору
 Re: Воскресная задачка. Числа Ферма с одной степенью  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Разве ферзёвая доска была тороидальной формы?
15 июл 19, 14:23    [21926796]     Ответить | Цитировать Сообщить модератору
 Re: Воскресная задачка. Числа Ферма с одной степенью  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Разве ферзёвая доска была тороидальной формы?
А зачем нам тор?

Главное понять ситуацию на срезе тора, где всё происходит, и эту ситуацию где-то отобразить.

Например, на ферзевой (ладейной) доске.
15 июл 19, 15:19    [21926866]     Ответить | Цитировать Сообщить модератору
 Re: Воскресная задачка. Числа Ферма с одной степенью  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Ладно флаг тебе в руки.
15 июл 19, 15:47    [21926895]     Ответить | Цитировать Сообщить модератору
 Re: Воскресная задачка. Числа Ферма с одной степенью  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Ладно флаг тебе в руки.
Зачем мне?

Есть d7i, вот ему и флаг в руки.

Только он что-то молчит.
Наверное, ладьи переставляет.
15 июл 19, 16:04    [21926915]     Ответить | Цитировать Сообщить модератору
 Re: Воскресная задачка. Числа Ферма с одной степенью  [new]
d7i
Member

Откуда:
Сообщений: 445
mayton
d7i
пропущено...

Возможно. Я знаю решение. Можно даже сделать простую программку, строк на 10-15.
А вот как доказать всё это чисто математически, не знаю.

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

Типа.
N123456
1
21
3
4


Когда мы ее заполним - то мы скорее всего увидим закономерность.
Взаимная простота и прочее.

Хотите таблицу? Пожалуйста

Поворот01234567
3 гр.3113
4 гр.41214
5 гр.511115
6 гр.6123216
7 гр.71111117


Ну и ?
15 июл 19, 16:05    [21926917]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / Программирование Ответить