Поиск простых чисел

[arseniiv]

(Оффтоп)

Что значит «существование шкал»? Построение любой равномерно темперированной шкалы никаких законов простых чисел вроде не привлекает! Формула частоты $k$-й ступени шкалы с $n$ ступениями в октаве же $f_k = f_0 \cdot 2^{k / n}$. Разве она как-то связана с? Не понял вас.

[Droog_Andrey]

(Оффтоп)

Имелось в виду существование практически применимых, т.е. адекватно звучащих шкал равномерной темперации.

[arseniiv]

(Оффтоп)

То есть, возможность ими аппроксимировать, например, натуральную?

[Ascar]

еще один интересный тестик на простоту от меня

заявка в оеис A186645

рассмотрим числа удовлетворяющие следующему условию

- $2^{n-1}\equiv 1\pmod{n}$
- $n\equiv 1\pmod{b}$

значение $b$ получается следующим образом
сначало находим значение $x$
$2^{n-1}\equiv x\pmod{n*n}$
очевидно, что значение $y$ будет целым числом
$y=(x-1)/n$
и наконец мы определяем значение $b$
$y\equiv b\pmod{n}$
----------------------------------------------------------
первые значения последовательности
7, 11, 13, 19, 31, 71, 127, 379, 491, 2047, 2633, 2659, 8191, 13249, 26893, 70687, 74597, 87211, 131071, 184511, 524287, 642581, 1897121, 2676301, 2703739, 8388607, 15456151, 52368101....

очевидно, что все составные числа этой последовательности принадлежат псевдопростым по основанию 2
последовательность A001567
проверил для всех значений этой последовательности $<=999986341201$
и самое интересное, что исключениями являются только числа Марсенна
$2047=2^{11}-1$; $8388607=2^{23}-1$; $536870911=2^{29}-1$; $137438953471=2^{37}-1$

Самый важный вопрос, существуют ли другие исключения????? не числа Марсена

[Ascar]

модифицировал тест (немного, для повышения результативности) и получил краине интересный результат :)

заявка в оеис A186884

рассмотрим числа удовлетворяющие следующему условию

* $2^{n-1}\equiv 1\pmod{n}$
* $n\equiv 2^{p}\pmod{b}$

где $p>=0$, целое число

значение $b$ получается следующим образом
сначало находим значение $x$
$2^{n-1}\equiv x\pmod{n*n}$
очевидно, что значение $b$ будет целым числом
$b=(x-1)/n$
(аналогично для моего поста выше, значение $b$ находится аналогично)
----------------------------------------------------------
первые значения последовательности
5, 7, 11, 13, 17, 19, 31, 71, 127, 173, 199, 233, 251, 257, 379, 491, 613, 881, 2047, 2633, 2659, 3457, 5501, 5683, 8191, 11497, 13249, 15823, 16879, 18839, 22669, 24763, 25037, 26893, 30139, 45337, 48473, 56671, 58921, 65537, 70687, 74531, 74597, 77023, 79669, 87211, 92237, 102407, 131071, 133493, 181421, 184511, 237379, 250583, 254491, 281381....

очевидно, что все составные числа этой последовательности принадлежат псевдопростым по основанию 2
последовательность A001567

проверил для всех значений этой последовательности $<=999986341201$
и самое интересное, что исключениями являются числа Марсенна
$2047=2^{11}-1$; $8388607=2^{23}-1$; $536870911=2^{29}-1$; $137438953471=2^{37}-1$
и конечноже всплыло еще одно составное число, очень меня порадовало
$4294967297 = 2 ^ {32} + 1$

интересно, что эта последовательность A186884 содержит все простые числа вида $2^{x}-1$ и $2^{x}+1$ (утверждение требует доказательства, пока то что наблюдаем говорит об этом)

что связывает эти числа с другими элементами этой последовательности? кроме условия конечноже :)
существуют ли составные числа другой формы тоже непонятно
вопросов много....

[Ascar]

еще один тест

заявка в оеис A187849

нечетные числа n удовлетворяющие условию
$2^{n-1}\equiv 1\pmod{n}$
$2^{m-1}\equiv 1\pmod{m}$
где
$m=n*p-n+1$; $n=2^k*p+1$; $k$ - целое больше нуля, $p$ - целое нечетное число больше нуля

первые элементы

(Оффтоп)

563, 1291, 1733, 1907, 2477, 2609, 2693, 2837, 3533, 3677, 4157, 4517, 5693, 12809, 15077, 19997, 25603, 28517, 29573, 29837, 31517, 32237, 32717, 34949, 37277, 43613, 43973, 44453, 50333, 52253, 62477, 68213, 69197, 72893, 74717, 77933, 80933, 81773, 83093, 84653, 86117, 92237, 92657, 93893, 95717, 108293, 111053, 121937, 124493, 128477, 129197, 139397, 147773, 148157, 150197, 155693, 156593, 159473, 160757, 163733, 164093, 168677, 169493, 170813, 181277, 186653, 187277, 195197, 197573, 202733, 205133, 210173, 214673, 216653, 223277, 227093, 234197, 236333, 239237, 239333, 248477, 252293, 253637, 260213, 260717, 266957, 271277, 280013, 281837, 282917, 285557, 297797, 302837, 304013, 307277, 309437, 313133, 318833, 323717, 324893, 326597, 344273, 346877, 356453, 360293, 360653, 369917, 379277, 379997, 380333, 387917, 390437, 393077, 395093, 409733, 412277, 418637, 419477, 424843, 433373, 434597, 447197, 448997, 455237, 465173, 466373, 467213, 467333, 468893, 477329, 493733, 499133, 509633, 517613, 517877, 525377, 530837, 534077, 537773, 541133, 544277, 545933, 550973, 554237, 563117, 571973, 577517, 579533, 579883, 590609, 592337, 596573, 602597, 603917, 604613, 605117, 611837, 613637, 628757, 639053, 644597, 647117, 651293, 657197, 657653, 661517, 662357, 665573, 707933, 711653, 724733, 731117, 731597, 733277, 733757, 739373, 743837, 755333, 758453, 767093, 775157, 776453, 781973, 783533, 788093, 788357, 791573, 800117, 819473, 828677, 837077, 837413, 844517, 844913, 852893, 854093, 866717, 868877, 878597, 881477, 896453, 901997, 904517, 912053, 923453, 925517, 926357, 936773, 945293, 948173, 949517, 950693, 961733, 968333, 976013, 979373, 999773, 1005413, 1006613, 1009157, 1027493, 1033493, 1040093, 1049837, 1056053, 1059077, 1064957, 1066757, 1067597, 1068917, 1077677, 1078853, 1088237, 1094453, 1096493, 1106957, 1107053, 1109117, 1114493, 1119653, 1120517, 1130813, 1142237, 1142573, 1147253, 1153613, 1159997, 1165937, 1171637, 1185893, 1205717, 1224533, 1231877, 1233437, 1252877, 1253093, 1254593, 1257317, 1261973, 1272917, 1275683, 1277597, 1292597, 1298117, 1300613, 1303013, 1316213, 1326653, 1327373, 1334357, 1342973, 1344797, 1347569, 1355357, 1383917, 1394993, 1395557, 1399037, 1401809, 1403957, 1423277, 1423757, 1425917, 1447973, 1453493, 1458053, 1462037, 1464773, 1483253, 1489667, 1491773, 1499357, 1504037, 1510493, 1516157, 1522253, 1524077, 1526093, 1535477, 1539653, 1540157, 1568453, 1571237, 1575437, 1583837, 1584413, 1586093, 1590077, 1600037, 1603013, 1607237, 1611293, 1633133, 1644197, 1646033, 1647677, 1667357, 1685837, 1691693, 1696973, 1701137, 1709693, 1716893, 1719413, 1722653, 1730357, 1738973, 1741613, 1743437, 1751693, 1752197, 1763093, 1764293, 1769333, 1778597, 1814237, 1815467, 1816853, 1818413, 1819397, 1822637, 1844477, 1847933, 1855853, 1857677, 1862957, 1863377, 1871477, 1874837, 1885757, 1892357, 1895249, 1897733, 1907729, 1915997, 1921937, 1922213, 1926293, 1934837, 1942757, 1952837, 1954157, 1956533, 1978997, 1989077, 1993637...

проверил до 10^15, нет ни одного исключения
для каждого значения $n$, значение $p$ также будет восновном простым, но исключения уже есть
----------------------------------------------
Есть предположение, что если $k=1$ и $p$-составное число, тогда $p\equiv 0\pmod{3}$
Первые примеры
$n = 1291 = 2 * 645 +1; p = 645 = 215 * 3$
$n = 25 603 = 2 * 12801 +1; p = 12801 = 4267 * 3 $
$n = 424843 = 2 * 212421 +1; p = 212421 = 70807 * 3$
$n = 579883 = 2 * 289941 +1; p = 289941 = 96647 * 3$
$n = 4325443 = 2 * 2162721 +1; p = 2162721 = 720907 * 3$
и т.д.
----------------
подовляющее количество элементов последовательности имеет параметр $k=2$

[maxal]

Ascar в сообщении #417173 писал(а):

рассмотрим числа удовлетворяющие следующему условию

- $2^{n-1}\equiv 1\pmod{n}$
- $n\equiv 1\pmod{b}$

значение $b$ получается следующим образом
сначало находим значение $x$
$2^{n-1}\equiv x\pmod{n*n}$
очевидно, что значение $y$ будет целым числом
$y=(x-1)/n$
и наконец мы определяем значение $b$
$y\equiv b\pmod{n}$
----------------------------------------------------------
первые значения последовательности
7, 11, 13, 19, 31, 71, 127, 379, 491, 2047, 2633, 2659, 8191, 13249, 26893, 70687, 74597, 87211, 131071, 184511, 524287, 642581, 1897121, 2676301, 2703739, 8388607, 15456151, 52368101....

А почему вы неявно исключили случай $b=1$?
Например, $n=3$, для которого $b=1$, также подходит под описание:

$$2^2\equiv 1\pmod{3}$$

$$3\equiv 1\pmod{1}$$

-- Mon Mar 14, 2011 07:47:14 --

Ascar в сообщении #417173 писал(а):

и самое интересное, что исключениями являются только числа Марсенна

Не только. Еще и числа вида n = 2^A001567(k) - 1.

[Ascar]

maxal в сообщении #422819 писал(а):

А почему вы неявно исключили случай $b=1$?
Например, $n=3$, для которого $b=1$, также подходит под описание:

$$2^2\equiv 1\pmod{3}$$

$$3\equiv 1\pmod{1}$$

-- Mon Mar 14, 2011 07:47:14 --

Ascar в сообщении #417173 писал(а):

и самое интересное, что исключениями являются только числа Марсенна

Не только. Еще и числа вида n = 2^A001567(k) - 1.

ну всетаки (mod 1) тут можно подставить любой остаток :)
а мы ищем числа для которых остаток равен 1 и только 1
тройка вообще число фантастическое для меня, оно всегда идет своей дорогой, где бы я на него не натыкался

насчет второго вы правы, осталось выяснить, есть ли исключения не являющиеся числами вида $2^{x}-1$

[maxal]

Ascar в сообщении #422822 писал(а):

ну всетаки (mod 1) тут можно подставить любой остаток :)
а мы ищем числа для которых остаток равен 1 и только 1

Тогда надо писать $n\bmod b = 1$ вместо написанного сравнения.

Но каких-либо преимуществ исключения $b=1$ тут все равно не видно. Даже, наоборот, оно выглядит очень искусственным.

[Ascar]

maxal в сообщении #422825 писал(а):

Ascar в сообщении #422822 писал(а):

ну всетаки (mod 1) тут можно подставить любой остаток :)
а мы ищем числа для которых остаток равен 1 и только 1

Тогда надо писать $n\bmod b = 1$ вместо написанного сравнения.

Но каких-либо преимуществ исключения $b=1$ тут все равно не видно. Даже, наоборот, оно выглядит очень искусственным.

да согласен
умные люди в оеис уже поменяли мне условие
Numbers n such that 2^(n-1) == 1 + b*n (mod n^2), where b>1 divides n-1.
A186645

[maxal]

Ascar в сообщении #422827 писал(а):

умные люди в оеис уже поменяли мне условие
Numbers n such that 2^(n-1) == 1 + b*n (mod n^2), where b>1 divides n-1.
A186645

Вообще-то это я сделал ;)
Но условие $b>1$ лучше бы выкинуть, если вы не возражаете.

[Ascar]

maxal в сообщении #422828 писал(а):

Ascar в сообщении #422827 писал(а):

умные люди в оеис уже поменяли мне условие
Numbers n such that 2^(n-1) == 1 + b*n (mod n^2), where b>1 divides n-1.
A186645

Вообще-то это я сделал ;)
Но условие $b>1$ лучше бы выкинуть, если вы не возражаете.

а и тогда мы добавим 3 для полного комплекта
больше ничего не добавится :)
можно и убрать, не возражаю

пысы ну вы уж там простите что я вас всех там так мучаю своей академической безграмотностью

[maxal]

Ascar в сообщении #422832 писал(а):

а и тогда мы добавим 3 для полного комплекта
больше ничего не добавится :)

Добавится. 29, например.

[Ascar]

maxal в сообщении #422836 писал(а):

Ascar в сообщении #422832 писал(а):

а и тогда мы добавим 3 для полного комплекта
больше ничего не добавится :)

Добавится. 29, например.

извиняюсь непосмотрел
нет не против
я правда незнаю какие тогда еще исключения появяться... но это интересно, если появятся новые исключения, то лучше завести новую последовательность (без b>1), чтоб было видно что там они есть а тут их нету, и из-за чего

[maxal]

Ascar в сообщении #422841 писал(а):

извиняюсь непосмотрел
нет не против
я правда незнаю какие тогда еще исключения появяться... но это интересно, если появятся новые исключения

Последовательность исправил. Новых исключений не обнаружено.