Пары близнецов

Автор темы Bat 
ОбъявленияПоследний пост
ОбъявлениеПравила и принципы форума «Высшая математика»28.10.2009 15:17
ОбъявлениеTinkoff Business Analyst / Product Owner19.02.2021 19:06
ОбъявлениеАктуарий в PPF Life Insurance (Junior)25.03.2021 21:35
04.10.2005 18:13
Пары близнецов
Хотелось бы знать, может ли иметь право на существование приведенный ниже проверочный тест пар близнецов?

[ (n + 1)^n – (n-1)^n – 0,5(n^2 + 5n + 2)] mod (n^2 – 1) = 0,
где n – среднее арифметическое близнецов, кратное 6.

Справедливости ради отмечу, что тест "пропускает" числа Кармайкла, имеющие в паре простое число.

04.10.2005 23:07
ошибается не только на числах Кармайкла
Ошибается не только на числах Кармайкла. Например, называет простыми
644±1, 646±1, 1906±1, 2700±1
05.10.2005 10:08
Пары близнецов
Извиняюсь, за то, что упустил, что n должно быть кратно 6 (ошибку исправил).
Из-за этой ошибки появилось число 64401.
Насчет числа 64601 - по моим прикидкам оно простое. Про другие - не могу сказать, может быть они "исчезнут" при новой проверке с учетом моей поправки?
05.10.2005 15:34
не помогает
Цитата

Батороев писал(а) :
Извиняюсь, за то, что упустил, что n должно быть кратно 6 (ошибку исправил).
Это исключает только некоторые ошибки.
n=2700 кратно 6.
Цитата

Батороев писал(а) :
Из-за этой ошибки появилось число 64401.
Причем тут 64401? У меня там стоит знак "плюс-минус".
644±1 это "644 плюс-минус 1".
Настройте фонты.
06.10.2005 18:47
просьба помочь
Опять извиняюсь, теперь за фонты (но как они настраиваются пока не знаю).
Что касается контр-примеров, то из приведенных Вами ранее, по-видимому, осталось число 2700?
Не могли бы Вы подсказать еще, хотя бы пару подобных контр-примеров?
06.10.2005 21:21
да сколько угодно
n = 1104 2466 2700 2820 4680 6600 10260 14490 16704 18720 19950 29340 30120 31608 39864 41040 42798 49140 52632 60702 68100 83664 85488 90750 104652 107184 129888 137148 158370 172080 181902 188460 204000 208464 226800 253242 272250 276012 278544 280602 285540 294270 323712 340560 348162 396270 422658 423792 458988 481572 488880 513630 534060 574860 580338 587862 588744 665280 670032 683760 710532 729060 738540 757944 786960 1004652 1033668 1082400 1141140 1207362 1251948 1302450 1333332 1357620 1507560 1520904 1533600 1549410 1678542 1711380 1735842 1746288 1801968 1827000 1837380 1892184 1896960 1907850 1909002 1937880 1994688 2035152 2085300 2100900 2299080 2419386 2487942 2503500 2510568 2528922 2797920 2811270 2867220 3090090 3146220 3235698 3316950 3336318 3337848 3363120 3435564 3539100 3656448 3726540 3779184 4082652 4259904 4363260

числа Кармайкла исключите сами
07.10.2005 07:27
Господин Батороев, а разве проблема простых чисел близнецов не решена ?
%-)



С уважением,
Борис
08.10.2005 01:36
Тест "дырявый", но
Спасибо Вам за столь содержательный ответ. Присланные Вами числа для меня очень интересны, правда на их "осмысление" потребуется время куда большее, чем сегодняшняя ночь (у нас 5 утра :))

Мы с Вами выяснили, что мой "недавноиспеченный" тест оказался "дырявым" для пар близнецов. Но есть одно "но".
Я проверил присланные Вами числа до 158370 (это мой lim) и везде в паре с ними обязательно присутствует простое число.

Хочу спросить Вас: можно ли проверить слово "обязательно" в моем предположении?
Если предположение верное, то указанный тест, наверное, можно было бы использовать для генерации простых чисел.
08.10.2005 01:45
Я не знаю...
Я увлекся простыми числами не так давно и пока не знаю ничего ни о проблемах, ни о том, решены ли они.
08.10.2005 07:08
генерация??
Цитата

Батороев писал(а) :
Я проверил присланные Вами числа до 158370 (это мой lim) и везде в паре с ними обязательно присутствует простое число.
Сходу найти контр-пример с составными соседями не удалось. Это, впрочем, вовсе не означает, что такого контр-примера не существует.

Цитата

Батороев писал(а) :
указанный тест, наверное, можно было бы использовать для генерации простых чисел.
Как это?
08.10.2005 14:38
проверил первые 100М
Я проверил первые 100 000 000 кратных 6 (т. е. до 600М). Контрпримеров не нашел.

Если Ваша гипотеза верна, то это очень интересно. Вам большой респект.

Кстати, насколько я знаю, проблема простых чисел-близнецов не решена.
08.10.2005 21:01
Что я имел в виду
Я не знаю, правильно ли я использую слова, при объяснении своих мыслей.
В данном случае, я имел в виду то, что, используя тест, мы находим пары чисел, одно из которых не всегда (и Вы это показали на контр-примерах) является простым. Но здесь я рискнул сделать предположение, что второе - ОБЯЗАТЕЛЬНО должно быть простым. И вот это слово "ОБЯЗАТЕЛЬНО" не дает покоя. Как к этому вопросу подойти с точки зрения теории, я пока не знаю...
Если допустить, что предположение верно, то, задавая любое n, мы всегда будем знать, что, если условие, указанное в первом сообщении, выполняется, то в этой паре (n+/-1) всегда должно быть простое число.
Остается проверить пару существующими тестами.
Таким образом, можно отыскивать простые числа в тех величинах, на которое только способно счетное устройство.

Чтобы уменьшить "дырявость" прежнего теста, я попытался составить новый, основанный на проверке 2 условий по принципу "либо-либо":
[(n+1)^(n:2) – (n-1)^(n:2) + 0,5(n^2 – 3n – 2)]mod(n^2 -1) = 0
[(n+1)^(n:2) – (n-1)^(n:2) - 0,5(n^2 – 3n – 2)]mod(n^2 -1) = 0
Не знаю, эффективнее он прежнего или нет. По крайней мере, если соблюдается условие "минус", то достоверность, как мне кажется, должна быть высокой.

08.10.2005 21:23
Спасибо за надежду
Дорогой Alih!
Ваше сообщение вызвало такое чувство, будто я получил 600М $. Очень хочется надеятся, что сумма будет больше :))

Кстати, насколько я знаю, проблема простых чисел-близнецов не решена.
[/quote]

Если имеется в виду доказательство бесконечности пар близнецов, то до недавних пор я сам скептически относился к их бесконечности. Сейчас, я - "колеблющийся".
09.10.2005 11:09
я понял, как это сделано...
Мы берем какой-нибудь тест, типа 2^(p-1) mod p = 0, и применяем его к двум соседям, надеясь, что два псевдопростых, но не простых числа не образуют пару близнецов.

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

Вот несколько пар простое-псевдопростое для Вашего последнего теста (только с минусом). Пар из двух псевдопростых я не видел.

29340
42798
49140
90750
104652
458988
1004652
1251948
1678542
2811270
3539100
5590620
9069228
9995670
11.10.2005 12:42
Re
В общих чертах Вы все правильно поняли.
В данном случае я применил свойства Малой теоремы Ферма.
Слово "развлечение" я бы заменил на "увлечение".
Насчет матриц в степенях, я Вам ответить не могу, т. к. пока до изучения матриц не дошел.

Хотел бы попросить Вас еще проверить второй тест со знаком "плюс" до тех же величин и сообщить контр-примеры.

13.10.2005 07:37
бессмысленно
Цитата

Батороев писал(а) :
Если допустить, что предположение верно, то, задавая любое n, мы всегда будем знать, что, если условие, указанное в первом сообщении, выполняется, то в этой паре (n+/-1) всегда должно быть простое число.
Откуда уверенность, что тест будет часто срабатывать?

Цитата

Батороев писал(а) :
Остается проверить пару существующими тестами.
Если привлекать "существующие тесты", то возникает вопрос - зачем ваш новый тест вообще нужен? Я не вижу в нем никаких преимуществ даже по сравнению с простейшим тестом Ферма.

Цитата

Батороев писал(а) :
Таким образом, можно отыскивать простые числа в тех величинах, на которое только способно счетное устройство.
Может быть и можно, но нужно ли? Учитывая, что есть гораздо более эффективные тесты с доказанными теоретическими оценками вероятности ошибки.
13.10.2005 13:25
Смысл мог бы быть, если...
Дело в том, что данный тест и составлен на основании проверки условий соблюдения Малой теоремы Ферма двух парных чисел друг по отношению к другу:
[(n-1)^n]mod(n+1)=1
[(n+1)^(n-2)]mod(n-1)=1
Таким условиям могут соответствовать (если я все правильно понял из прочитанного в Интернете) только простые числа и псевдопростые числа (к которым относятся и числа Кармайкла).
Таким образом, можно утверждать, что данный тест отыскивает только пары чисел (n+/-1):
либо "простое-простое",
либо "простое-псевдопростое",
либо "псевдопростое-псевдопростое".
Весь вопрос в том, СУЩЕСТВУЮТ или НЕТ в природе пары "псевдопростое-псевдопростое» (именно, в парах (n+/-1)? И можно ли это доказать? Как мне кажется (здесь я могу ошибаться), пары таких «взаимопсевдопростых» чисел могли бы создать только числа Кармайкла, причем не имеющие общих делителей.

Если бы было доказано, что «нет», то тест можно было бы взять на вооружение и вот по каким причинам:
Любой, из существующих ныне, вероятностных тестов (Рабина-Миллера, Лемана и др.) предполагает, во-первых, проведение большого числа раундов на каждом, отдельно взятом, числе, а во-вторых, НЕ ДАЕТ ГАРАНТИЙ, что число простое.
Предложенным же тестом можно, во-первых, достаточно быстро и точно определить пары, в которых существует, хотя бы, одно простое число. С другой стороны, тест не в состоянии сам определить, какое из двух чисел – составное. Зато, и это - во-вторых, с этим достаточно успешно справляются существующие тесты и, в случае, если они сумеют определить, что одно из чисел составное (и мы знаем, что ответ – стопроцентный), то другое будет ГАРАНТИРОВАННО простое (естественно, при условии доказательства указанного выше предположения).
16.10.2005 19:11
нет, это все-таки развлечение
потому что это очень легко. Достаточно просто скомбинировать несколько существующих тестов, дающих ошибку на очень немногих числах. И никто ничего не докажет.

Вот Вам пример. Тест на простоту числа p, если оно оканчивается на 3 или 7:
1) 2^(p-1) mod p = 1,
2) F(p+1) mod p = 0,
где F - число Фибоначчи (F(1)=F(2)=1, F(n+1)=F(n)+F(n-1)).

Число Фибоначчи по модулю, кстати, считается быстро, равно как и степени.
Кто-нибудь, найдите контрпример!


Насчет теста с плюсом, вот несколько к/п:

1104
2466
4680
6600
16704
30120
41040
52632
85488
16.10.2005 20:40
небольшой расчет
Вот тут:
http://primes.utm.edu/glossary/page.php?sort=PRP
написано, что среди 25e9 (e значит *10^) первых чисел доля псевдопростых относительно теста 2^(p-1)=1 примерно 1e-6. Допустим, что у нас есть 25e9 независимых случайных величин и мы тыкаем в две из них в надежде найти пару псевдопростых.
(подсчет грубый, потому что мы реально проверяем через 6).
Какая вероятность успеха? Примерно 1e-12. Вывод: если мы переберем 25 миллиардов чисел, то вероятность найти контрпример будет пара процентов. Все это, конечно, лишь грубая оценка в предположении независимости вероятности псевдопростоты.
16.10.2005 21:48
а можно и заработать
Цитата из R.K.Guy "Unsolved Problems in Number Theory":

Selfridge, Wagstaff & Pomerance offer $500+$100+$20 for a composite n=3 or 7 mod 10 which divides both 2^n-2 and the Fibonacci number u(n+1) or $20+$100+$500 for a proof that there is no such n.
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти