Нашёл формулу p = 6k ± 1, но она иногда даёт простое, в одном из случаев (плюс или минус),
а иногда - простые числа-близнецы. Поэтому надо проверять числа на простоту.
>Есть ли какие-либо алгоритмы, или формулы позволяющие генерировать
>гарантированно простое число - заданной битности?
Нет и не может быть.
Всякое простое число, большее 3, представимо в виде 6k + 1 или 6k−1,
где k — некоторое натуральное число.
Таким образом, формула p = 6k ± 1, выдаёт либо простое число,
либо составное (в зависимости от того плюсуется ли 1 или отнимется),
либо сразу выдаёт - простые числа-близнецы (числа простые и при отнимании и при добавлении единицы).
Ты говоришь нет и быть не может, но есть же формулы для диапазонов простых чисел,
как например, следующие прогрессии из простых чисел:
6171054912832631+366384⋅23#⋅n for n=0..24
43142746595714191+23681770⋅23#⋅n for n=0..25
468395662504823+205619⋅23#⋅n for n=0..23
293037522812241983+42713298⋅23#·n for n =0..24
161004359399459161+47715109⋅23#·n for n =0..25
556904117141899+1105111⋅23#⋅n for n=0..21
1059297083391793+408270⋅23#⋅n for n=0..21
660593947782971+5414270⋅23#⋅n for n=0..22
542440132260899+4560607⋅23#⋅n for n=0..22
3465600168789197+3405459⋅23#⋅n for n=0..22
489357377433019+2701556⋅23#⋅n for n=0..22
43760869165417+2339805⋅23#⋅n for n=0..22
1172380401690583+1675204⋅23#⋅n for n=0..22
Где, 23# - праймориал от числа 23.
Он равен 23# = 2⋅3⋅5⋅7⋅11⋅13⋅17⋅19⋅23 = 223092870
Дальше перебирается n - от 0 до числа,
и считаются простые числа:
6171054912832631+366384⋅23#⋅0 = 6171054912832631
6171054912832631+366384⋅23#⋅1 = 6171054912832631+366384⋅23#⋅1 = 6171054912832631+366384⋅223092870⋅1 = 6252792570914711
и т. д. - Все числа простые, если ввести их в wolframalpha.com, и посмотреть там Prime factorization.
Так вот, я думаю, что в распределении чисел k, содержащих простые числа-близнецы - может быть какой-то закон,
зависящий от пи, по формуле Эйлера, или от логарифма какого-нибудь, например от логарифма квадрата пи.
Есть же формула Валлиса.
Диапазон [n!+2 .. n!+n] не содержит ни одного простого числа, т.к. все их можно представить в виде x(n!/x+1). Если n устремляем к бесконечности, получается, что существует бесконечно большой непрерывный диапазон составных чисел. А значит, или перед ним находится последнее простое число (что доказано, что не так) или функция распределения должна перескочить через бесконечность к следующему простому числу, что невозможно.
не понял, к чему кусок про p = 6k ± 1.
существуют k, для которых и 6k+1 и 6k-1 составные.
Дело в том, что
каждое число может быть записано в виде 6n, 6n+1, 6n+2, 6n+3, 6n+4 или 6n+5.
Совершенно очевидно, что
6n всегда делится на 6,
6n + 1 может быть простым,
6n + 2 всегда будет делиться на 2,
6n + 3 на 3,
а 6n + 4 на 2.
6n + 5 может быть простым.
Поэтому кандидаты на простые числа составляют 6n + 1 и 6n + 5.
Можно видеть, что 6n + 5 = 6 (n + 1) -1 = 6x - 1;
и 6n + 5 = 6 (n + 1) -1 = 6x-1
И каждое простое число можно записать в виде 6n ± 1.
>Существуют k, для которых и 6k+1 и 6k-1 составные.
Да, я уже вижу такое k
6×1000000 + 1 = 6000001 = (7^2 × 122449) его факторизация, не простое.
6×1000000 - 1 = 5999999 = (1013 × 5923) его факторизация, не простое.
Возможно, есть какие-то особые свойства у числа k?
Или, быть может, если расписать значения k для чисел-близнецов - в последовательность, вырисуется что-то закономерное?
Первые 100 значений k, начиная от нуля, включительно:
0×6-1 = -1
0×6+1 = 1
1×6-1 = 5 - Числа-близнецы
1×6+1 = 7
2×6-1 = 11 - Числа-близнецы
2×6+1 = 13
3×6-1 = 17 - Числа-близнецы
3×6+1 = 19
4×6-1 = 23 - простое
4×6+1 = 25 - не простое (5×5)
5×6-1 = 29 - Числа-близнецы
5×6+1 = 31
6×6-1 = 35 - не простое (5×7)
6×6+1 = 37 - простое
7×6-1 = 41 - Числа-близнецы
7×6+1 = 43 - Числа-близнецы
8×6-1 = 47 - простое
8×6+1 = 49 - не простое (7×7)
9×6-1 = 53 - простое
9×6+1 = 55 - не простое (5×11)
10×6-1 = 59
10×6+1 = 61 - Числа-близнецы
11×6-1 = 65 - не простое (5×13)
11×6+1 = 67 - простое
12×6-1 = 71
12×6+1 = 73 - Числа-близнецы
13×6-1 = 77 - не простое
13×6+1 = 79 - простое
14×6-1 = 83 - и так далее
14×6+1 = 85
15×6-1 = 89
15×6+1 = 91
16×6-1 = 95
16×6+1 = 97
17×6-1 = 101 - Числа-близнецы
17×6+1 = 103
18×6-1 = 107
18×6+1 = 109
19×6-1 = 113
19×6+1 = 115
20×6-1 = 119
20×6+1 = 121
21×6-1 = 125
21×6+1 = 127
22×6-1 = 131
22×6+1 = 133
23×6-1 = 137
23×6+1 = 139
24×6-1 = 143
24×6+1 = 145
25×6-1 = 149
25×6+1 = 151
26×6-1 = 155
26×6+1 = 157
27×6-1 = 161
27×6+1 = 163
28×6-1 = 167
28×6+1 = 169
29×6-1 = 173
29×6+1 = 175
30×6-1 = 179
30×6+1 = 181
31×6-1 = 185
31×6+1 = 187
32×6-1 = 191
32×6+1 = 193
33×6-1 = 197
33×6+1 = 199
34×6-1 = 203
34×6+1 = 205
35×6-1 = 209
35×6+1 = 211
36×6-1 = 215
36×6+1 = 217
37×6-1 = 221
37×6+1 = 223
38×6-1 = 227
38×6+1 = 229
39×6-1 = 233
39×6+1 = 235
40×6-1 = 239
40×6+1 = 241
41×6-1 = 245
41×6+1 = 247
42×6-1 = 251
42×6+1 = 253
43×6-1 = 257
43×6+1 = 259
44×6-1 = 263
44×6+1 = 265
45×6-1 = 269
45×6+1 = 271
46×6-1 = 275
46×6+1 = 277
47×6-1 = 281
47×6+1 = 283
48×6-1 = 287
48×6+1 = 289
49×6-1 = 293
49×6+1 = 295
50×6-1 = 299
50×6+1 = 301
51×6-1 = 305
51×6+1 = 307
52×6-1 = 311
52×6+1 = 313
53×6-1 = 317
53×6+1 = 319
54×6-1 = 323
54×6+1 = 325
55×6-1 = 329
55×6+1 = 331
56×6-1 = 335
56×6+1 = 337
57×6-1 = 341
57×6+1 = 343
58×6-1 = 347
58×6+1 = 349
59×6-1 = 353
59×6+1 = 355
60×6-1 = 359
60×6+1 = 361
61×6-1 = 365
61×6+1 = 367
62×6-1 = 371
62×6+1 = 373
63×6-1 = 377
63×6+1 = 379
64×6-1 = 383
64×6+1 = 385
65×6-1 = 389
65×6+1 = 391
66×6-1 = 395
66×6+1 = 397
67×6-1 = 401
67×6+1 = 403
68×6-1 = 407
68×6+1 = 409
69×6-1 = 413
69×6+1 = 415
70×6-1 = 419
70×6+1 = 421
71×6-1 = 425
71×6+1 = 427
72×6-1 = 431
72×6+1 = 433
73×6-1 = 437
73×6+1 = 439
74×6-1 = 443
74×6+1 = 445
75×6-1 = 449
75×6+1 = 451
76×6-1 = 455
76×6+1 = 457
77×6-1 = 461
77×6+1 = 463
78×6-1 = 467
78×6+1 = 469
79×6-1 = 473
79×6+1 = 475
80×6-1 = 479
80×6+1 = 481
81×6-1 = 485
81×6+1 = 487
82×6-1 = 491
82×6+1 = 493
83×6-1 = 497
83×6+1 = 499
84×6-1 = 503
84×6+1 = 505
85×6-1 = 509
85×6+1 = 511
86×6-1 = 515
86×6+1 = 517
87×6-1 = 521
87×6+1 = 523
88×6-1 = 527
88×6+1 = 529
89×6-1 = 533
89×6+1 = 535
90×6-1 = 539
90×6+1 = 541
91×6-1 = 545
91×6+1 = 547
92×6-1 = 551
92×6+1 = 553
93×6-1 = 557
93×6+1 = 559
94×6-1 = 563
94×6+1 = 565
95×6-1 = 569
95×6+1 = 571
96×6-1 = 575
96×6+1 = 577
97×6-1 = 581
97×6+1 = 583
98×6-1 = 587
98×6+1 = 589
99×6-1 = 593
99×6+1 = 595
100×6-1 = 599
100×6+1 = 601
Что это за формула такая большая?
Что означают буквы там и как их подставлять, чтоб получить простое число?
Насколько я понял, там, в этом множестве - целая система уравнений, так?
Первая формула Эйлера, интересная.
Быстро реализовал перебор n - на JavaScript, в браузере.
Первые 40 чисел - простые.
0^2-0+41 = 41 - простое
1^2-1+41 = 41 - оно же
2^2-2+41 = 43 - простое
3^2-3+41 = 47 - простое
4^2-4+41 = 53 - простое
5^2-5+41 = 61 - простое
6^2-6+41 = 71 - простое
7^2-7+41 = 83 - простое
8^2-8+41 = 97 - простое
9^2-9+41 = 113 - простое
10^2-10+41 = 131 - простое
11^2-11+41 = 151 - простое
12^2-12+41 = 173 - простое
13^2-13+41 = 197 - простое
14^2-14+41 = 223 - простое
15^2-15+41 = 251 - простое
16^2-16+41 = 281 - простое
17^2-17+41 = 313 - простое
18^2-18+41 = 347 - простое
19^2-19+41 = 383 - простое
20^2-20+41 = 421 - простое
21^2-21+41 = 461 - простое
22^2-22+41 = 503 - простое
23^2-23+41 = 547 - простое
24^2-24+41 = 593 - простое
25^2-25+41 = 641 - простое
26^2-26+41 = 691 - простое
27^2-27+41 = 743 - простое
28^2-28+41 = 797 - простое
29^2-29+41 = 853 - простое
30^2-30+41 = 911 - простое
31^2-31+41 = 971 - простое
32^2-32+41 = 1033 - простое
33^2-33+41 = 1097 - простое
34^2-34+41 = 1163 - простое
35^2-35+41 = 1231 - простое
36^2-36+41 = 1301 - простое
37^2-37+41 = 1373 - простое
38^2-38+41 = 1447 - простое
39^2-39+41 = 1523 - простое
40^2-40+41 = 1601 - простое
41^2-41+41 = 1681 - не простое. Факторизуется как 41^2
42^2-42+41 = 1763 - не простое (41×43)
43^2-43+41 = 1847 - простое
44^2-44+41 = 1933 - простое
45^2-45+41 = 2021 - не простое (43×47)
46^2-46+41 = 2111 - и так далее, дальше лень руками расписывать...
47^2-47+41 = 2203
48^2-48+41 = 2297
49^2-49+41 = 2393
50^2-50+41 = 2491
51^2-51+41 = 2591
52^2-52+41 = 2693
53^2-53+41 = 2797
54^2-54+41 = 2903
55^2-55+41 = 3011 - простое
56^2-56+41 = 3121 - и ещё простые есть, можно их как-то проверить.
57^2-57+41 = 3233
58^2-58+41 = 3347
59^2-59+41 = 3463
60^2-60+41 = 3581
61^2-61+41 = 3701
62^2-62+41 = 3823
63^2-63+41 = 3947
64^2-64+41 = 4073
65^2-65+41 = 4201
66^2-66+41 = 4331
67^2-67+41 = 4463
68^2-68+41 = 4597
69^2-69+41 = 4733
70^2-70+41 = 4871
71^2-71+41 = 5011
72^2-72+41 = 5153
73^2-73+41 = 5297
74^2-74+41 = 5443
75^2-75+41 = 5591
76^2-76+41 = 5741
77^2-77+41 = 5893
78^2-78+41 = 6047
79^2-79+41 = 6203
80^2-80+41 = 6361
81^2-81+41 = 6521
82^2-82+41 = 6683
83^2-83+41 = 6847
84^2-84+41 = 7013
85^2-85+41 = 7181
86^2-86+41 = 7351
87^2-87+41 = 7523
88^2-88+41 = 7697
89^2-89+41 = 7873
90^2-90+41 = 8051
91^2-91+41 = 8231
92^2-92+41 = 8413
93^2-93+41 = 8597
94^2-94+41 = 8783
95^2-95+41 = 8971
96^2-96+41 = 9161
97^2-97+41 = 9353
98^2-98+41 = 9547
99^2-99+41 = 9743
100^2-100+41 = 9941 - простое.
...
>Первая формула Эйлера, интересная.
>n^2 - n + 41
Можно поставить знак плюс, перед n, и тоже много простых чисел выдаст. n^2 + n + 41
Дискриминант выражения n^2+n+41 равен "−163": http://www.wolframalpha.com/input/?i=n%5E2%2Bn%2B41
(Polynomial discriminant: Δ = -163) и это число Хегнера. https://en.wikipedia.org/wiki/Heegner_number
Можно попробовать ещё эти выражения:
n^2 ± n + 17;
n^2 ± n + 55661;
n^2 ± n + 333491;
n^2 ± n + 701147;
Но во-второй формуле, уже вижу одно число не простое это 6^2+6+55661=55703
http://www.wolframalpha.com/input/?i=6%5E2%2B6%2B55661
и оно делится на 53: http://www.wolframalpha.com/input/?i=55703 Prime factorization: (53×1051)
Эти полиномы содержат дофига простых чисел.
В общем виде n^2 - n + x, при различных x:
41 -> можно получить 2208197
55661 -> 2478942 простых чисел
333491 -> 2535780 простых чисел
701147 -> 2587904 простых чисел
Это только если минус n в полиноме, а ещё может быть плюс n.
Ещё нашёл такие полиномы тут:
https://math.stackexchange.com/questions/289338/is-the-notorious-n2-n-41-prime-generator-the-last-of-its-type/289357
n^2 - n + 361637
n^2 - n + 383681
n^2 - n + 601037
n^2 - n + 206807
Наверняка, вместо -n можно прикрутить туда и +n
А ещё нашёл такую последовательность чисел: https://oeis.org/A060392
Так и не понял толком что она значит, но возможно некоторые числа из неё можно использовать в полиномах,
чтоб получить формулу для какого-нибудь длинного диапазона простых чисел.
Тут кто-то в этом разделе как-то писал, что
если перемножить все простые числа
и прибавить единицу получится простое число.
Так вот, это не так. Например:
23# = 1·2·3·5·7·11·13·17·19·23 = 223092870 + 1 = 223092871 - не простое. Его факторизация: (317 × 703763)
>Тут кто-то в этом разделе как-то писал, что
если перемножить все простые числа
и прибавить единицу получится простое число.
Это работает, только если простых чисел конечное число.
>Это работает, только если простых чисел конечное число.
То есть, ты хочешь сказать,
что делители 317 и 703763, на которые делится число 223092871
не принадлежат какому-то множеству, и поэтому число можно считать простым?
Например, после числа 23, следующее простое число 29, число перед ним - 28,
и множество содержащее конечное количество простых чисел 1·2·3·5·7·11·13·17·19·23 -
имеет вид вот такой {0-28}, и ни 317 ни 703763 - не входят в это множество.
Поэтому число 223092871 не разделится ни на одно из чисел от 1 до 28,
являясь при этом простым для этого множества. Всё верно?
Если да, то это так вообще?
То есть дейстительно ли наименьшее из чисел, на которые факторизуется большое число - обязательно вылазит за множество?
И можно ли так генерировать псевдопростые числа заданной битности?
>Что это за формула такая большая?
>Что означают буквы там и как их подставлять, чтоб получить простое число?
Целые неотрицательные числа подставляй вместо букв.
Ты пишешь странно, мне тяжело читать.
Суть в том, что если множество P простых чисел конечно,
то их p=(произведение+1) должно делится на какое-то число из P,
но оно не делится ни на одно из них. Значит либо p простое,
либо делится на какое-то простое число, не лежащее в P.
Но P, по условию, содержит все простые числа. Противоречие.
Поэтому простых чисел бесконечное количество.
В общем я неверно первый ответ написал.
Но суть в том, что тот анон просто не прав,
неправильно понял доказательство, или специально запутал.
При если генерировать эти числа от 1 до 10 - то получается
какое-то большое отрицательное число: https://jsfiddle.net/98o1p5mt
Исходник - открыт там. Можешь нажать кнопку Run и проверить. В консоли браузера - тоже выводится это число.
Можешь проверить код и подправить, если что.
Ну так я и спросил действительно ли оно не делится?
Написал туда (k-1), вместо (k+2). Вот тут исправлено: https://jsfiddle.net/98o1p5mt/3/
Но всё-равно получаются числа большие и отрицательные.
Если генерировать значения переменных от 1 до 10-ти,
то в фигурных скобках получается единица - минус сумма квадратов.
Если эту сумму квадратов заменить буквой x, то видно, что
(k + 2)(1 - x) = k - kx + 2 - 2x = (k + 2) - x · (k + 2)
То есть, при большом x, значение x·(k + 2) будет большим числом, поэтому - результат отрицателен.
https://ru.wikipedia.org/wiki/Простое_число#Формулы_для_нахождения_простых_чисел
Там ещё вот что написано:
>второй множитель этого многочлена (в фигурных скобках) имеет форму: единица минус сумма квадратов.
>Таким образом, многочлен может принимать положительные значения (при положительных k)
>только если, каждый из этих квадратов (т.е. каждый многочлен в квадратных скобках) равен нулю.
>В этом случае выражение в фигурных скобках будет равно 1.
Но тогда, при x = 0, (k+2)·(1-0) = 1·(k+2), и при k = 6, (k+2) = 8 - и это не простое число.
Короче, попробовал ещё засунуть туда отрицательное k вместе с переменными от 1 до 10,
но не получается сгенерировать ни одно простое число.
var k = 0-getRandomInt(1, 10);
176362743236934880
22594341136741948
422074280946015360
28778792198272144
25000295023768
172569879608
Наверное потому, что это k - есть внутри фигурных скобок.
В общем, не понятно как использовать этот многочлен, для получения простых чисел.
Поэтому, наилучшими формулами для генерации простых чисел - я вижу
арифметические прогрессии с PrimeGrid и полиномы, подобные полиному Эйлера,
которые имеют обий вид x^2 ± x + p:
n^2 ± n + 17;
n^2 ± n + 41;
n^2 ± n + 55661;
n^2 ± n + 333491;
n^2 ± n + 701147;
n^2 ± n + 361637;
n^2 ± n + 383681;
n^2 ± n + 601037;
n^2 ± n + 206807;
Но все числа из них полученные - всё-равно надо проверять на простоту.
Например, когда формула имеет вид x^2 - x + p,
при значении x = p, -p + p = 0, и число равно x^2 - получается очевидное не простое, и факторизуется оно как (x · x);
Если число делится на одно из натуральных, в котором лежат числа множества простых,
то это число разделится и на простые числа.
>Ну так я и спросил действительно ли оно не делится?
Пикрелейтед. Страница 57, книга "Простая одержимость. Бернхард Риман и величайшая нерешенная проблема в математике", автор Джон Дербишир.
>что невозможно.
Почему?
Не знаю, я дал тебе направление, ищи сам, я не подставлял туда числа.
>Но тогда, при x = 0, (k+2)·(1-0) = 1·(k+2), и при k = 6, (k+2) = 8 - и это не простое число.
У тебя при k=6 скобка нулём становится?
Нет, я же оставил цитату, и выделил жирным.
Там в википедии написано, что когда каждый из квадратов (и каждый многочлен в квадратных скобках),
равен нулю, то полином Джонса принимает положительные значения.
Я занулил всё в квадратных скобках, чтобы показать, что например при k = 6,
полином даёт положительное число 8, и это не простое число.
Я не вижу списка прогрессий от 0 до 19 в PrimeGrid,
но я вижу, что есть множество арифметических прогрессий у пользователей PrimeGrid.
Сейчас я последовательно перебираю ссылки вида http://www.primegrid.com/ap.php?userid=N,
где N - номер пользователя. И извлекаю прогрессии.
Все эти арифметические прогрессии - запишу в массив, и запхну его - в генератор простых чисел.
Он будет выбирать прогрессию из списка и генерировать n, после чего - возвращать гарантированно простое число.
Я ещё сохраняю номера пользователей, которые содержат в статистике арифметические прогрессии.
Потому что количество таких прогрессий у них может расти по мере продолжения их вычислений.
Я сам, с двумя 1080Ti - нашёл 45 арифметических прогрессий с длинной от 20 до 21, и их количество растёт.
Но в администрации PrimeGrid сказали мне, что они не публикуют такие маленькие прогрессии,
и это по причине их большого количества. Они публикуют только большие открытия и это прогрессии с длиной от 23 до 26.
Я думал, что есть последовательности, вроде OEIS, содержащие все прогрессии с длиной 20 и меньше,
и как только какой-то пользователь находит прогрессию - сразу же эти списки обновляются.
Ан-нет!.. Приходится выколупывать их ещё и руками, лол. Ну... JS помощь, хоть это радует.
>Там в википедии написано, что когда каждый из квадратов (и каждый многочлен в квадратных скобках),
>равен нулю, то полином Джонса принимает положительные значения.
Равен нулю каждый из квадратов или нет зависит от k. Наверняка при k = 6 скобки нулю не равны.
Вот другой вид полинома, на картинке.
k стоит не в каждой квадратной скобке.
После выражений в квадратных скобках происходит возведение этих выражений в квадрат.
Если все квадратные скобки равны нулю, как написано в википедии,
и если это является условием для положительного значения этого полинома,
то скобка (1-0) = 1, и после перемножения (k+2) на эту единицу - остаётся лишь (k+2).
При любом k кратном двум, результат полинома будет делиться на два - и это не простое число.
>Если все квадратные скобки равны нулю
То равны нулю и квадратные скобки с k. Не еби мозг, k нельзя взять с головы здесь.
Уже в 4 формуле сверху при k=6 и при том, что переменные не могут быть отрицательными 0 не получится.
>Сейчас я последовательно перебираю ссылки вида http://www.primegrid.com/ap.php?userid=N
>где N - номер пользователя. И извлекаю прогрессии.
Там, на PrimeGrid.com около миллиона пользователей, вот номер последнего из них: 999980
Я открываю по 50 окон при помощи JS через window.open и закрываю их по одному - у тех, у кого нет прогрессий.
Затем копирую прогрессии в текстовый файл, и засовываю его в скрипт - после этого, получаю массив прогрессий.
Настолько нудное занятие закрывать эти окна. Может есть где нормальные парсеры, чтоб слить все прогрессии с сайта?
Когда будет полный список, может быть даже там найдутся - прогрессии из прогрессий.
>парсеры
BeautifulSoup+lxml
Просто отвечу здесь вот этому древнему анону, может будет проходить мимо: https://2ch.hk/math/res/21096.html#22462
>Хочу создать свою личную криптовалюту, повелся на хайп.
>Но вместо того чтобы компуктеры считали какую то белиберду цифро-буквенную
>хочу сделать так чтобы считалась математическая белиберда.
>Сейчас я только додумался заставить комплекторы перебирать все числа от двух до бесконечности
>на простоту и вести в блокчейн записи уровня "2 простое число, 6 делится на 1-2-3-6,
>147 делится на 3-7-21-49, т.д."
>Нахуя? Потому что могут. Ну и плюс потом в будущем, ящитаю,
>возможно понадобится кому то знать является ли число >1749369875873489562938483726489517389910463036490265936748495727659474191037703763535 простым или нет.
>Числа Mерсена вычислять нихуя не подходит, так как только НЕКОТОРЫЕ из чисел мерсена простые,
>возможно что даже конечное множество. А еще они пропускают некоторые простые числа при последовательном увеличении степени
>Есть еще что то такое чем математика может занять вычислительные мощности?
Итак, во-перых...
Хранить факторизацию простых натуральных чисел - в блокчейне, неебически сложная задача. Особенно для таких больших чисел.
Если хочешь знать на что делится число 1749369875873489562938483726489517389910463036490265936748495727659474191037703763535
то есть его факторизацию - просто введи его в wolframalpha.com
http://www.wolframalpha.com/input/?i=1749369875873489562938483726489517389910463036490265936748495727659474191037703763535
Prime factorization:
5×7×11×29×199×1213×5477×1160608367×316134229883×323004876255732144171530186386683923776150893770761
Перемножить их можешь тут: http://osvarke.info/477-nauchnyj-onlajn-kalkulyator.html
Простых чисел Мерсенна - всего 50. Наибольшее из них - 277232917 − 1 нашли в проекте GIMPS, в декабре 2017-го.
Если уж в блокчейн совать числа, то лучше научиться ужимать их оптимальнейшим образом, вот так, как делают эти:
http://www.primegrid.com/primes/mega_primes.php
В одной транзакции блокчейна - можно запхнуть миллион простых чисел.
Ну и конечно же, если бы они были записаны вряд, то можно было бы генерировать простые числа из них,
из этих предыдущих простых чисел - попыткой деления на них, и даже переводить их - с кошелька на кошелёк,
находя всей сетью - следующее простое число. Всё это вместе упаковывалось бы в различные прогрессии,
которые могли бы описываться множеством переменных.
Но право на числа в блокчейне висело бы на адресах. Они могли бы котироваться, шифроваться, и сами использоваться для шифрования.
К тому же эмиссия простых чисел - ограничена. https://ru.wikipedia.org/wiki/Теорема_о_распределении_простых_чисел
И сложность их добычи - занимала бы весь хешрейт сети.
Ещё сюда добавлю ответ вот на это:
>Если кто не понял что я хочу, математические проблемы которые пока не имеют способов решения кроме как тупым перебором.
>Чтобы суть задачи вроде простая как два пальца обоссать асфальтом, типа последовательности простых чисел 2-3-5-7-11-13-17-19-23-29-31, а найти >например 867 простое число, кроме как тупо перебирать все числа с калькулятором, невозможно было.
В вольфраме для этого есть специальная опция. Например - миллиардное простое число. https://www.wolframalpha.com/input/?i=1,000,000,000th+prime
>все их можно представить в виде x(n!/x+1)
У тебя две переменные там.
Откуда ты это взял?
Представь мне число 999999999989 в через факториал.
Я знаю, что есть https://ru.wikipedia.org/wiki/Факториальное_простое_число
но это отдельный тип чисел. Среди них нет 11 и 13 - а это числа близнецы.
К тому же, В 2013 году Итан Чжан отправил в журнал Annals of Mathematics статью,
в которой доказывалось что существует бесконечно много пар последовательных простых чисел
с разностью не более 70 миллионов.
Слил вот этот сайт себе http://primos.mat.br/ - тут 50 гигов последовательных простых чисел.
Перевёл его на русский - и повесил вот сюда: https://42k5tcpg7bhjjaze.onion/primes/
В TOR-Browser быстрее открывается, но если из WEB'а ломиться, то можно зайти вот так:
http://vobhod.org/browse.php?u=http%3A%2F%2F42k5tcpg7bhjjaze.onion%2Fprimes
или так: https://42k5tcpg7bhjjaze.onion.to/primes/
Затем, после того, как слил сайт - написал прогу на питоне для проверки чисел по списку,
делением их - на все простые, до корня из числа. Она есть там на страницах why.
Удобно юзать списки, очень быстро проверяется числа.
Сейчас от нехуй делать - бручу у себя, питоном, второй триллион среди всех нечётных чисел,
p = 6k ± 1 исключив другие из этих:
условие для цикла: if (i%6==3) or (i%6==2) or (i%5==0): continue;
Количество чисел - проверяю в вольфраме, запросом prime[начальное_простое, конечное]
А их можно как-то ещё сильнее ужать - особенно те, что в конце?
Ну - чтоб не расписывать их полностью...
Файл Ate_100G_part1.txt из архива Ate_100G_part1.7z занимает 90,1 МБ (94 484 450 байт),
сам архив 11,9 МБ (12 536 200 байт).
А предпоследний текстовый файл из архива, с 10-ю миллионами чисел который,
так он вообще 124 МБ (131 000 000 байт) занимает.
Может простые числа, можно представить как в PrimeGrid - каким-нибудь разложением?
То, что все простые числа могут быть представлены как 6k ± 1, уже позволяет сжать их,
записав только значение k и один бит рядом, соответствующий либо сложению либо вычитанию единицы...
Может это поможет: https://books.google.com/books?id=P5H9AgAAQBAJ&pg=PA332
Каждое простое число (кроме чисел вида 8n-1) можно представить в виде суммы трех квадратов.
Наверняка и числа вида 8n-1 можно как-то разложить.
Например, вот так:
8n-1 = a^2 + b^2 + c^2
n = 1/8(1 + a^2 + b^2 + c^2)
>У тебя две переменные там.
>Откуда ты это взял?
Все числа этого диапазона имеют вид n! + x, где x = 2..n. А n! + x это x(n!/x+1). Два множителя - число составное.
Потому что бесконечность бесконечна.
Они там - по цифрам пишутся, текстом, через разделитель.
Можно минусовать триллион от каждого, и записать этот триллион - в начале файла.
Можно ещё, ужать текст - в сами числа, тогда выйдет не более 6 байт на каждое число, и разделитель тогда не нужен будет.
Но думаю, лучше, наверное, оставить в виде текста (так понятнее что за файл) и использовать архиватор.
А ещё, думал разложить числа в степени двойки и записать сами степени.
То есть сами адреса бит, или последовательность их смещений относительно номера предыдущего адреса с единичным битом.
Но если так жать файл, там будет неведомый HEX внутри, читаемый только программой, и его можно удалить ненароком.
На данный момент, я нашёл около миллиона чисел, свыше триллиона.
На квадраты - долго раскладываются каждое из чисел. Уже проверил двумя циклами.
К тому же тройка чисел a, b, c - больше бит занимают вместе, чем само число.
>существует бесконечно большой непрерывный диапазон составных чисел
Я-то думал эти диапазоны можно исключить в коде, чтоб ускорить проверку чисел на простоту.
Ну ты там это... Поставь вместо n, хотя-бы 20, и ты увидишь насколько это "бесконечно большой диапазон" -
с разницей лишь в 18 натуральных чисел. :)
Хаххахх. А факториал от бесконечности считать научишь-то?
Кстати, вот тут https://alexlotov.livejournal.com/540579.html
можно видеть, что диапазон [(70млн. + 1)! + 2, (70 млн. + 1)+(70 млн. + 1)] - таки не содержит ни одного простого числа.
А тебе прям _гарантированно_ нужно или сойдет вероятность 0.999999 (столько девяток сколько сам захочешь)?
Именно вот - гарантированно простое, и именно заданной битности.
Вот, смотри - есть например, алгоритм RSA: https://ru.wikipedia.org/wiki/RSA#Пример
По нему, сначала, выбираются два простых числа - это p и q,
из них - получают n, их перемножением (p×q), и потом считают функцию Эйлера - φ(n).
Для любого одиночного простого числа, φ(p) = (p-1),
то есть функция Эйлера - равна ВСЕМ натуральным числам, стоящим до него,
Поэтому φ(n) = (p-1)(q-1), если n = p×q, где p и q - простые числа.
>или сойдет вероятность 0.999999 (столько девяток сколько сам захочешь)?
А так-то, если речь идёт о "вероятности простоты",
то сошло бы и любое нечётное псевдопростое, или "возможно простое".
Ведь функция Эйлера имеющая вид φ(p) = (p-1), для непростого числа не совсем корректна,
и если число делить, и если оно таки-разделится,
то где-то обязательно появляются нули, а из-за этого могут быть лаги.
Но у любом нечётного, даже если оно разделится на какое-либо число до его половины (или на какое-то простое до его корня),
всё-равно деление его на делители, в диапазоне - от половины этого числа до самого этого числа, даёт какой-то ненулевой статок.
На пикрелейтед видно, что шарики в конце - перекатываются по одному.
Например, если взять число 77, и представить его в виде (частное×делитель + остаток),
то по возрастанию делителя видно, что:
77 =
38×2 + 1 =
25×3 + 2 =
19×4 + 1 =
15×5 + 2 =
12×6 + 5 =
11×7 + 0 (разделилось на 7) =
9×8 + 5 =
8×9 + 5 =
7×10 + 7 =
7×11 + 0 (разделилось на 11) =
6×12 + 5 =
6×12 + 5 =
5×13 + 12 =
5×14 + 7 =
5×15 + 2 =
4×16 + 13 =
4×17 + 9 =
4×18 + 5 =
4×19 + 1 =
3×20 + 17 =
3×21 + 14 =
3×22 + 11 =
3×23 + 8 =
3×24 + 5 =
3×25 + 2 =
2×26 + 25 =
2×27 + 23 =
2×28 + 21 =
2×29 + 19 =
2×30 + 17 =
2×31 + 15 =
2×32 + 13 =
2×33 + 11 =
2×34 + 9 =
2×35 + 7 =
2×36 + 5 =
2×37 + 3 =
2×38 + 1 =
1×39 + 38 (тут делитель уже больше половины числа - 38.5) =
1×40 + 37 (дальше, когда шарики в числе уложены в два ряда, то эти шарики перекатываются по одному) =
1×41 + 36 =
1×42 + 35...
И при увеличении частного на единицу - остатки убывают на единицу.
Поэтому, если выбрать делитель больше половины числа, криптосистема должна будет работать,
однако для внешнего криптоаналитика, наличие единицы в частном - будет немалозначимым,
и может позволить ему восстановить само число.
Заметь, что при делителе до половины числа (от 2 до 38) - имеет место быть, непоследовательное распределение остатков,
и поскольку частное в модульной арифметике - не учитывается, а только остатки,
то получить из остатков само число (77) - трудно.
А в случае единицы в частном, можно получить и само число (оно равно делитель + остаток).
>Ну ты там это... Поставь вместо n, хотя-бы 20, и ты увидишь насколько это "бесконечно большой диапазон"
Ну ты подумай, что будет быстрее для очень больших чисел, проверка на простоту или проверка на то, является ли это число числом вида n!+x, x<n+1 (по сути можно просто занести их в массив до определенного n).
Можно хранить простые, например, как пару (n,k), где 30n+k твое число.
Да, при длинных числах, хоть этот диапазон чисел и незначителен, но нагрузка на проверку числел - падает, если пропустить этот диапазон,
ведь для проверки надо делить на все простые до корня от числа, и проще проверить большие числа - сразу уже так.
>Можно хранить простые, например, как пару (n,k), где 30n+k твое число.
Ой, тут на самом деле закралось - некое подобие решета Эрастофена: http://www.codenet.ru/progr/alg/normalize/
>N = {30n+1} + {30n+7}+ {30n+11} + {30n+13}+ {30n+17} + {30n+19}+ {30n+23} + {30n+29} , n = (0, ∞]
С виду, формула имеет вид x⋅n+p, где p - простое число, которое ты обозначил как k.
Число x = 30 - означает количество строк в таблице, на пик1.
Числа, k которые прибавляются - а это 1, 7, 11, 13, 17, 19, 23 и 29 - они все простые (я их обозначил как p),
и они означают количество первое число из невычеркнутых строк, в таблице.
Простые числа 2, 3 и 5 вместе с кратными им строками - вычеркнуты, поэтому они исключены из ряда натуральных N.
На картинке 2, видно, что строк может быть больше (x = 210 и 2310),
если вычеркнуть все строки кратные числам k = 7 и 11.
Тогда, ряд натуральных N, для поиска простых чисел - должен будет принять вид, наподобие:
N = {210n+1} + {210n+11} + {210n+13}+ {210n+17} + {210n+19}+ {210n+23} + {210n+29} + ... + {210n+199}
где, вместо "..." - вот это вот всё: https://www.wolframalpha.com/input/?i=prime%5B0,210%5D
Таким образом, простые числа могли бы быть выражены как x⋅n + p,
где x - количество строк (второй столбец на пик2),
p - как мне кажется - простое число от нуля до максимального количества строк,
n - какое-либо натуральное число.
Так, например, простое число 1000079817311 может быть записано следующим образом: p = xn + k
Но я вижу, что некоторые остатки k - не простые:
1000079817311 =
6 ⋅ 166679969551 + 5 (простое) =
30 ⋅ 33335993910 + 11 (простое)=
210 ⋅ 4762284844 + 71 (простое) =
2310 ⋅ 432934985 + 1961 (тут остаток - не простое, оно равно 37×53) =
30030 ⋅ 33302691 + 6581 (простое) =
510510 ⋅ 1958981 + 427001 (простое) =
9699690 ⋅ 103104 + 2979551 (простое) =
223092870 ⋅ 4482 + 177573971 (простое) =
6469693230 ⋅ 154 + 3747059891 (не простое, факторизуется как 109×1629119) =
200560490130 ⋅ 4 + 197837856791 (простое) ...
C чего бы это?
Но даже если записывать простое число как x⋅n + k, где остаток k может быть составным,
то как видно, пара чисел n, k - занимает больше бит, чем двоичный вид самого числа.
Поэтому в списке первых 10 миллионов чисел, следующих за триллионным натуральным:
prime[1000000000000, 1000276307647] https://www.wolframalpha.com/input/?i=prime%5B1000000000000,+1000276307647%5D
можно просто минусовать один триллион, и писать сам остаток - в виде бит.
Вот так 1000079817311 = 1000000000000 + (79817311->в файл)
так как запись остатка:
100110000011110101001011111(2) = 79817311(10) намного короче чем запись числа
1110100011011001011001101111101001011111(2) = 1000079817311(10)
При этом, последнее 10-миллионное число 1000276307647 имеет остаток
10000011110000001111010111111(2) = 276307647(10)
00010000 01111000 00011110 10111111, и это - по 4 байта на каждое число, а не по 5:
11101000 11011001 01100110 11111010 01011111 (для полной записи числа)
и уж тем более не по 13 байт - если писать однобайтными симолами все цифры числа.
Но я буду всё-же писать их в файл символами (+ затем ужму 7z) - просто так читабельнее для txt.
>то как видно, пара чисел n, k - занимает больше бит, чем двоичный вид самого числа.
если хранить в двоичном формате, то неясно, что служит разделителем чисел. И опять же ты хранить в txt, так что xn + p может быть эффективнее
>если хранить в двоичном формате, то неясно, что служит разделителем чисел.
Можно выделить на каждое число в конкретном диапазоне - по x байт, тогда и разделитель не нужен.
Например, в диапазоне https://www.wolframalpha.com/input/?i=prime%5B1000000000000,+1000276307647%5D
первое простое число 1000000000039 последнее 1000276307647.
В двоичный вид их:
1110100011010100101001010001000000100111(2) = 1000000000039(10)
1110100011100101000111010010111010111111(2) = 1000276307647(10)
Теперь по байтам:
11101000 11010100 10100101 00010000 00100111 - 5 байт по 8 бит.
11101000 11100101 00011101 00101110 10111111 - тоже.
Но если отнимать триллион от каждого числа, то первое число может быть представлено просто как 39,
последнее - как 276307647.
Итого:
100111(2) = 39(10)
10000011110000001111010111111(2) = 276307647(10)
и двоичный вид их может быть выражен четырьмя байтами на каждое число:
00000000 00000000 00000000 00100111 - 4 байта
00010000 01111000 00011110 10111111 - тоже.
Причём без всяких разделителей. Количество байт и триллион к суммированию - в начале файла указать, и всё.
Но если так делать, файл с простыми числами будет бинарным, а не текстовым.
Можно убить много времени на его создание, а потом тупо забыть,
и ненароком удалить из-за неведомой, нечитабельной хуиты внутри.
>И опять же ты хранить в txt, так что xn + p может быть эффективнее
Я тебе уже показал, что запись двух чисел не снижает количество бит на число.
Но, наглядно, покажу ещё раз:
1000079817311 = 30 ⋅ 33335993910 + 11
1110100011011001011001101111101001011111(2) =
11101000 11011001 01100110 11111010 01011111(2) = 1000079817311(10) - само число, 5 байт.
11111000010111110101110011000110110(2) =
00000111 11000010 11111010 11100110 00110110(2) = 33335993910(10) - частное 5 байт.
1011(2) =
00001011(2) = 11(10) - остаток - 1 байт.
11111000010111110101110011000110110+1011 даже если не дополнять нулями и не делить по байтам,
нужен разделитель, и по длине два числа почти как полная запись одного числа. Разве что минус 1 бит.
Иначе - 6 байт, вместо пяти на каждое число, а это уже - избыточно, и писать само число.
>и писать само число.
и проще - писать само число.
Информация в принципе несжимаема. Если есть число N, то для его хранения необходимо минимум ceil(log2(N)) бит и именно столько число N занимает в двоичном виде. Любые другие формы записи этого числа потребуют больше бит для его хранения.
Сделал там в TOR'е - отдельную папку FOLDER_FOR_UPLOADS, куда можно загружать всякие файлы на сервер.
У кого есть списки простых чисел или какие-то программы для параллельного поиска их видеокартами - можете залить.
Ну и алсо, всякую хуйню можете ещё позаливать, типа котиков-наркотиков, лол.
http://www.primegrid.com/primes/mega_primes.php с тобой несогласны.
Их записи занимают намного меньше бит.
Это частные случаи. Универсального способа записать любое число так, чтобы оно занимало меньше бит, чем в двоичном виде - не существует.
Так-то можно и список всех простых чисел на серверах гугла составить, а у себя хранить только их индексы. Первые 264 простых чисел будут всего по 8 байт.
>Так-то можно и список всех простых чисел на серверах гугла составить, а у себя хранить только их индексы.
>Первые 264 простых чисел будут всего по 8 байт.
Вольфрам Альфа, по всей видимости, так и делает.
В запросе http://www.wolframalpha.com/input/?i=prime%5B1000082617987,1000082617987%5D
можно видеть одно простое число 1000082617987.
Если же навести курсор на него и выбрать plaintext, то видно следующее: Prime[Range[37610901576, 37610901576]].
Такие запросы не работают в вольфраме, но это порядковый номер,
индекс - этого простого числа, в диапазоне от нуля до его самого.
В этом можно убедиться, если ввести тут https://primes.utm.edu/nthprime/index.php
в поле Pi function - само это число:
>There are 37,610,901,576 primes less than or equal to 1,000,082,617,987.
А также, если ввести в Nth Prime индекс - 37610901576:
>The 37,610,901,576th prime is 1,000,082,617,987.
вот это оно и есть.
Я также вижу что у них там и про алгоритм что-то написано, но ничего не понял.
>Я также вижу что у них там и про алгоритм что-то написано, но ничего не понял.
Зато там есть пи-функция от 1 до 30 триллионов:
>There are 1,000,121,668,853 primes less than or equal to 30,000,000,000,000.
триллионное простое число со значением около 30 триллионов:
>The 1,000,000,000,000th prime is 29,996,224,275,833.
там есть генератор случайного простого числа с порядковым номером от 1-го до триллионного,
и главное - там есть HTTPS.
А ещё, там есть поддержка GET-запросов!
Например, миллионное число может быть получено так: https://primes.utm.edu/nthprime/index.php?n=1000000
>The 1,000,000th prime is 15,485,863.
А количество всех простых чисел до миллиарда (пи-функция от миллиарда) - так: https://primes.utm.edu/nthprime/index.php?x=1000000000
>There are 50,847,534 primes less than or equal to 1,000,000,000.
Рандомное простое число - вот так: https://primes.utm.edu/nthprime/index.php?random=true
(тут параметр random, внутри ссылки - просто надо переключить в TRUE)
Я кажется написал самый простой генератор простых чисел.
getPrime(int n) {
prime = http.Get("https://primes.utm.edu/nthprime/index.php?n="+n)
return prime
}
Сейчас роскомпозор пол мира перебанит и что ты тогда делать будешь?
Архивировать интернет и ужимать в комбинации простых чисел, а их потом - на ДНК-флешку.
Парсер прицепил бы туда ещё:
>и ужимать в комбинации простых чисел
А, вот оно что. Пока ты не потратил пол жизни на написание нового архиватора Попова, который винрарно сожмет весь интернет на флешку, поясню, почему информация в принципе несжимаема.
Допустим, у нас есть информация размером N бит и супер функция, которая сжимает ее хотя бы на один бит (гарантированно). Данные у нас хранятся в файлах, а значит всего может существовать 2N различных файлов. Полученные нашей функцией архивы будут иметь размер максимум N-1 бит, а значит может существовать не более 2N-1 архивов. Т.е. распаковать наши архивы в исходные файлы без коллизий не получится - архивов всегда минимум в два раза меньше.
Говоришь так, как будто дерево директрий нельзя записать в txt-файл и ужать этот текстовый файл архиватором.
>Допустим, у нас есть информация размером N бит и супер функция, которая сжимает ее хотя бы на один бит (гарантированно).
Ок.
>Данные у нас хранятся в файлах, а значит всего может существовать 2N различных файлов.
Если по биту на каждый файл писать, то они представляют из себя копии одного и того же файла.
Поэтому при помощи жестких ссылок hardlink - можно минимизировать инфу, сведя её лишь до двух секторов на диске,
и до списка файлов в файловой системе (тот самый txt-шник, о котором я писал выше, с путями и именами файлов).
>Полученные нашей функцией архивы будут иметь размер максимум N-1 бит, а значит может существовать не более 2N-1 архивов.
А нафига ты по одному биту в каждый архив писать собрася?
>Т.е. распаковать наши архивы в исходные файлы без коллизий не получится - архивов всегда минимум в два раза меньше.
Как будто один архив за счёт вычислительных мощностей, при распаковке - не может писать на диск, много архивов.
Кстати, вот здесь: по ссылке
>http://www.codenet.ru/progr/alg/normalize/
внутри, есть код, и ссылка на программу с описанием её:
>http://www.codenet.ru/np-includes/upload/2007/08/21/128152.zip
Программа произодит нормализацию исходного кода файлов.
Я попробовал сделать нормализацию, и вижу в шестнадцатиричном редакторе
шестнадцатиричный шум наподобие крипторандома.
Автор пишет, что нормализация означает, что:
>в получаемом файле соотношение 0 и 1 всегда почти точно 50% на 50%
Так вот, программа эта, нормализованный файл - может денормализовать назад, в прежний вид.
(я нормализовывал ею файл этого же архива). После денормализации - архив снова открывается архиватором.
А это значило бы, что при помощи подобных программ, в процессе денормализации данных,
можно было бы снизить энтропию (то есть почти равномерное распределение нулей и единиц в бинарном коде файла).
Это получается - что-то типа синергетической архивации, основанной на негэнтропии.
Ты нихуя не понял. Файлы не хранят по одному биту и в архивы пишутся не по одному биту. Ты можешь взять любое N, например - 10. Т.е. каждый файл будет хранить 10 бит и всего может существовать 1024 разных файла размером 10 бит, 1025-й уже будет копией одного из предыдущих. Если мы эти 10-тибитные файлы пожмем универсальной суперфункцией до 9 бит, то получим 512 различных архивов. 513-й уже будет копией одного из существующих архивов. А из 512 возможных архивов сделать 1024 исходных файла, очевидно, невозможно.
Все существующие архиваторы занимаются удалением избыточности, т.е. фактически просто переписывают исходное сообщение другим алфавитом, созданным специально для этого сообщения. Попробуй сжать рандомные данные (где нет избыточности) любым существующим архиватором и результат будет больше исходных данных.
>А из 512 возможных архивов сделать 1024 исходных файла, очевидно, невозможно.
Когда разархивируешь какой-нибудь zip ты из одного файла много делаешь же.
>Попробуй сжать рандомные данные (где нет избыточности) любым существующим архиватором и результат будет больше исходных данных.
Так вот я и намекал выше на архивацию с уменьшением энтропии - то есть работающую, на принципах синергетической самоорганизации.
>Так вот я и намекал выше на архивацию с уменьшением энтропии
Двоичная форма - это запись с минимально возможной энтропией. Ее уже невозможно там уменьшить.
>Когда разархивируешь какой-нибудь zip ты из одного файла много делаешь же.
Ты наркоман, чтоле? В последний раз, предельный случай:
У нас есть информация размером 2 бита. Все возможные варианты: 00 01 10 11
У нас есть функция, сжимающая информацию на один бит. Все возможные результаты: 0 1
Мощность множества "архивов" меньше мощности множества "данных". Обратное восстановление невозможно.
>Допустим, у нас есть информация размером N бит и супер функция, которая сжимает ее хотя бы на один бит (гарантированно).
Для меня не очень понятно, как невозможность существования такой функции может быть неочевидна для твоего собеседника.
Я ОП, и я вернулся.
Итак, самым эффективным алгоритмом генерации оказался - тест Миллера-Рабина,
сомещённый с циклом перебора нечётных, имеющих вид 6k±1.
За подсказку - спасибо -анону.
https://gist.github.com/bnlucas/5857478 вот здесь - рабочий исходник на языке Python.
В википедии, псевдокод - нерабочий.
Чтобы всё это работало - нужно поставить пистон и добавить в начало две строки:
import random
from random import randrange
И в конец - можно добавить это:
number = input("Input the number: ");
print(miller_rabin(int(number)))
или это:
#numbers array
input_nums = [
112925255197241067691991,
258288191437393543032381,
1685579612271893009957,
355849543052141644347763,
690189687285399364733225,
168915076940107245134713,
237511420791257209734169,
77275506460653546416341,
459787368207055542960105,
641800620656532268941589,
886673240805426141859665,
605677968519203132991021,
88927130156883467219963,
198992278326083871206563,
];
for num in input_nums:
if miller_rabin(int(num)): newfile.write('%(num)s,\n'%{'num':int(num)}); print(num); print('\n')
Если не работает xrange - можно заменить его на range.
Тест проверяет числа довольно быстро, даже большие.
Нашел где-то 50 простых чисел длиной 2048 бит из 50000 нечётных, порядка 10^616.
Если надо случайное число заданной битности или из диапазона - можно ещё задать или сгенерировать n, и от него уже плясать,
в пределах 70 миллионов.
Двумя битами можно кодировать степень двойки в порождателе инфы,
для дальнейшего перебора всех вариантов от 0 до 2^1.
на вход: 1 бит -> 0, 1
степень двойки: 2^0 = 1 -> в порождателе - все комбинации одного бита: 0, 1
степень дойки: 2^1 = 2 -> в порождателе - все комбинации двух битов 00, 01, 10, 11
И мне почему-то кажется, что при помощи простых чисел,
можно представить любую уникальную комбинацию бит на каком-либо определённом секторе жесткого диска.
Но времени и вычислительных ресурсов, на упаковку уйдёт дофига, потому что - факторизация.
Но если сектор делить на 64-битные числа, а потом факторизовать эти числа, или если весь сектор рассматривать как одно число,
и найти делители его, то запись простых делителей будет если не меньше, то даже больше - битовой строки самого числа.
Поэтому, можно было бы использовать список простых чисел, и сохранять только индексы их.
К тому же, наверняка - есть алгоритмы, способные быстро рассчитать N-ное простое число - по индексу,
а также значение пи-функции от произвольного натурального (то есть индекс ближайшего простого - Meissel–Lehmer algorithm),
ну - чтобы не хранить сами простые числа.
Но я проверил, и вольфрам-альфа, успевая отвечать браузеру по сети - быстрее считает пи-функцию, чем программа
c вот этим алгоритмом: http://docs.sympy.org/latest/modules/ntheory.html#sympy.ntheory.generate.primepi
И хотя алгоритм и подвисает, но это намного быстрее, чем прочёсывать все простые числа по каким-то базам данных и диапазонам.
>можно было бы использовать список простых чисел, и сохранять только индексы их.
Даже не индексы, а смещения индексов. Ведь они возрастают, как и сами числа:
Prime factorization:
5×7×11×29×199×1213×5477×1160608367×316134229883×323004876255732144171530186386683923776150893770761
Простые числа, на которые факторизуется составное число - возрастают существенно, а вот индексы - не очень.
К тому же, с ростом значения диапазона натуральных - количество простых чисел в диапазоне убывает.
Процент простых чисел в натуральных - наглядно видно здесь: , на второй картинке.
Таким образом, если у числа много одинакоых простых делителей можно записать степень, либо индекс простого, и нули за индексом. И эти нули потом, если их много - проще ужать потом ещё и архиватором.
Дальше уже - не индекс, а смещение индекса относительно индекса предыдущего простого.
Тогда, по индукции, архивирование не может быть произведено ни для какой строки.
Так и есть. Арифметический архиватор принципиально невозможен. Это как нарушить закон сохранения.
Но если ОП не верит, пусть попробует. Я когда-то пробовал: и с простыми множителями и с их индексами - в большинстве случаев "сжатый" результат будет больше исходных данных.
Контрпример надо? Будем считать, что возможны только двухбитовые архивы, а кодирующий набор бит может быть каким угодно.
Рассмотрим функцию f такую, что
f(0) = 00, f(1) = 11, f(01) = 01, f(10) = 10.
Тогда ровно половину двухбитовых архивов удастся закодировать одним битом.
Как ты в потоке отличишь [0, 1] от [01]? Нужен еще один бит, чтобы указать, когда там однобитный архив, а когда двухбитный, иначе будет неопределенность.
Этот способ кодирования используется по другому: если первый бит 1, то после него один бит сжатых данных. Если первый бит 0, то если второй бит 1, то после него джва бита сжатых данных. Если первый бит 0, второй бит 0, третий бит 1, то после него 4 бита сжатых данных и т.п.
1[0..1]
01[00..11]
001[0000..1111]
...
Потом составляется частотная таблица для каждого байта исходных данных и наиболее часто встречающимся байтам назначаются наименее длинные коды. Два байта, которые встречаются чаще всего будут иметь размер по два бита каждый. Следующие 4 байта по частоте будут 4 бита в длину. А наименее частые байты будут иметь длину в несколько байт. Если данные не рандомны (т.е. частота всех байт не одинакова), то результирующий архив будет меньше исходных данных.
А разве кто-то что-то говорил про поток?
А надо бы о нем задуматься, ведь данные надо не только сжать, но еще и как-то хранить и расжать потом.
Чё-то я не пойму как разжать, твоими условиями - вот это двоичное число: 01101100000111
Оно было получено так...
Исходное двоичное значение:
1001010011101010100111
по два бита его бью:
10 01 01 00 11 10 10 10 10 01 11
Видно, что наиболее часто встречаемые комбинации бит - это 10 и 01.
Затем - кодирую их 1 битом:
f(0) = 10, f(1) = 01, f(01) = 00, f(10) = 11.
После, пропускаю через функцию этот массив где входное значение - по два бита:
0 1 1 01 10 0 0 0 0 1 11
И получаю: 01101100000111
Теперь, пытаюсь его разжать твоими условиями:
>если первый бит 1, то после него один бит сжатых данных.
>Если первый бит 0, то если второй бит 1, то после него два бита сжатых данных.
>Если первый бит 0, второй бит 0, третий бит 1, то после него 4 бита сжатых данных
Читаю самого начала это число:
Первое условие - false. Первый бит не 1.
Второе условие - true (ну 0 и потом 1, значит - два бита после нуля): 0 1 1
Ок. Дальше...
01 10 - тут срабатывает второе условие, и оно должно бы дать 0 1 1 (что неправильно),
это если от нулевого бита два бита считать, как выше.
Либо же, выше, второе условие должно было бы дать 0 1 10 (если два бита - после единицы, что тоже неправильно).
Ну и дальше уже - всё поехало...
По частотным таблицам - нашёл следующее: https://ru.wikipedia.org/wiki/Код_Хаффмана
На картинке видно наверху, что буква 15 повторений буквы А
(в некоем тексте ААААБВВГВБДДДАААААГБВД) - кодируются одной буквой А,
числом 15, и нулём, а сама буква заносится в таблицу,
а при этом, к ней - кодирует дерево Хаффмана. А сам текст - код Хаффмана.
На картинке видна суммация.
Буква А - повторяется в тексте 15 раз, поэтому, путь к ней, в дереве Хаффмана,
как к наиболее повторяемой букве - записывается нулём.
После этого, составляется таблица, с тремя битами на букву:
Символ: | Код:
А | 0
Б | 100
В | 101
Г | 110
Д | 111
Почему не двумя - не пойму, видимо, потому что букв 5 и число 5 кодируется тремя битами 101.
Видно, что может присутствовать некая контрольная сумма, в виде числа 39, кодирующая всю таблицу.
При этом, 39 = 15 + 7 + 6 + 6 + 5 - частоты всех букв.
И от этого числа, можно отнимать повторения: 39 - 15 = 24.
В общем виде, текст ААААБВВГВБДДДАААААГБВД - кодируется кодом Хаффмана, таблицей с деревом Хаффмана,
а также контрольной суммой, от которой надо отнимать повторения каждой буквы из таблицы.
>Если данные не рандомны (т.е. частота всех байт не одинакова), то результирующий архив будет меньше исходных данных.
Ты говоришь, что данные не должны быть рандомыны, и что там должны быть обязательно повторения.
Но взять вот например какой-нибудь шум, например белый свет. Он разлагается на спектр различных цветов.
Если разложить рандом "по цветам" байтов, можно получить множество секвенций с множеством нулей, и эти нули потом - ужать.
Обратная распаковка - восстановление нулей, сборка секвенций - и сбор их множества в композицию.
>Чё-то я не пойму как разжать, твоими условиями
Потому что сжимаешь своими условиями. А разжать ты их не сможешь, потому что при кодировании создаешь неопределенность.
>f(0) = 10, f(1) = 01, f(01) = 00, f(10) = 11
это compress-only архиватор. Таким алгоритмом потомкам можно википедию сжать, пусть поебутся, чтоб не скучали.
>можно получить множество секвенций с множеством нулей, и эти нули потом - ужать
Если говорить про биты, то ты увеличишь данные в восемь раз. Причем нули там будут непоследовательно (в основном), а поэтому сжать более, чем в восемь раз не получится.
Неопределённость можно было бы использовать при наличии вычислительных мощностей,
например, если есть быстрый квантовый компьютер.
Закодировал одним битом два состояния f(1) = 01, f(01) = 00, прицепил хеш полного файла, и всё.
Мне чё-то кажется, что даже при указании одной лишь длины файла количество коллизий резко уменьшится.
Ишь ты какой? Ты откуда про мои 8 байт узнал? Помнишь небось...
Байты брал отсюда: https://www.random.org/cgi-bin/randbyte?nbytes=10&format=h
10 в калькулятор не поместилось, поместилось поэтому, поместилось лишь
>восемь.
Я пришёл к единичной матрице:
e1 -> 1 0 0 0 0 0 0 0
90 -> 0 1 0 0 0 0 0 0
e7 -> 0 0 1 0 0 0 0 0
81 -> 0 0 0 1 0 0 0 0
c7 -> 0 0 0 0 1 0 0 0
bd -> 0 0 0 0 0 1 0 0
05 -> 0 0 0 0 0 0 1 0
90 -> 1 0 0 0 0 0 0 1
и уже вижу избыточность.
Да, не учёл, ведь байты всё-равно придется писать в таблицы, и будет столько же таблиц, сколько и было байт.
Но можно ещё так попробовать - разложить значение байта в степенной ряд двойки,
и записать смещения позиций у показателей в степенях.
например, байт FF(16) = 255(10) = 11111111(2) = 2^7 + 2^6 + 2^5 + 2^4 + 2^3 + 2^2 + 2^1 + 2^0
показатели степени: 01234567
смещения текущего относительно предыдущего:
11111111 - похоже, что это же число получается...
А теперь смещения, относительно процесса увеличения степени предыдущего - на единицу...
00000000 - нет смещений сверх единицы.
Возьму другое число:
90(16) = 144(10) = 10010000 = 10000000 + 10000 = 2^4 + 2^7.
Беру показатели степени двойки 4 и 7, и считаю отступы текущего от предыдущего.
4 - 0 = 4; 7 - 4 = 3. Пара чисел 4 и 3 может быть записана как 100 и 11 и это - 5 бит.
Но если указать отступ позиции, где есть единица - с учётом процесса увеличения показателя степени на единицу,
то... 0,3,2 = 0 11 10. Первый ноль обязательно писать, ведь 2^0 = 1, и эта единица может либо прибавляться к числу, либо нет.
Развётка байта - в обратном порядке:
0 11 10
0. 2^0 = 1 - единицу не прибавляем. +1 к текущему показателю.
11 = 3. 2^((+1)+3) = 2^4 = 10000 -> x. Прибавляю ещё единицу к показателю.
11 = 3. 2^((4+1)+2) = 2^(5+2) = 2^7 + x -> x = 10010000.
7 степень достигнута - следующий байт.
Вот что нашёл:
https://ru.wikipedia.org/wiki/Сжатие_без_потерь#Метод_сжатия_без_потерь
https://ru.wikipedia.org/wiki/Префиксный_код
Интересно, если поксорить рандом или уже сжатый и несжимаемый код - сам с собой,
можно снизить уменьшить энтропию и потом ещё ужать?
Или можно ли каким-то хитромудрым образом, вот той программой для денормализации файлов -
подобрать такой ключ, который выдаст преобразованный файл - с наименьшим числом единиц?
Бля, забыл что тогда будут сплошные нули.
У меня же есть XOR, вот там на сайте onion, в TOR'e - внутри BrainWallet'а.
Можно посчитать количество единиц в файле или битовой строке,
затем сравнить с половиной длины файла,
и если единиц больше половины длины этого бинарного кода - то сделать инверсию всего кода,
а потом дописать лишь один бит, символизирующий её
и ужать все те нули, образовавшиеся там, где было дофига единиц.
Если сделать так много раз, то я думаю можно было бы уменьшить энтропию
и свести код
01110111110
к какому-то такому
10001000001,
а потом расписав его в степень двойки так:
10000000000 (2^10) +
00001000000 (2^6)+
00000000001 (2^0)=
сохранить только показатели 0, 6, 10 или их смещения относительно друга 0, 6, 4.
Или представить длинное большое число, как сумму двух простых,
согласно бинарной проблеме Гольдбаха, а сами простые числа - сжать как PrimeGrid,
сделав из них чётные, и разделив дофига раз на два, например.
>Наверняка и числа вида 8n-1 можно как-то разложить.
Если p - простое число, и p = x^3 - y^3, где x и y - натуральные числа, то x > y,
и имеем, p = x^3 - y^3 = (x - y)(x^2 + xy + y^2), - тут раскрыта разница кубов.
Так как здесь, второй сомножитель больше первого, то должно быть x - y = 1, и (x^2 + xy + y^2) = p;
откуда, p = x^3 - (x - 1)^3 = 3x^2 - 3x + 1.
Таким образом, простое число p, является разницей кубов двух натуральных чисел,
тогда и только тогда, когда оно имеет вид 3x(x - 1) + 1, (в этом выражении - 3x вынесено за скобку)
где x - натуральное число.
И ещё, из двух последовательных чисел x - 1 и x - одно из них, всегда нечётное.
Следовательно, простое число должно быть вида 6x+1.
Поэтому, для некоторых 6x+1, а именно - для всех, имеющих вид p = 3x(x - 1) + 1;
возможно разложение на разность двух кубов: p = x^3 - y^3
при этом, x - y = 1, и не обязательно записывать y битами, достаточно записать лишь x.
Корень кубический от числа - в три раза короче записи числа.
919 = 18^3 - 17^3; 18-17 = 1;
1110010111(2) = 919(10);
10001(2) = 17(10); и этого числа y - достаточно, чтобы выразить x, + 1 бит.
Можно также, разложить любое большое натуральное число - на сумму восьми кубов,
и записать только корни кубические от кубов этих.
Есть даже алгоритм рассчёта кубических корней в столбик, при достаточно больших числах
(ну, если брать целый сектор например и представлять как одно большое число):
Вот этот алго: https://ru.wikipedia.org/wiki/Кубический_корень#Столбиком
После вычисления корня - нужно также проверить является ли корень кубический - целым числом,
а затем включить алгоритм Миллера-Рабина - и провести тест простоты для корня.
Когда 8 корней записано - указывается считается длина бит большего корня,
и на каждый последующий корень - выделяется столько же бит.
Но 1 корень кубический - ужимает число в три раза,
а 8 корней, записанных в виде бит, подряд - не думаю что дали бы меньшую длину битовой строки...
Например, число:
8945 = 1 + 8 + 27 + 125 + 343 + 1331 + 2197 + 4913 =
1^3 + 2^3 + 3^3 + 5^3 + 7^3 + 11^3 + 13^3 + 17^3.
10001011110001 (2) = 8945(10)
1|1
10|2
11|3
101|5
111|7
1011|11
1101|13
10001|17
и биты корней кубических, вместе взятые - намного больше места занимают, чем биты самого числа.
При наличии быстрого алгоритма для рассчёта прайм пи-функции -
можно было бы использовать вместо чисел - только индексы простых чисел (как минимум 7 из них - простые, ведь)
и кодировать только интервалы между этими индексами, ну потому что корни кубические эти,
в ряду суммы кубов - располагаются по возрастанию.
>можно было бы использовать вместо чисел - только индексы простых чисел
Все равно результат будет занимать больше места, чем само число.
Натуральные числа - это и есть сжатое наилучшим алгоритмом множество произведений простых чисел.
Я так и понял, что в сумму кубов двоичное число не сжать.
>степень двойки
>сохранить только показатели 0, 6, 10 или их смещения относительно друга 0, 6, 4.
Показатели степени ряду суммы степеней двойки - тоже не сжимают.
Наглядно - вот:
Есть строка: 1001001001100011100011001000010011100101000010110010000111010111
с десятичным числом 10548429254638117335, и внутри неё 28 единиц.
В ряд суммы степеней двойки раскладываю всё это:
читаю с конца, и пишу: 1×2^0 + 1×2^1 + 1×2^2 + 0×2^3 + 1×2^4 + ...
Там где бит единица - и множитель для степени 1,
пишу только показатель степени, где множитель 0 - пропускаю,
показатель не пишу.
Получаю массив степеней двойки для единичных бит:
[0, 1, 2, 4, 6, 7, 8, 13, 16, 17, 19, 24, 26, 29, 30, 31, 34, 39, 42, 43, 47, 48, 49, 53, 54, 57, 60, 63]
Так как показатель растёт - то смещения текущего показателя степени относительно предыдущего:
1-0, 2-1, 4-2, и т. д - в массив:
[0, 1, 1, 2, 2, 1, 1, 5, 3, 1, 2, 5, 2, 3, 1, 1, 3, 5, 3, 1, 4, 1, 1, 4, 1, 3, 3, 3]
Дальше, смещения относительно процесса заполнения бит (при заполнении +1).
Все числа снижаются на единицу, появляется много нулей.
[0, 0, 0, 1, 1, 0, 0, 4, 2, 0, 1, 4, 1, 2, 0, 0, 2, 4, 2, 0, 3, 0, 0, 3, 0, 2, 2, 2]
Битовые представления числел в массиах - много места занимает, и проще - битовая строка.
Так, для максимального числа 4 - количество бит, чтобы его выразить равно трем: 100
3*28 единиц = 84 бита, что больше, чем просто - 28 единиц.
И да... В последнем массиве вот что получилось...
В битовой строке: 1001001001100011100011001000010011100101000010110010000111010111
эти числа - не что инное, как количество нулей,
после каждой конкретной единицы, если читать строку - с конца:
1, затем ещё 1 и между ними - ноль нулей. 0
1, затем ещё 1 и между ними - ноль нулей. 0
1, затем ещё 1 и между ними - ноль нулей. 0
1, затем ещё 1 и между ними - один ноль. 1
1, затем ещё 1 и между ними - один ноль. 1
1, затем ещё 1 и между ними - ноль нулей. 0
1, затем ещё 1 и между ними - ноль нулей. 0
седьмая единица с конца - 1, затем ещё 1 и между ними - 4 нуля. 4
0, 0, 1, 1, 0, 0, 4, и так далее.......... Это значения массива.
Можно было бы снизить количество единиц негацией блоков строки, с наибольшим количеством единиц,
дописав бинарный код с количеством бит, равным количеству блоков.
Например 500 байт, половина из них подвергнута негации, и строка из 500 бит дополнительно, к ним,
в которой биты 1 и 0 соответствуют тому, значение ли байта тут или его инверсия.
И когда количество единиц снизится, можно использовать префиксный код, сжимающий нули.
Но я смотрю в другое... Я нашёл алгоритм поиска корня n-ной степени:
https://ru.wikipedia.org/wiki/Алгоритм_нахождения_корня_n-ной_степени
И наверняка, можно было бы, большое число - разложить на корень n-ной степени или сумму этих корней,
указав основания и показатели.
Получилось бы нечто вроде чисел из PrimeGrid MegaPrimes: http://www.primegrid.com/primes/mega_primes.php
Причём чисел, вида: 1806676×41^1806676+1
или 356926^524288+1, в которых достаточно большой показатель.
Но так записываются там только простые числа, и я не вижу какой-либо закономерности в простых числах вида.
x^524288 + 1, или x^n+1 в общем... Поэтому не знаю, даст ли произвольное длинное число, представляющее из себя сектор на диске,
какое-либо разложение на корень n-ной степени, или сумму их,
или произведение его с каким-либо небольшим числом.
>Поэтому не знаю, даст ли произвольное длинное число, представляющее из себя сектор на диске,
>какое-либо разложение на корень n-ной степени, или сумму их,
>или произведение его с каким-либо небольшим числом.
Некоторые, конечно же, дадут. Но по отношению ко всем 256512 числам, которые может представить сектор на диске, их число будет ничтожно мало. Все же остальные будут "сжиматься" таким способом крайне неэффективно (станут намного больше самого исходного числа).
То есть ты намекаешь на длинный остаток.
Как например:
1100001 = 1000000 + 100001 = 2^6 + 100001.
Остаток лишь на 1 бит меньше + основание с показателем - всё это ещё больше бит занимают, чем число.
Ок... Но я говорил - о переборе оснований, чтобы представить число минимальнейшим образом.
Так, например, по ссылке выше, можно видеть степень основания больше двух.
Также, я где-то видел и н-ное простое число, которое можно вычислить локально, через интегральный логарифм...
А вот же: http://docs.sympy.org/latest/_modules/sympy/ntheory/generate.html#prime
Только у меня нифига не работает, я не знаю как подключить, и файл setup.py выдаёт синтаксическую ошибку там.
К тому же PrimePi функция вычисляется долго.
Вот эта PrimePi функция: http://docs.sympy.org/latest/_modules/sympy/ntheory/generate.html#primepi
работает без выебонов, но она долго считает индекс числа, при значении больше 10-ти миллионов.
Если только простые числа, а не все натуральные - можно представить также коротко,
как в PrimeGrid MegaPrimes, через корень n-ной степени,
то по бинарной проблеме Гольдбаха, можно было бы взять целый сектор, в качестве простого числа,
затем, разделить его на два, как огромное большое число,
после этого, включить алгоритм Миллера-Рабина в диапазоне от половины,
до плюс-минус 70 миллионов чисел.
Итан Чжан показал, или даже доказал, что интервал между простыми числами не может быть более 70 миллионов,
если конечно это не тот диапазон с факториалами, речь о котором выше.
Таким образом, в пределах 70-ти миллионов натуральных, от половины значения сектора - можно найти как минимум два простых числа.
Дальше, найденное простое число - отнимается от сектора, и результат тоже проверяется на простоту алгоритмом Миллера-Рабина.
Если результат - число не составное, сектор предствляется суммой простых чисел.
А вот уже простые числа - наверняка можно ужать в корень N-ной степени, причём какими бы большими они не были.
Или же, представить их - через праймориал.
>Итан Чжан показал, или даже доказал, что интервал между простыми числами не может быть более 70 миллионов,
Нет. Он доказал, что есть бесконечное число пар простых чисел, между которыми не более 70 млн составных. Это просто приближение к доказательству вроде пока недоказанной гипотезы, что существует бесконечное число простых-близнецов.
В принципе же, разрыв между парой простых чисел может быть абсолютно любой.
>То есть ты намекаешь на длинный остаток
Нет. Я намекаю на то, что натуральный ряд - это уже архив. Там энтропия минимально возможная и сжать его даже на бит не получится. Лишь некоторую ничтожно малую часть этих чисел можно переписать более компактно. Оставшиеся же, перебьют всю сэкономленную память и сверху еще навалят на порядки больше, чем занимало само число.
Во всём ряду, может и да, но отдельные числа можно ещё больше сжать.
Так, например, натуральное число 18446744073709551614, имеющее бинарный вид:
1111111111111111111111111111111111111111111111111111111111111110
может быть выражено всего двумя битами: 1 и ещё 1 бит,
символизирующий инверсию оставшихся 63-х бит. Хочу подчеркнуть, что число натуральное.
И таких чисел в ряду - натуральных - много, на каждое из них - можно выделить и по биту,
если сжимать нули - многократными прогонами префиксного кодирования.
Ну, между простыми числами-близнецами может быть ещё дофига простых чисел разных видов.
Я даже проверил - зациклив с рандомного числа алгоритм Миллера-Рабина для каждого конкретного нечётного.
И вот что получилось...
Простые числа длиной 1024 бита:
130341454124268511361589671683820282331561282068405574945037046867157404705885569876181968046817776443073022840838404286132626397576976602718965722741926326403746054664615428828902895650047026429699744843338645411810009738677202895562377441140885715679334820178662070173385328005700679135241947932745462464673
130341454124268511361589671683820282331561282068405574945037046867157404705885569876181968046817776443073022840838404286132626397576976602718965722741926326403746054664615428828902895650047026429699744843338645411810009738677202895562377441140885715679334820178662070173385328005700679135241947932745462464889
130341454124268511361589671683820282331561282068405574945037046867157404705885569876181968046817776443073022840838404286132626397576976602718965722741926326403746054664615428828902895650047026429699744843338645411810009738677202895562377441140885715679334820178662070173385328005700679135241947932745462465607
130341454124268511361589671683820282331561282068405574945037046867157404705885569876181968046817776443073022840838404286132626397576976602718965722741926326403746054664615428828902895650047026429699744843338645411810009738677202895562377441140885715679334820178662070173385328005700679135241947932745462465877
130341454124268511361589671683820282331561282068405574945037046867157404705885569876181968046817776443073022840838404286132626397576976602718965722741926326403746054664615428828902895650047026429699744843338645411810009738677202895562377441140885715679334820178662070173385328005700679135241947932745462465897
130341454124268511361589671683820282331561282068405574945037046867157404705885569876181968046817776443073022840838404286132626397576976602718965722741926326403746054664615428828902895650047026429699744843338645411810009738677202895562377441140885715679334820178662070173385328005700679135241947932745462466147
130341454124268511361589671683820282331561282068405574945037046867157404705885569876181968046817776443073022840838404286132626397576976602718965722741926326403746054664615428828902895650047026429699744843338645411810009738677202895562377441140885715679334820178662070173385328005700679135241947932745462466269
130341454124268511361589671683820282331561282068405574945037046867157404705885569876181968046817776443073022840838404286132626397576976602718965722741926326403746054664615428828902895650047026429699744843338645411810009738677202895562377441140885715679334820178662070173385328005700679135241947932745462466317
130341454124268511361589671683820282331561282068405574945037046867157404705885569876181968046817776443073022840838404286132626397576976602718965722741926326403746054664615428828902895650047026429699744843338645411810009738677202895562377441140885715679334820178662070173385328005700679135241947932745462466869
130341454124268511361589671683820282331561282068405574945037046867157404705885569876181968046817776443073022840838404286132626397576976602718965722741926326403746054664615428828902895650047026429699744843338645411810009738677202895562377441140885715679334820178662070173385328005700679135241947932745462467241
Простые числа длиной 2048 бит:
21894522688173756518387509995253958704268650919380741160068056991226576652537628754644264895435856354147612343217117209366305017382894505733026140913413882817495851973374969623377139375449641938210847324176820868735983294429307271769970891706180198116465335419602471925379728494564736572313661243905640883039531280416030435734976123313673612001126259164031919936749302013472219124881546261385713221731806830502862030086331885023727955202834481010696866904774814380192780846179486511261293778786507647997805206107563484930117826257855349238784801300846796108163038193745394400472632071926087475316262676417598331659257
21894522688173756518387509995253958704268650919380741160068056991226576652537628754644264895435856354147612343217117209366305017382894505733026140913413882817495851973374969623377139375449641938210847324176820868735983294429307271769970891706180198116465335419602471925379728494564736572313661243905640883039531280416030435734976123313673612001126259164031919936749302013472219124881546261385713221731806830502862030086331885023727955202834481010696866904774814380192780846179486511261293778786507647997805206107563484930117826257855349238784801300846796108163038193745394400472632071926087475316262676417598331660187
21894522688173756518387509995253958704268650919380741160068056991226576652537628754644264895435856354147612343217117209366305017382894505733026140913413882817495851973374969623377139375449641938210847324176820868735983294429307271769970891706180198116465335419602471925379728494564736572313661243905640883039531280416030435734976123313673612001126259164031919936749302013472219124881546261385713221731806830502862030086331885023727955202834481010696866904774814380192780846179486511261293778786507647997805206107563484930117826257855349238784801300846796108163038193745394400472632071926087475316262676417598331661021
21894522688173756518387509995253958704268650919380741160068056991226576652537628754644264895435856354147612343217117209366305017382894505733026140913413882817495851973374969623377139375449641938210847324176820868735983294429307271769970891706180198116465335419602471925379728494564736572313661243905640883039531280416030435734976123313673612001126259164031919936749302013472219124881546261385713221731806830502862030086331885023727955202834481010696866904774814380192780846179486511261293778786507647997805206107563484930117826257855349238784801300846796108163038193745394400472632071926087475316262676417598331667759
21894522688173756518387509995253958704268650919380741160068056991226576652537628754644264895435856354147612343217117209366305017382894505733026140913413882817495851973374969623377139375449641938210847324176820868735983294429307271769970891706180198116465335419602471925379728494564736572313661243905640883039531280416030435734976123313673612001126259164031919936749302013472219124881546261385713221731806830502862030086331885023727955202834481010696866904774814380192780846179486511261293778786507647997805206107563484930117826257855349238784801300846796108163038193745394400472632071926087475316262676417598331667767
21894522688173756518387509995253958704268650919380741160068056991226576652537628754644264895435856354147612343217117209366305017382894505733026140913413882817495851973374969623377139375449641938210847324176820868735983294429307271769970891706180198116465335419602471925379728494564736572313661243905640883039531280416030435734976123313673612001126259164031919936749302013472219124881546261385713221731806830502862030086331885023727955202834481010696866904774814380192780846179486511261293778786507647997805206107563484930117826257855349238784801300846796108163038193745394400472632071926087475316262676417598331671851
21894522688173756518387509995253958704268650919380741160068056991226576652537628754644264895435856354147612343217117209366305017382894505733026140913413882817495851973374969623377139375449641938210847324176820868735983294429307271769970891706180198116465335419602471925379728494564736572313661243905640883039531280416030435734976123313673612001126259164031919936749302013472219124881546261385713221731806830502862030086331885023727955202834481010696866904774814380192780846179486511261293778786507647997805206107563484930117826257855349238784801300846796108163038193745394400472632071926087475316262676417598331676729
21894522688173756518387509995253958704268650919380741160068056991226576652537628754644264895435856354147612343217117209366305017382894505733026140913413882817495851973374969623377139375449641938210847324176820868735983294429307271769970891706180198116465335419602471925379728494564736572313661243905640883039531280416030435734976123313673612001126259164031919936749302013472219124881546261385713221731806830502862030086331885023727955202834481010696866904774814380192780846179486511261293778786507647997805206107563484930117826257855349238784801300846796108163038193745394400472632071926087475316262676417598331677107
21894522688173756518387509995253958704268650919380741160068056991226576652537628754644264895435856354147612343217117209366305017382894505733026140913413882817495851973374969623377139375449641938210847324176820868735983294429307271769970891706180198116465335419602471925379728494564736572313661243905640883039531280416030435734976123313673612001126259164031919936749302013472219124881546261385713221731806830502862030086331885023727955202834481010696866904774814380192780846179486511261293778786507647997805206107563484930117826257855349238784801300846796108163038193745394400472632071926087475316262676417598331677737
21894522688173756518387509995253958704268650919380741160068056991226576652537628754644264895435856354147612343217117209366305017382894505733026140913413882817495851973374969623377139375449641938210847324176820868735983294429307271769970891706180198116465335419602471925379728494564736572313661243905640883039531280416030435734976123313673612001126259164031919936749302013472219124881546261385713221731806830502862030086331885023727955202834481010696866904774814380192780846179486511261293778786507647997805206107563484930117826257855349238784801300846796108163038193745394400472632071926087475316262676417598331679297
Простые числа длиной 4096 bit:
652847511922665051218342821505509360505472799862368633568780170538745984238166668012067318042425171493000391274259624160197650107291873808506689216240034938220221245930032199305948006645670800375358054981521364280623712444472308613777461406892411532021075448168109786072434294667042228646992211867788877495766692398047074302715717236431331194949079884375541133608089357670962195053633600079171675977808957516254418592651994078835346903333766010277887798264226256202944980219028678779858060203957762810913529347040540456105103604408908176444791718619284345489704506301110329022983689819824140988354988806218558891581812927042301282247588981375127638378966037895465948710323067785582924083374083196300144749326784485671226533936478706537934575380366710296906390842785413493838256752655933754149302160673331910960394041675049651633757853497099855509954720284269917359840926699780511948083290338559068928397359556520037318719291214305469977224683963954017831362210405053639986770514860371072137296085841335739070812637304503372574919575902068948992715756760971657107883394344324872799345511368099734406525430574930207642218154379802891909069947879122390885777274022704627660795382619271213806627167783627218483308419889081617252238409601
652847511922665051218342821505509360505472799862368633568780170538745984238166668012067318042425171493000391274259624160197650107291873808506689216240034938220221245930032199305948006645670800375358054981521364280623712444472308613777461406892411532021075448168109786072434294667042228646992211867788877495766692398047074302715717236431331194949079884375541133608089357670962195053633600079171675977808957516254418592651994078835346903333766010277887798264226256202944980219028678779858060203957762810913529347040540456105103604408908176444791718619284345489704506301110329022983689819824140988354988806218558891581812927042301282247588981375127638378966037895465948710323067785582924083374083196300144749326784485671226533936478706537934575380366710296906390842785413493838256752655933754149302160673331910960394041675049651633757853497099855509954720284269917359840926699780511948083290338559068928397359556520037318719291214305469977224683963954017831362210405053639986770514860371072137296085841335739070812637304503372574919575902068948992715756760971657107883394344324872799345511368099734406525430574930207642218154379802891909069947879122390885777274022704627660795382619271213806627167783627218483308419889081617252238411059
652847511922665051218342821505509360505472799862368633568780170538745984238166668012067318042425171493000391274259624160197650107291873808506689216240034938220221245930032199305948006645670800375358054981521364280623712444472308613777461406892411532021075448168109786072434294667042228646992211867788877495766692398047074302715717236431331194949079884375541133608089357670962195053633600079171675977808957516254418592651994078835346903333766010277887798264226256202944980219028678779858060203957762810913529347040540456105103604408908176444791718619284345489704506301110329022983689819824140988354988806218558891581812927042301282247588981375127638378966037895465948710323067785582924083374083196300144749326784485671226533936478706537934575380366710296906390842785413493838256752655933754149302160673331910960394041675049651633757853497099855509954720284269917359840926699780511948083290338559068928397359556520037318719291214305469977224683963954017831362210405053639986770514860371072137296085841335739070812637304503372574919575902068948992715756760971657107883394344324872799345511368099734406525430574930207642218154379802891909069947879122390885777274022704627660795382619271213806627167783627218483308419889081617252238411173
652847511922665051218342821505509360505472799862368633568780170538745984238166668012067318042425171493000391274259624160197650107291873808506689216240034938220221245930032199305948006645670800375358054981521364280623712444472308613777461406892411532021075448168109786072434294667042228646992211867788877495766692398047074302715717236431331194949079884375541133608089357670962195053633600079171675977808957516254418592651994078835346903333766010277887798264226256202944980219028678779858060203957762810913529347040540456105103604408908176444791718619284345489704506301110329022983689819824140988354988806218558891581812927042301282247588981375127638378966037895465948710323067785582924083374083196300144749326784485671226533936478706537934575380366710296906390842785413493838256752655933754149302160673331910960394041675049651633757853497099855509954720284269917359840926699780511948083290338559068928397359556520037318719291214305469977224683963954017831362210405053639986770514860371072137296085841335739070812637304503372574919575902068948992715756760971657107883394344324872799345511368099734406525430574930207642218154379802891909069947879122390885777274022704627660795382619271213806627167783627218483308419889081617252238412387
652847511922665051218342821505509360505472799862368633568780170538745984238166668012067318042425171493000391274259624160197650107291873808506689216240034938220221245930032199305948006645670800375358054981521364280623712444472308613777461406892411532021075448168109786072434294667042228646992211867788877495766692398047074302715717236431331194949079884375541133608089357670962195053633600079171675977808957516254418592651994078835346903333766010277887798264226256202944980219028678779858060203957762810913529347040540456105103604408908176444791718619284345489704506301110329022983689819824140988354988806218558891581812927042301282247588981375127638378966037895465948710323067785582924083374083196300144749326784485671226533936478706537934575380366710296906390842785413493838256752655933754149302160673331910960394041675049651633757853497099855509954720284269917359840926699780511948083290338559068928397359556520037318719291214305469977224683963954017831362210405053639986770514860371072137296085841335739070812637304503372574919575902068948992715756760971657107883394344324872799345511368099734406525430574930207642218154379802891909069947879122390885777274022704627660795382619271213806627167783627218483308419889081617252238415627
652847511922665051218342821505509360505472799862368633568780170538745984238166668012067318042425171493000391274259624160197650107291873808506689216240034938220221245930032199305948006645670800375358054981521364280623712444472308613777461406892411532021075448168109786072434294667042228646992211867788877495766692398047074302715717236431331194949079884375541133608089357670962195053633600079171675977808957516254418592651994078835346903333766010277887798264226256202944980219028678779858060203957762810913529347040540456105103604408908176444791718619284345489704506301110329022983689819824140988354988806218558891581812927042301282247588981375127638378966037895465948710323067785582924083374083196300144749326784485671226533936478706537934575380366710296906390842785413493838256752655933754149302160673331910960394041675049651633757853497099855509954720284269917359840926699780511948083290338559068928397359556520037318719291214305469977224683963954017831362210405053639986770514860371072137296085841335739070812637304503372574919575902068948992715756760971657107883394344324872799345511368099734406525430574930207642218154379802891909069947879122390885777274022704627660795382619271213806627167783627218483308419889081617252238419081
652847511922665051218342821505509360505472799862368633568780170538745984238166668012067318042425171493000391274259624160197650107291873808506689216240034938220221245930032199305948006645670800375358054981521364280623712444472308613777461406892411532021075448168109786072434294667042228646992211867788877495766692398047074302715717236431331194949079884375541133608089357670962195053633600079171675977808957516254418592651994078835346903333766010277887798264226256202944980219028678779858060203957762810913529347040540456105103604408908176444791718619284345489704506301110329022983689819824140988354988806218558891581812927042301282247588981375127638378966037895465948710323067785582924083374083196300144749326784485671226533936478706537934575380366710296906390842785413493838256752655933754149302160673331910960394041675049651633757853497099855509954720284269917359840926699780511948083290338559068928397359556520037318719291214305469977224683963954017831362210405053639986770514860371072137296085841335739070812637304503372574919575902068948992715756760971657107883394344324872799345511368099734406525430574930207642218154379802891909069947879122390885777274022704627660795382619271213806627167783627218483308419889081617252238421567
652847511922665051218342821505509360505472799862368633568780170538745984238166668012067318042425171493000391274259624160197650107291873808506689216240034938220221245930032199305948006645670800375358054981521364280623712444472308613777461406892411532021075448168109786072434294667042228646992211867788877495766692398047074302715717236431331194949079884375541133608089357670962195053633600079171675977808957516254418592651994078835346903333766010277887798264226256202944980219028678779858060203957762810913529347040540456105103604408908176444791718619284345489704506301110329022983689819824140988354988806218558891581812927042301282247588981375127638378966037895465948710323067785582924083374083196300144749326784485671226533936478706537934575380366710296906390842785413493838256752655933754149302160673331910960394041675049651633757853497099855509954720284269917359840926699780511948083290338559068928397359556520037318719291214305469977224683963954017831362210405053639986770514860371072137296085841335739070812637304503372574919575902068948992715756760971657107883394344324872799345511368099734406525430574930207642218154379802891909069947879122390885777274022704627660795382619271213806627167783627218483308419889081617252238422191
652847511922665051218342821505509360505472799862368633568780170538745984238166668012067318042425171493000391274259624160197650107291873808506689216240034938220221245930032199305948006645670800375358054981521364280623712444472308613777461406892411532021075448168109786072434294667042228646992211867788877495766692398047074302715717236431331194949079884375541133608089357670962195053633600079171675977808957516254418592651994078835346903333766010277887798264226256202944980219028678779858060203957762810913529347040540456105103604408908176444791718619284345489704506301110329022983689819824140988354988806218558891581812927042301282247588981375127638378966037895465948710323067785582924083374083196300144749326784485671226533936478706537934575380366710296906390842785413493838256752655933754149302160673331910960394041675049651633757853497099855509954720284269917359840926699780511948083290338559068928397359556520037318719291214305469977224683963954017831362210405053639986770514860371072137296085841335739070812637304503372574919575902068948992715756760971657107883394344324872799345511368099734406525430574930207642218154379802891909069947879122390885777274022704627660795382619271213806627167783627218483308419889081617252238422857
652847511922665051218342821505509360505472799862368633568780170538745984238166668012067318042425171493000391274259624160197650107291873808506689216240034938220221245930032199305948006645670800375358054981521364280623712444472308613777461406892411532021075448168109786072434294667042228646992211867788877495766692398047074302715717236431331194949079884375541133608089357670962195053633600079171675977808957516254418592651994078835346903333766010277887798264226256202944980219028678779858060203957762810913529347040540456105103604408908176444791718619284345489704506301110329022983689819824140988354988806218558891581812927042301282247588981375127638378966037895465948710323067785582924083374083196300144749326784485671226533936478706537934575380366710296906390842785413493838256752655933754149302160673331910960394041675049651633757853497099855509954720284269917359840926699780511948083290338559068928397359556520037318719291214305469977224683963954017831362210405053639986770514860371072137296085841335739070812637304503372574919575902068948992715756760971657107883394344324872799345511368099734406525430574930207642218154379802891909069947879122390885777274022704627660795382619271213806627167783627218483308419889081617252238423281
Как видишь, отличаются они - лишь десятками тысяч. В википедии, в статье про сектор диска - я вижу следующее:
Новые жесткие диски используют размер сектора 4096 байт (4 Кбайт), известный как расширенный формат (Advanced Format),
и эти числа - как раз длиною в сектор.
Да и вообще, судя по функции распределения простых чисел - она зависит от логарифма, причём натурального, и судя по этой таблице
https://ru.wikipedia.org/wiki/Функция_распределения_простых_чисел#Таблицы_для_пи-функции,_x_/_ln_x_и_li(x)
процент простых чисел далеко-далеко - приближается к 1% и там зависает около того.
Есть же график логарифмической функции, и PrimePI-функция подобна ей.
И ещё вопрос оставлю тут:
Аноны, кто-нибудь знает - как выдрать с исходного кода, отсюда ,
по ссылкам внутри там - все фрагменты, да так их закомментировать - чтобы в одном py-файле,
работали эти функции: prime(nth), li(x), Li(x) - ну, сдвинутый интегральный логарифм.
Или есть ли алгоритм рассчета интегрального логарифма у кого?
У меня модули не ставятся и не импортируется нифига - выбивает всякие ерроры...
Хотел найти N-ное простое число - и вижу там, отдельным массивом они объявляются эти простые числа:
>_list = _array('l', [2, 3, 5, 7, 11, 13, 17, 19, 23])
и после последнего простого числа (тут оно 9-е, у меня) -
начинаются траблы с этими функциями li(), log(), Li(), и прочее...
Был бы у меня алгоритм рассчёта интегрального логарифма - я попытался бы найти число Скьюза,
потому что пи-функция у меня работает локально. Но не вольфрам же дрочить по вебу каждый раз:
https://www.wolframalpha.com/input/?i=LogIntegral%5B2%5D
хотя там довольно точно рассчитывается этот интегральный логарифм.
Поставил Anaconda (python со вшитым sympy), без всяких багов - попёрли цифры...
Интегральный логарифм с точностью до 1000 знаков:
>>> li(2).evalf(1000)
1.045163780117492784844588889194613136522615578151201575832909144075013205210359
53017271740562638335630602082976887474662228523978521965027902108233455784540551
59053003222632748284543905148534966228633054761993303044191709434064183547149667
28596717017227338273714300125193836755515319447162976529780078148971487790319821
88519147113706991634634546145669268395700985294401943733041485320549175590426740
34376055257631453647013996141578816205226945882167913779577985755793070640280590
88488920257316919757992888222796598747399061809849093348573555554633208717494295
44429144879540630078900509249372759973792879832401077413460701742686305761355494
51725696332316233096424132629787724067443606625192514864611488915201308403944647
50402167878403958119211513737654364343272889716990374103843991215975681213659120
87965726714423273237468687426861913799539868695073624705150351784646192104683318
74813866025467134576495035178662403288015619622921383812609964490733284014730018
44780347826133407814725434678125931835111
Я принёс пи-функцию из 2015-го года:
pi(10^27) = 16,352,460,426,841,680,446,427,399
http://www.mersenneforum.org/showthread.php?t=20473
Значений больше - не вижу.
МОжно засунуть эти числа в исходник, чтоб быстрее дальше считать?
А то не очень хочется перебирать по-новой - столька многа цифар.
Для длинной последовательности простых чисел, можно записать их в виде разницы между текущим простым числом и предыдущим.
Разницу - записать не цифрами а байтами, и на каждое простое число, выражаемое в виде разницы - выделить
определённое число байт. По-сути, эта разница кодирует количество составных натуральных до очередного простого.
Для получения энного числа, нужно просуммировать все разницы до энного, и прибавить результат к первому простому,
записанному в виде числа.
Видно, что второе 4096-битное число отличается от первого, также, как отличается
411059 от 409601. 411059 - 409601 = 1458 = 10110110010(2) = 00000101 10110010 - и это два байта.
Таким образом, на запись каждого 4096-битного числа может уйти лишь два байта,
вместо записи всех цифр каждого числа.
2^4096 = 10^x; x = 1233, то есть 1233 байта/2 байта - сжатие в 616,5 раз.
К тому же, в длинном файле с последовательными простыми числами - многие числа могут повторяться,
что позволит ещё больше сжать файл - при помощи кода Хаффмана.
>К тому же, в длинном файле с последовательными простыми числами - многие числа могут повторяться,
многие разницы между ними, хотел сказать.
Там, кстати, есть функция Якобсталля для рассчета интервалов между простыми числами.
И всё-же - хреновая идея. Первые 10 миллионов простых чисел занимают 90,1 МБ (94 484 450 байт)
если записывать их по 10 чисел через табуляцию со сбросом строки, причём цифрами и в виде ASCII-текста.
Если же выделять по одному байту на запись только интервалов, получается 9,53 МБ (10 000 001 байт).
И это даже лучшее сжатие, чем ужал первый файл архиватор 7z - он ужал его в 11,9 МБ (12 536 200 байт).
Более того, сам текстовый файл с этими однобайтовыми интервалами - тоже можно ужать при помощи 7z,
причём до размера 5,18 МБ (5 436 330 байт). Казалось бы, чё бы не использовать однобайтовые интервалы, но...
У такой последовательности, от каждого бита - зависит целостность всего файла.
Один бит если где-то повреждён, или один бед-сектор если появится - то всё придётся перегенерировать снова.
Последовательности, где пишутся все цифры - можно перегенерировать, частично
включая алгоритм Миллера-Рабина диапазонами...
Так как для поиска N-ного простого числа по файлу, нужно суммировать последовательно однобайтовые интервалы,
процессор от этого греется немало.
Но можно конечно засунуть туда через каждые 1000 байт сумму предыдущих 1000,
и через каждый миллион - сумму миллиона предыдущих, чтоб ускорить рассчёт.
Тогда, можно будет прикрутить и корректирующие коды какие-нибудь, по контрольной сумме,
или восстанавливать целые блоки по этим суммам, если где-то повреждён хоть один бит.
Запхнул алгоритм Миллера-Рабина - в Javascript BigInteger, вот сюда:
https://github.com/username1565/BigInteger/commit/5bfea9f1f2db6dbd2933558dd26ab59e91a2921a
Теперь, можно в браузере, через эту HTML-страницу
https://github.com/username1565/BigInteger/blob/master/Miller-Rabin_test.html,
проверять на простоту - пиздатые числа и генерировать простые из них.
Для этого надо скачать BigInteger.js и эту страницу, закинуть их в одну папку, и открыть в браузере html-страницу.
В исходном коде - страницы можно также прописать любое число, числа, и цикл для проверки списка чисел.
Что вы тут, скучаете?
А я вам - немного факторизации, покушать принёс:
Я переписал ρ-метод факторизации Джона Полларда (с оптимизацией от Ричарда Брента).
Реализация на JavaScript, адаптированная к BigInteger.js в которой доступны три вариации алгоритма.
Факторизовать числа можно тут:
https://username1565.github.io/BigInteger.js/Pollard_rho_factorization/
Сам исходник с BigInteger'ом - тут:
https://github.com/username1565/BigInteger.js/tree/master/Pollard_rho_factorization
Вариант с Brent-оптимизацией - намного быстрее двух предыдущих вариантов, раскладывает тестовое число:
539665377349940636086669695451569769025523026168820293846695597848211
на простые множители:
123457 × 1234577 × 12345701 × 123456791 × 1234567907 × 12345678923 × 123456789133 × 1234567891253
А перебор их занял бы ещё больше времени.
Исходя из этого поста: https://stackoverflow.com/questions/2267146/what-is-the-fastest-factorization-algorithm
ρ-метод - ищет простые множители, длина которых не больше 2^70.
Для более длинных чисел - доступны и другие алгоритмы:
>Less than 2^16 or so: Lookup table.
>Less than 2^70 or so: Richard Brent's modification of Pollard's rho algorithm.
>Less than 10^50: Lenstra elliptic curve factorization
>Less than 10^100: Quadratic Sieve
>More than 10^100: General Number Field Sieve
а также 100%-й метод Ферма, исходник которого - здесь: http://e-maxx.ru/algo/factorization
Этот метод очень быстро ищет простые делители длинного числа,
но если оно является составным, и состоит из двух рядом лежащих простых чисел.
Например, простые числа p и q для генерации числа n по алгоритму RSA.
Я вам тут Javascript-Primality-Tester с генератором подвёз. Может кому надо будет...
На клиентской стороне, он без сервера, в браузере - работает с большими числами, при помощи BigInt.js
Используется алгоритм Миллера-Рабина с 50-ю раундами.
Демонстрация - тут: https://username1565.github.io/Javascript-Primality-Tester/
Исходник - тут: https://github.com/username1565/Javascript-Primality-Tester
Засунул туда генератор.
Теперь можно генерировать списки последовательных простых чисел - произвольной длины,
начиная с произвольного большого простого числа.
Сам я считаю простые числа кодом на python, там тоже Miller-Rabin но с 10-ю раундами.
Ошибок не вижу, ориентируясь по сайту https://primes.utm.edu/nthprime/
Рассчёт хоть и на одном ядре (ибо я не смог в векторизацию и параллелизм на GPU), но зато быстрее чем в браузере, и сразу пишет в файл.
Скоро закончу генерацию списков простых чисел среди 2-х триллионов натуральных...
Первый триллион - находится вот тут: http://www.primos.mat.br/
Последовательные простые числа, более триллиона, через TOR - тут: https://42k5tcpg7bhjjaze.onion/primes_over_1T/
Фу, погромист. Бвэээ
Это чё за блевотина?!! Аж самому тошнит. А ну-ка веник и савок в руки, и прибирай за собой.
Только веником по совку бливотину не размажь, лучше тряпкой размажь.
>Скоро закончу генерацию списков простых чисел среди 2-х триллионов натуральных...
>Последовательные простые числа, более триллиона, через TOR - тут: https://42k5tcpg7bhjjaze.onion/primes_over_1T/
Второй триллион натуральных чисел рассчитан!
Все последовательные простые числа от 1T до 2T - доступны там теперь.
От 37607912019-го (1,000,000,000,039)
до 73301896139-го простого числа (1,999,999,999,981)
было проверено 35,693,984,120 простых чисел. Ошибок не обнаружено.
Все эти простые числа - запакованы в 3570 7z-архивов по 10 миллионов простых чисел в каждом.
Суммарный объем данных этой части, в сжатом виде - составляет 44,7 ГБ (48 070 309 289 байт).
Считал с апреля месяца на одном ядре, процессором.
Сейчас проверяю и пакую числа в диапазоне 2T-3T. Если у кого есть списки простых чисел из этого диапазона, можете залить.
Я склею, прогоню и добавлю. Там есть папка FOLDER FOR UPLOADS.
Если кто будет заливать, просьба учесть формат.
1. Внутри каждого 7z архива - текстовый файл. Один текстовый файл - миллион строк.
2. По 10 простых чисел в каждой строке. Разделитель между числами - символ табуляции. 9 табуляций.
3. После последнего числа табуляции нет, вместо этого - сброс строки '\r\n' (CRLF)
4. Значение прайм-пи функции от 2Trillions - составляет PrimePi(2T) = 73301896139 - ровно столько простых чисел до двух триллионов.
Первое простое число после 2-х триллионов, число 2,000,000,000,003 уже 73301896140-е: https://primes.utm.edu/nthprime/index.php?n=73301896140
10 миллионов чисел в каждой части, если включить первое, то +9,999,999 чисел.
Таким образом, архивы долны иметь следующие оффсеты:
________________________________________________________________________________________
part | first_prime_index | last_prime_index | first prime - last prime |
1 | 73301896140 | 73311896139 | 2,000,000,000,003 - 2,000,283,236,933 |
2 | 73311896140 | 73321896139 | 2,000,283,236,977 - 2,000,566,532,281 |
3 | 73321896140 | 73331896139 | 2,000,566,532,351 - 2,000,849,735,189 |
4 | 73331896140 | 73341896139 | 2,000,849,735,197 - 2,001,133,018,613 |
5 | 73341896140 | 73351896139 | 2,001,133,018,631 - 2,001,416,240,129 |
6 | (last_prime_index_part_5) +1 = 73351896140 | (first_prime_index_part_6)+9,999,999 = 73361896139 | https://primes.utm.edu/nthprime/index.php?n=73351896140 - https://primes.utm.edu/nthprime/index.php?n=73361896139
N | (last_prime_index_N-1)+1 | (first_prime_index_N) | и на сайте видно - числа по индексам.
И так далее...
По ссылкам, вы можете получить N-ное простое число, по его индексу, и значение прайм-пи функции
в пределах первых 30-ти триллионов натуральных чисел, и триллиона простых.
Но списки последовательных простых чисел вы там не качнёте.
Поэтому, можно рассчитать first_prime_index для любой части, получить простое число по индексу, и начать с него перебор.
Задача рассчета хорошо параллелится таким образом, и можете заливать туда да хоть разные части.
Нахуя это нужно? В стронгкрипто используются числа порядка 100300, так что твой первый триллион простых чисел никакой роли там не сыграет.
10300, то есть.
Там за простое число из двух миллионов цифр дают миллион долларов, вот анон и готовится.
Алсо, было бы неплохо на основании этих чисел вывести какую никакую формулу для нахождения простых чисел. Это я так толсто набросил
>Там за простое число из двух миллионов цифр дают миллион долларов
Попахивает пиздежом. И не такие уже находили.
https://www.youtube.com/watch?v=tlpYjrbujG0
>Нахуя это нужно?
Чтоб по торрентам раздавать и 4 месяца не брутить их, как поц, очевидно же.
>В стронгкрипто используются числа порядка 100^300
>10^300, то есть.
Вот здесь можно сгенерировать такие: https://username1565.github.io/Javascript-Primality-Tester/
Только надо подождать, а то долго генерируется...
Я сделал это так:
1. >var x = '1'; for(i=1;i<300;i++){x = x+'0';} console.log(x, x.length);
2. start number - это число, numbers - 1. Получил число на 669 больше этого, и оно простое.
>так что твой первый триллион простых чисел никакой роли там не сыграет.
Там два триллиона. Ты сночало добейсо.
Ещё, с последовательными простыми числами, можно быстро развернуть
пёздатейшую скатерть Улама, и вдруг она окажется скатертью-самобранкой?
А ещё, простых чисел всего около 1% в природе, среди натуральных.
Они диффицитные, и ими можно торговать.
И тут - рассчёт простых чисел приравнивается к майнингу, лол.
Я уже представляю себе биржи простых чисел, и блокчейн на них.
>Попахивает пиздежом.
Да так и есть, походу...
>Там за простое число из двух миллионов цифр дают миллион долларов, вот анон и готовится.
Где там? Смотри какие тут значения в столбце Digits: http://primegrid.com/primes/mega_primes.php
>вот анон и готовится
Да никуда я не готовлюсь, просто у меня появилось чё-то такая "ПРОСТАЯ ОДЕРЖИМОСТЬ".
Процессор 45 ватт всего тянет, в нагрузке, это не так много, вот и решил сюда его флопсы присунуть.
Нигде в сети не вижу 2 триллиона, кроме как на сайте https://primes.utm.edu/nthprime/index.php
но там нет архивов. Так-то я мог бы и 4 терабайта простыми числами себе забить.
>Алсо, было бы неплохо на основании этих чисел вывести какую никакую
>формулу для нахождения простых чисел.
>Это я так толсто набросил
А действительно, прикинь по двум триллионам - находишь формулу, опережаешь primeGrid, получаешь премию.
Но, ИМХО, лучшая формула - это быстрейший алгоритм теста простоты:
https://ru.wikipedia.org/wiki/Тест_простоты#Истинные_тесты_простоты
Однако куда быстрее можно найти число по смещению, оффсету,
нежели проверять перебором все нечётные, не делящиеся на 5, а уж тем более - все натуральные.
Есть ещё алгоритм поиска энного простого числа по интегральному логарифму:
но он долго работает при значениях овер триллион.
Я думаю, что список последовательных простых чисел может помочь отметить опорные точки,
или создать массивы для ускорения работы программ, оперирующих простыми числами.
>можно найти число по смещению, оффсету
Ну и какой там у простых чисел оффсет? Как обычно, четыре пробела?
Во-первых, я не затачивал списки под быстрый поиск N-ного простого числа -
это скорее продолжение списоков с сайта http://primos.mat.br/
Во-вторых, это было не четыре пробела, а символ табуляции \t он же - байт 0x09.
Можно его инкрементировать вместе с байтами сброса строки [0x0d, 0x0a],
чтобы найти n-ное простое число.
Но проще заранее рассчитать крайние значения prime pi-функции для каждого файла,
(и можно сделать это быстро, кстати, ибо в файлах по 10 млн чисел),
а потом искать N-ное простое число - в конкретном выбранном файле,
в пределах входного значения искомого N.
В-третьих, можно было бы и выделить по определённому числу байт на каждое простое,
и пропускать их пачкам при поиске, например - секторами, но придётся перепаковывать всё,
и я не особо хочу заниматься этим (даже планировать), ведь там овер 3к архивов и я уже хеши их обсчитал.
Если есть конкретные предложения для более удобной организации всего этого - пишите, рассмотрим.
Или качайте и запиливайте у себя уже сами...
Поначалу, я думал сжать все эти числа, используя: https://ru.wikipedia.org/wiki/Интервалы_между_простыми_числами
Но тогда, при поиске N-ного простого, все эти интервалы пришлось бы суммировать, от начала до конца файла...
В этом случае, если целостность файла нарушена хоть на один бит (появился битый сектор, например), то вся конструкция станет не рабочей.
Поэтому, было решено оставить числа даже не в виде байт, а именно в виде ASCII-текста, то есть в виде читабельных списков,
как изначально и было в файлах на сайте http://primos.mat.br Ну и 7z достаточно хорошо их жмёт.
Аноны, я тут при помощи Garlic.exe (v0.0.5.3) сгенерировал новый onion-домен: http://primesznxlfc5ika.onion
А ещё нашёл альтернативу сервису Tor2Web, на сайтах https://onion.pet/ и https://onion.top/
Теперь, простые числа доступны из Интернета, без TOR-браузера - тут: http://primesznxlfc5ika.onion.pet/primes/
Сам же Garlic, если кому надо - я повесил тут: https://primesznxlfc5ika.onion.top/Other_files/Vanity_onion_domain/Garlicv0.0.5.3(CPU_calculations)/
Сам я его еле нашёл в сети...
Сейчас, с помощью garlic я рассчитываю другое доменное имя с префиксом primenums. В течении недели программа должна рассчитать.
Заебало, короче, считать онион домен - garlic на одном ядре целый месяц собрался рассчитывать... Кулер свистит и пердит.
Зато нашёл быстрый генератор последовательных простых чисел.
Чтобы получить списки как на как на http://primos.mat.br/
1. Надо скачать PARI/GP (Pari64-2-11-0.exe) https://pari.math.u-bordeaux.fr/download.html
2. Установить его.
3. Запустить gp.exe с правами администратора.
4. Переключить раскладку на Еnglish (EN)
5. Вставить туда - это (одна строка!):
>folder="C:\\Pari64-2-11-0\\data";blockname="2T-3T";part=424;n=0;s="";forprime(p=2119935706183,3000000000000,n++;s=Str(s,p,if(n % 10 != 0,"\t","\n"));if(n % 10^3 == 0, write1(Str(folder,"\\",blockname,"_part",part,".txt"),s);s="");if(n%10000000==0, part++));
В этой строке нужно указать два параметра - номер части (part) и первое простое число в ней (p).
Первое простое число может быть рассчитано просто, потому что PrimePi(2T) = 73,301,896,139, и +10 миллионов простых чисел в каждой части.
Поэтому (73,301,896,139+1) + (424-1)×10,000,000 = 73,301,896,140 + 4,230,000,000 = 77531896140 - и это число N для первого простого в части 424.
Затем, может быть доступно и само простое число, как N-ное простое здесь: https://primes.utm.edu/nthprime/index.php?n=77531896140
и оно имеет значение 2,119,935,706,183 (2119935706183).
Это простое число, как результат, может быть использовано как параметр p и так для любой произвольной части.
В результате, может быть сгененрировано множество частей в различном порядке,
и эта работа может быть распараллелена с использованием множества компьютеров процессоров и ядер,
а также с последующим сравнением хешей всех этих частей.
Каждая часть на выходе - содержит 10 миллионов простых чисел - 10 в одной строке через разделитель '\t' (0x09),
и миллион строк в каждой части, через разделитель '\n' (0x0d, 0x0a).
Для быстрой упаковки множества txt-частей -> в архив, с помощью 7z, может быть использован bat-файл, с кодом:
>for X in ("full_patheway_for_folder_with_txt_parts\*.txt") do "full_pathway_to_7z_folder\7z.exe" a "~nX.7z" "%%X"
В этом случае будет создано много 7z-архивов, рядом с txt-частями.
Pari/GP даёт мне на выхооде части с одинаковыми SHA512 и контрольная сумма СRC-32 внутри 7z файла тоже совпадает.
но PARI/GP генерирует части быстрее моего алгоритма. Но это не GPU программа - она использует процессор.
Там где начинается и кончается спойлер - по два знака процента должно быть, в строке. Никогда не спойлерил процентами...
Аноны, смотрите какое число нашёл!
Вольфрам говорит что между в этом диапазоне лишь два простых числа:
http://www.wolframalpha.com/input/?i=primes%5B2999999999933,3000000000013%5D
primes.utm.edu - тоже:
https://primes.utm.edu/nthprime/index.php?n=108340298703
https://primes.utm.edu/nthprime/index.php?n=108340298704
Но между числами 2999999999933 и 3000000000013 есть ещё одно простое: 2999999983949
Это число видит PariGP и WolframAlpha - одобряет:
http://www.wolframalpha.com/input/?i=2999999983949
>2999999983949 is a prime number.
Факторизовать его нельзя: https://username1565.github.io/BigInteger.js/Pollard_rho_factorization/pollard_rho.html
На этом числе - стопорятся алгоритмы, они дают сдвиг.
Что в этом числе такого особенного? Как выдоить с него - зиллиард баксов?
>2999999999933
>2999999983949
>между числами 2999999999933 и 3000000000013 есть ещё одно
Завязывал бы ты с простыми, от них кукухой можно двинуться.
-кун
Оо, внатуре! Перегенерировал - и всё норм.
С третьего - по четвёртый триллион теперь считаю,
пока мы в параллель тут, из клопа - циклопа на сишке пилим:
Охуенно быстро генерирует.
Знакомьтесь Сlang - Consecutive Lists Of Primes: ttps://github.com/username1565/cyclop
>Сlang - Consecutive Lists Of Prime
Почему не CLOP?
Я иконку с клопом не нашёл, и звучит как-то мерзко...
Я тут, у себя, диалог для ввода параметров написал, кстати.
>Я иконку с клопом не нашёл
Ну хочь - форкни, откомпиль, да сам повешай клопа своего. Я там батник сунул и описание компиляции.
У меня же - циклопом прога будет зваться. Он таким няшный на windows 8.1 в больших значках смотрится...
Нашёл тут, картинку получше, с бОльшим разрешением: http://www.medical-enc.ru/10/images/klop.jpg
Твоя, я вижу - была повёрнута. Я тоже повернул. Пик1.
Смущает белый фон. Дело поправимое. Заменил на прозрачный.
Сначала сходил сюда: https://www.imgonline.com.ua/replace-white-background-with-transparent.php
Подобрал интенсивность замены, периодически добавляя к body в исходном коде страницы с картинкой bgcolor="000000".
Получил - пик2.
Дальше - иду сюда: https://username1565.github.io/MultiCoin-paperwallet/index_files/static/avatars/docs/
Делаю аватар 256x256 - пик2. Аватар этот - с прозрачным фоном. Пик3.
Сую его в https://convertico.com/ - получаю multi-icon ico-файл - пик4.
Проверяю Multi-icon ли? Иду сюда: https://redketchup.io/icon/edit -> Open ICO File -> Загружаю...
Вижу 6 иконок ico... И главное - все они с прозрачным фоном!
>получаю multi-icon ico-файл - пик4.
.ico - тип файла не поддерживается. Можете влить туда третью пикчу - получите эту же ico.
>И главное - все они с прозрачным фоном!
Это годно, когда на рабочем столе заставка и когда перетаскиваешь файл.
Есть число 420599303587838138310567954368696889132078473300110593927087135329323325211067643992189
Надо разложить на простые множители
Известно:
1)Их два
2)Число вида (2p-1)(2q-1) где p и q простые
Число так же равно 8576682859183712660439494656457(2^185) + 60149540478113987615*(2^92) + 29235325
Мне кажется я близок хэлп
Надо разложить на простые множители
Известно:
1)Их два
2)Число вида (2p-1)(2q-1) где p и q простые
Число так же равно 8576682859183712660439494656457(2^185) + 60149540478113987615*(2^92) + 29235325
Мне кажется я близок хэлп
Я уж думал анон с тараканами себе пикчи нашел, а это два пикчи двухлетние.
А смешно таки они так вывалились
Есть ли какие-либо алгоритмы, или формулы позволяющие генерировать
гарантированно простое число - заданной битности?
Первое, что приходит в голову, так это использовать арифметические прогрессии в PrimeGrid:
http://www.primegrid.com/stats_ap26.php
И хотя числа простые, и их не надо проверять - там нельзя выбрать битность.
На картинке - визуализация решета Эрастофена.