М.Двач / Математика

43 Кб, 554x445
Простые числа. Алгоритм генерации. 31 мар 2018, 17:00 38039 В конец треда | Веб

Приветствую, матанон.
Есть ли какие-либо алгоритмы, или формулы позволяющие генерировать
гарантированно простое число - заданной битности?
Первое, что приходит в голову, так это использовать арифметические прогрессии в PrimeGrid:
http://www.primegrid.com/stats_ap26.php
И хотя числа простые, и их не надо проверять - там нельзя выбрать битность.

На картинке - визуализация решета Эрастофена.

Ответы38042380433804638058383673843538578386483878639916420244258043158

2 31 мар 2018, 19:32 2 38042

>>38039 (OP)
Нашёл формулу p = 6k ± 1, но она иногда даёт простое, в одном из случаев (плюс или минус),
а иногда - простые числа-близнецы. Поэтому надо проверять числа на простоту.

3 31 мар 2018, 20:57 3 38043

>>38039 (OP)
>Есть ли какие-либо алгоритмы, или формулы позволяющие генерировать
>гарантированно простое число - заданной битности?
Нет и не может быть.

Ответы38045

4 31 мар 2018, 23:55 4 38045

>>38043
Всякое простое число, большее 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, содержащих простые числа-близнецы - может быть какой-то закон,
зависящий от пи, по формуле Эйлера, или от логарифма какого-нибудь, например от логарифма квадрата пи.
Есть же формула Валлиса.

4 31 мар 2018, 23:55 4 38045

>>38043
где k — некоторое натуральное число.

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

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, содержащих простые числа-близнецы - может быть какой-то закон,
зависящий от пи, по формуле Эйлера, или от логарифма какого-нибудь, например от логарифма квадрата пи.
Есть же формула Валлиса.

Показать весь текст
Ответы3804738050

138 Кб, 1220x480
5 1 апр 2018, 00:23 5 38046

>>38039 (OP)

Ответы38053

6 1 апр 2018, 00:36 6 38047

>>38045
Диапазон [n!+2 .. n!+n] не содержит ни одного простого числа, т.к. все их можно представить в виде x(n!/x+1). Если n устремляем к бесконечности, получается, что существует бесконечно большой непрерывный диапазон составных чисел. А значит, или перед ним находится последнее простое число (что доказано, что не так) или функция распределения должна перескочить через бесконечность к следующему простому числу, что невозможно.

Ответы3808038434

7 1 апр 2018, 05:08 7 38050

>>38045
не понял, к чему кусок про p = 6k ± 1.
существуют k, для которых и 6k+1 и 6k-1 составные.

Ответы38052

8 1 апр 2018, 09:17 8 38052

>>38050
Дело в том, что
каждое число может быть записано в виде 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

8 1 апр 2018, 09:17 8 38052

>>38050
Дело в том, что
каждое число может быть записано в виде 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

Показать весь текст
Ответы38435

9 1 апр 2018, 09:45 9 38053

>>38046
Что это за формула такая большая?
Что означают буквы там и как их подставлять, чтоб получить простое число?
Насколько я понял, там, в этом множестве - целая система уравнений, так?

Первая формула Эйлера, интересная.
Быстро реализовал перебор 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 - простое.
...

9 1 апр 2018, 09:45 9 38053

>>38046
Что это за формула такая большая?
Что означают буквы там и как их подставлять, чтоб получить простое число?
Насколько я понял, там, в этом множестве - целая система уравнений, так?

Первая формула Эйлера, интересная.
Быстро реализовал перебор 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 - простое.
...

Показать весь текст
Ответы3805438062

10 1 апр 2018, 10:09 10 38054

>>38053
>Первая формула Эйлера, интересная.
>n^2 - n + 41
Можно поставить знак плюс, перед n, и тоже много простых чисел выдаст. n^2 + n + 41
Дискриминант выражения n^2+n+41 равен "−163": http://www.wolframalpha.com/input/?i=n^2+n+41
(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^2+6+55661
и оно делится на 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.

Ответы38055

11 1 апр 2018, 12:11 11 38055

>>38054
Ещё нашёл такие полиномы тут:
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
Так и не понял толком что она значит, но возможно некоторые числа из неё можно использовать в полиномах,
чтоб получить формулу для какого-нибудь длинного диапазона простых чисел.

12 1 апр 2018, 13:22 12 38058

>>38039 (OP)
Тут кто-то в этом разделе как-то писал, что
если перемножить все простые числа
и прибавить единицу получится простое число.

Так вот, это не так. Например:
23# = 1·2·3·5·7·11·13·17·19·23 = 223092870 + 1 = 223092871 - не простое. Его факторизация: (317 × 703763)

Ответы38059

13 1 апр 2018, 13:44 13 38059

>>38058
>Тут кто-то в этом разделе как-то писал, что
если перемножить все простые числа
и прибавить единицу получится простое число.
Это работает, только если простых чисел конечное число.

Ответы38061

14 1 апр 2018, 14:32 14 38061

>>38059
>Это работает, только если простых чисел конечное число.
То есть, ты хочешь сказать,
что делители 317 и 703763, на которые делится число 223092871
не принадлежат какому-то множеству, и поэтому число можно считать простым?

Например, после числа 23, следующее простое число 29, число перед ним - 28,
и множество содержащее конечное количество простых чисел 1·2·3·5·7·11·13·17·19·23 -
имеет вид вот такой {0-28}, и ни 317 ни 703763 - не входят в это множество.
Поэтому число 223092871 не разделится ни на одно из чисел от 1 до 28,
являясь при этом простым для этого множества. Всё верно?
Если да, то это так вообще?
То есть дейстительно ли наименьшее из чисел, на которые факторизуется большое число - обязательно вылазит за множество?
И можно ли так генерировать псевдопростые числа заданной битности?

Ответы3806438077

15 1 апр 2018, 15:07 15 38062

>>38053
>Что это за формула такая большая?
>Что означают буквы там и как их подставлять, чтоб получить простое число?
Целые неотрицательные числа подставляй вместо букв.

Ответы38066

16 1 апр 2018, 15:43 16 38064

>>38061
Ты пишешь странно, мне тяжело читать.
Суть в том, что если множество P простых чисел конечно,
то их p=(произведение+1) должно делится на какое-то число из P,
но оно не делится ни на одно из них. Значит либо p простое,
либо делится на какое-то простое число, не лежащее в P.
Но P, по условию, содержит все простые числа. Противоречие.
Поэтому простых чисел бесконечное количество.

Ответы3806538066

17 1 апр 2018, 15:48 17 38065

>>38064
В общем я неверно первый ответ написал.
Но суть в том, что тот анон просто не прав,
неправильно понял доказательство, или специально запутал.

18 1 апр 2018, 16:36 18 38066

>>38062
При если генерировать эти числа от 1 до 10 - то получается
какое-то большое отрицательное число: https://jsfiddle.net/98o1p5mt
Исходник - открыт там. Можешь нажать кнопку Run и проверить. В консоли браузера - тоже выводится это число.
Можешь проверить код и подправить, если что.

>>38064
Ну так я и спросил действительно ли оно не делится?

Ответы380703807638077

5 Кб, 466x16
19 1 апр 2018, 19:36 19 38070

>>38066

Ответы38076

20 2 апр 2018, 12:44 20 38076

>>38066
Написал туда (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) будет большим числом, поэтому - результат отрицателен.

>>38070
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);

20 2 апр 2018, 12:44 20 38076

>>38066
Написал туда (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) будет большим числом, поэтому - результат отрицателен.

>>38070
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);

Показать весь текст
Ответы3808138082

93 Кб, 463x640
21 2 апр 2018, 12:57 21 38077

>>38061
Если число делится на одно из натуральных, в котором лежат числа множества простых,
то это число разделится и на простые числа.
>>38066
>Ну так я и спросил действительно ли оно не делится?
Пикрелейтед. Страница 57, книга "Простая одержимость. Бернхард Риман и величайшая нерешенная проблема в математике", автор Джон Дербишир.

22 2 апр 2018, 15:57 22 38080

>>38047
>что невозможно.
Почему?

Ответы38459

23 2 апр 2018, 16:49 23 38081

>>38076
Не знаю, я дал тебе направление, ищи сам, я не подставлял туда числа.

24 2 апр 2018, 17:10 24 38082

>>38076
>>38076
>Но тогда, при x = 0, (k+2)·(1-0) = 1·(k+2), и при k = 6, (k+2) = 8 - и это не простое число.
У тебя при k=6 скобка нулём становится?

Ответы38083

25 2 апр 2018, 18:50 25 38083

>>38082
Нет, я же оставил цитату, и выделил жирным.
Там в википедии написано, что когда каждый из квадратов (и каждый многочлен в квадратных скобках),
равен нулю, то полином Джонса принимает положительные значения.
Я занулил всё в квадратных скобках, чтобы показать, что например при 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 помощь, хоть это радует.

Ответы3809138119

26 3 апр 2018, 00:12 26 38091

>>38083
>Там в википедии написано, что когда каждый из квадратов (и каждый многочлен в квадратных скобках),
>равен нулю, то полином Джонса принимает положительные значения.
Равен нулю каждый из квадратов или нет зависит от k. Наверняка при k = 6 скобки нулю не равны.

Ответы38097

124 Кб, 620x420
27 3 апр 2018, 02:21 27 38097

>>38091
Вот другой вид полинома, на картинке.
k стоит не в каждой квадратной скобке.
После выражений в квадратных скобках происходит возведение этих выражений в квадрат.
Если все квадратные скобки равны нулю, как написано в википедии,
и если это является условием для положительного значения этого полинома,
то скобка (1-0) = 1, и после перемножения (k+2) на эту единицу - остаётся лишь (k+2).
При любом k кратном двум, результат полинома будет делиться на два - и это не простое число.

Ответы3809838099

28 3 апр 2018, 02:45 28 38098

>>38097
>Если все квадратные скобки равны нулю
То равны нулю и квадратные скобки с k. Не еби мозг, k нельзя взять с головы здесь.

Ответы38099

29 3 апр 2018, 02:49 29 38099

>>38098
>>38097
Уже в 4 формуле сверху при k=6 и при том, что переменные не могут быть отрицательными 0 не получится.

30 4 апр 2018, 14:56 30 38119

>>38083
>Сейчас я последовательно перебираю ссылки вида http://www.primegrid.com/ap.php?userid=N
>где N - номер пользователя. И извлекаю прогрессии.
Там, на PrimeGrid.com около миллиона пользователей, вот номер последнего из них: 999980
Я открываю по 50 окон при помощи JS через window.open и закрываю их по одному - у тех, у кого нет прогрессий.
Затем копирую прогрессии в текстовый файл, и засовываю его в скрипт - после этого, получаю массив прогрессий.
Настолько нудное занятие закрывать эти окна. Может есть где нормальные парсеры, чтоб слить все прогрессии с сайта?
Когда будет полный список, может быть даже там найдутся - прогрессии из прогрессий.

Ответы38121

31 4 апр 2018, 15:33 31 38121

>>38119
>парсеры
BeautifulSoup+lxml

Ответы38619

32 10 апр 2018, 15:58 32 38367

>>38039 (OP)
Просто отвечу здесь вот этому древнему анону, может будет проходить мимо: 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/Теорема_о_распределении_простых_чисел
И сложность их добычи - занимала бы весь хешрейт сети.

32 10 апр 2018, 15:58 32 38367

>>38039 (OP)
Просто отвечу здесь вот этому древнему анону, может будет проходить мимо: 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/Теорема_о_распределении_простых_чисел
И сложность их добычи - занимала бы весь хешрейт сети.

Показать весь текст
Ответы38368

33 10 апр 2018, 16:02 33 38368

>>38367
Ещё сюда добавлю ответ вот на это:
>Если кто не понял что я хочу, математические проблемы которые пока не имеют способов решения кроме как тупым перебором.
>Чтобы суть задачи вроде простая как два пальца обоссать асфальтом, типа последовательности простых чисел 2-3-5-7-11-13-17-19-23-29-31, а найти >например 867 простое число, кроме как тупо перебирать все числа с калькулятором, невозможно было.
В вольфраме для этого есть специальная опция. Например - миллиардное простое число. https://www.wolframalpha.com/input/?i=1,000,000,000th+prime

34 13 апр 2018, 20:04 34 38434

>>38047
>все их можно представить в виде x(n!/x+1)
У тебя две переменные там.
Откуда ты это взял?
Представь мне число 999999999989 в через факториал.
Я знаю, что есть https://ru.wikipedia.org/wiki/Факториальное_простое_число
но это отдельный тип чисел. Среди них нет 11 и 13 - а это числа близнецы.
К тому же, В 2013 году Итан Чжан отправил в журнал Annals of Mathematics статью,
в которой доказывалось что существует бесконечно много пар последовательных простых чисел
с разностью не более 70 миллионов.

Ответы38458

35 13 апр 2018, 20:21 35 38435

>>38039 (OP)
Слил вот этот сайт себе http://primos.mat.br/ - тут 50 гигов последовательных простых чисел.
Перевёл его на русский - и повесил вот сюда: https://42k5tcpg7bhjjaze.onion/primes/
В TOR-Browser быстрее открывается, но если из WEB'а ломиться, то можно зайти вот так:
http://vobhod.org/browse.php?u=http://42k5tcpg7bhjjaze.onion/primes
или так: https://42k5tcpg7bhjjaze.onion.to/primes/

Затем, после того, как слил сайт - написал прогу на питоне для проверки чисел по списку,
делением их - на все простые, до корня из числа. Она есть там на страницах why.
Удобно юзать списки, очень быстро проверяется числа.
Сейчас от нехуй делать - бручу у себя, питоном, второй триллион среди всех нечётных чисел,
p = 6k ± 1 исключив другие из этих: >>38052
условие для цикла: if (i%6==3) or (i%6==2) or (i%5==0): continue;
Количество чисел - проверяю в вольфраме, запросом prime[начальное_простое, конечное]

Ответы3843938599

36 13 апр 2018, 21:17 36 38439

>>38435
А их можно как-то ещё сильнее ужать - особенно те, что в конце?
Ну - чтоб не расписывать их полностью...
Файл 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 и один бит рядом, соответствующий либо сложению либо вычитанию единицы...

Ответы3845338468

10 Кб, 491x129
37 14 апр 2018, 11:54 37 38453

>>38439
Может это поможет: 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)

Ответы3846838681

38 14 апр 2018, 16:54 38 38458

>>38434
>У тебя две переменные там.
>Откуда ты это взял?
Все числа этого диапазона имеют вид n! + x, где x = 2..n. А n! + x это x(n!/x+1). Два множителя - число составное.

Ответы38468

39 14 апр 2018, 16:56 39 38459

>>38080
Потому что бесконечность бесконечна.

Ответы38468

40 15 апр 2018, 11:51 40 38468

>>38439
Они там - по цифрам пишутся, текстом, через разделитель.
Можно минусовать триллион от каждого, и записать этот триллион - в начале файла.
Можно ещё, ужать текст - в сами числа, тогда выйдет не более 6 байт на каждое число, и разделитель тогда не нужен будет.
Но думаю, лучше, наверное, оставить в виде текста (так понятнее что за файл) и использовать архиватор.
А ещё, думал разложить числа в степени двойки и записать сами степени.
То есть сами адреса бит, или последовательность их смещений относительно номера предыдущего адреса с единичным битом.
Но если так жать файл, там будет неведомый HEX внутри, читаемый только программой, и его можно удалить ненароком.
На данный момент, я нашёл около миллиона чисел, свыше триллиона.

>>38453
На квадраты - долго раскладываются каждое из чисел. Уже проверил двумя циклами.
К тому же тройка чисел a, b, c - больше бит занимают вместе, чем само число.

>>38458
>существует бесконечно большой непрерывный диапазон составных чисел
Я-то думал эти диапазоны можно исключить в коде, чтоб ускорить проверку чисел на простоту.

Ну ты там это... Поставь вместо n, хотя-бы 20, и ты увидишь насколько это "бесконечно большой диапазон" -
с разницей лишь в 18 натуральных чисел. :)

>>38459
Хаххахх. А факториал от бесконечности считать научишь-то?

Кстати, вот тут https://alexlotov.livejournal.com/540579.html
можно видеть, что диапазон [(70млн. + 1)! + 2, (70 млн. + 1)+(70 млн. + 1)] - таки не содержит ни одного простого числа.

Ответы3858238586

41 19 апр 2018, 13:17 41 38578

>>38039 (OP)
А тебе прям _гарантированно_ нужно или сойдет вероятность 0.999999 (столько девяток сколько сам захочешь)?

Ответы38581

134 Кб, 300x300
42 19 апр 2018, 14:20 42 38581

>>38578
Именно вот - гарантированно простое, и именно заданной битности.

Вот, смотри - есть например, алгоритм 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) - трудно.
А в случае единицы в частном, можно получить и само число (оно равно делитель + остаток).

134 Кб, 300x300
42 19 апр 2018, 14:20 42 38581

>>38578
Именно вот - гарантированно простое, и именно заданной битности.

Вот, смотри - есть например, алгоритм 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) - трудно.
А в случае единицы в частном, можно получить и само число (оно равно делитель + остаток).

Показать весь текст

43 19 апр 2018, 14:25 43 38582

>>38468
>Ну ты там это... Поставь вместо n, хотя-бы 20, и ты увидишь насколько это "бесконечно большой диапазон"
Ну ты подумай, что будет быстрее для очень больших чисел, проверка на простоту или проверка на то, является ли это число числом вида n!+x, x<n+1 (по сути можно просто занести их в массив до определенного n).

Ответы38589

44 19 апр 2018, 14:41 44 38586

>>38468
Можно хранить простые, например, как пару (n,k), где 30n+k твое число.

Ответы38589

45 19 апр 2018, 16:32 45 38589

226 Кб, 628x38911 Кб, 415x468

>>38582
Да, при длинных числах, хоть этот диапазон чисел и незначителен, но нагрузка на проверку числел - падает, если пропустить этот диапазон,
ведь для проверки надо делить на все простые до корня от числа, и проще проверить большие числа - сразу уже так.

>>38586
>Можно хранить простые, например, как пару (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[0,210]
Таким образом, простые числа могли бы быть выражены как 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[1000000000000,+1000276307647]
можно просто минусовать один триллион, и писать сам остаток - в виде бит.
Вот так 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.

45 19 апр 2018, 16:32 45 38589

226 Кб, 628x38911 Кб, 415x468

>>38582
Да, при длинных числах, хоть этот диапазон чисел и незначителен, но нагрузка на проверку числел - падает, если пропустить этот диапазон,
ведь для проверки надо делить на все простые до корня от числа, и проще проверить большие числа - сразу уже так.

>>38586
>Можно хранить простые, например, как пару (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[0,210]
Таким образом, простые числа могли бы быть выражены как 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[1000000000000,+1000276307647]
можно просто минусовать один триллион, и писать сам остаток - в виде бит.
Вот так 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.

Показать весь текст
Ответы385913862238649

46 19 апр 2018, 17:18 46 38591

>>38589
>то как видно, пара чисел n, k - занимает больше бит, чем двоичный вид самого числа.
если хранить в двоичном формате, то неясно, что служит разделителем чисел. И опять же ты хранить в txt, так что xn + p может быть эффективнее

Ответы38592

47 19 апр 2018, 18:17 47 38592

>>38591
>если хранить в двоичном формате, то неясно, что служит разделителем чисел.
Можно выделить на каждое число в конкретном диапазоне - по x байт, тогда и разделитель не нужен.
Например, в диапазоне https://www.wolframalpha.com/input/?i=prime[1000000000000,+1000276307647]
первое простое число 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 байт, вместо пяти на каждое число, а это уже - избыточно, и писать само число.

47 19 апр 2018, 18:17 47 38592

>>38591
>если хранить в двоичном формате, то неясно, что служит разделителем чисел.
Можно выделить на каждое число в конкретном диапазоне - по x байт, тогда и разделитель не нужен.
Например, в диапазоне https://www.wolframalpha.com/input/?i=prime[1000000000000,+1000276307647]
первое простое число 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 байт, вместо пяти на каждое число, а это уже - избыточно, и писать само число.

Показать весь текст
Ответы3859338598

48 19 апр 2018, 18:19 48 38593

>>38592
>и писать само число.
и проще - писать само число.

49 19 апр 2018, 19:26 49 38598

>>38592
Информация в принципе несжимаема. Если есть число N, то для его хранения необходимо минимум ceil(log2(N)) бит и именно столько число N занимает в двоичном виде. Любые другие формы записи этого числа потребуют больше бит для его хранения.

Ответы38600

50 19 апр 2018, 19:28 50 38599

>>38435
Сделал там в TOR'е - отдельную папку FOLDER_FOR_UPLOADS, куда можно загружать всякие файлы на сервер.
У кого есть списки простых чисел или какие-то программы для параллельного поиска их видеокартами - можете залить.
Ну и алсо, всякую хуйню можете ещё позаливать, типа котиков-наркотиков, лол.

51 19 апр 2018, 19:35 51 38600

>>38598
http://www.primegrid.com/primes/mega_primes.php с тобой несогласны.
Их записи занимают намного меньше бит.

Ответы38602

52 19 апр 2018, 19:44 52 38602

>>38600
Это частные случаи. Универсального способа записать любое число так, чтобы оно занимало меньше бит, чем в двоичном виде - не существует.
Так-то можно и список всех простых чисел на серверах гугла составить, а у себя хранить только их индексы. Первые 264 простых чисел будут всего по 8 байт.

Ответы38607

53 19 апр 2018, 20:27 53 38607

>>38602
>Так-то можно и список всех простых чисел на серверах гугла составить, а у себя хранить только их индексы.
>Первые 264 простых чисел будут всего по 8 байт.
Вольфрам Альфа, по всей видимости, так и делает.
В запросе http://www.wolframalpha.com/input/?i=prime[1000082617987,1000082617987]
можно видеть одно простое число 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.
вот это оно и есть.

Я также вижу что у них там и про алгоритм что-то написано, но ничего не понял.

Ответы38608

54 19 апр 2018, 20:37 54 38608

>>38607
>Я также вижу что у них там и про алгоритм что-то написано, но ничего не понял.
Зато там есть пи-функция от 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.

Ответы38609

55 19 апр 2018, 20:51 55 38609

>>38608
А ещё, там есть поддержка 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)

Ответы38613

56 19 апр 2018, 22:15 56 38613

>>38609
Я кажется написал самый простой генератор простых чисел.

getPrime(int n) {
prime = http.Get("https://primes.utm.edu/nthprime/index.php?n="+n)
return prime
}

Ответы3861438619

57 19 апр 2018, 22:22 57 38614

>>38613
Сейчас роскомпозор пол мира перебанит и что ты тогда делать будешь?

Ответы38618

58 19 апр 2018, 23:46 58 38618

>>38614
Архивировать интернет и ужимать в комбинации простых чисел, а их потом - на ДНК-флешку.

Ответы38621

59 19 апр 2018, 23:47 59 38619

>>38613 Парсер прицепил бы туда ещё: >>38121

60 20 апр 2018, 00:43 60 38621

>>38618
>и ужимать в комбинации простых чисел
А, вот оно что. Пока ты не потратил пол жизни на написание нового архиватора Попова, который винрарно сожмет весь интернет на флешку, поясню, почему информация в принципе несжимаема.
Допустим, у нас есть информация размером N бит и супер функция, которая сжимает ее хотя бы на один бит (гарантированно). Данные у нас хранятся в файлах, а значит всего может существовать 2N различных файлов. Полученные нашей функцией архивы будут иметь размер максимум N-1 бит, а значит может существовать не более 2N-1 архивов. Т.е. распаковать наши архивы в исходные файлы без коллизий не получится - архивов всегда минимум в два раза меньше.

Ответы3862238633

5 Кб, 174x273
61 20 апр 2018, 02:07 61 38622

>>38621
Говоришь так, как будто дерево директрий нельзя записать в txt-файл и ужать этот текстовый файл архиватором.
>Допустим, у нас есть информация размером N бит и супер функция, которая сжимает ее хотя бы на один бит (гарантированно).
Ок.
>Данные у нас хранятся в файлах, а значит всего может существовать 2N различных файлов.
Если по биту на каждый файл писать, то они представляют из себя копии одного и того же файла.
Поэтому при помощи жестких ссылок hardlink - можно минимизировать инфу, сведя её лишь до двух секторов на диске,
и до списка файлов в файловой системе (тот самый txt-шник, о котором я писал выше, с путями и именами файлов).
>Полученные нашей функцией архивы будут иметь размер максимум N-1 бит, а значит может существовать не более 2N-1 архивов.
А нафига ты по одному биту в каждый архив писать собрася?
>Т.е. распаковать наши архивы в исходные файлы без коллизий не получится - архивов всегда минимум в два раза меньше.
Как будто один архив за счёт вычислительных мощностей, при распаковке - не может писать на диск, много архивов.

Кстати, вот здесь: >>38589 по ссылке
>http://www.codenet.ru/progr/alg/normalize/
внутри, есть код, и ссылка на программу с описанием её:
>http://www.codenet.ru/np-includes/upload/2007/08/21/128152.zip
Программа произодит нормализацию исходного кода файлов.
Я попробовал сделать нормализацию, и вижу в шестнадцатиричном редакторе
шестнадцатиричный шум наподобие крипторандома.
Автор пишет, что нормализация означает, что:
>в получаемом файле соотношение 0 и 1 всегда почти точно 50% на 50%
Так вот, программа эта, нормализованный файл - может денормализовать назад, в прежний вид.
(я нормализовывал ею файл этого же архива). После денормализации - архив снова открывается архиватором.
А это значило бы, что при помощи подобных программ, в процессе денормализации данных,
можно было бы снизить энтропию (то есть почти равномерное распределение нулей и единиц в бинарном коде файла).

Это получается - что-то типа синергетической архивации, основанной на негэнтропии.

5 Кб, 174x273
61 20 апр 2018, 02:07 61 38622

>>38621
Говоришь так, как будто дерево директрий нельзя записать в txt-файл и ужать этот текстовый файл архиватором.
>Допустим, у нас есть информация размером N бит и супер функция, которая сжимает ее хотя бы на один бит (гарантированно).
Ок.
>Данные у нас хранятся в файлах, а значит всего может существовать 2N различных файлов.
Если по биту на каждый файл писать, то они представляют из себя копии одного и того же файла.
Поэтому при помощи жестких ссылок hardlink - можно минимизировать инфу, сведя её лишь до двух секторов на диске,
и до списка файлов в файловой системе (тот самый txt-шник, о котором я писал выше, с путями и именами файлов).
>Полученные нашей функцией архивы будут иметь размер максимум N-1 бит, а значит может существовать не более 2N-1 архивов.
А нафига ты по одному биту в каждый архив писать собрася?
>Т.е. распаковать наши архивы в исходные файлы без коллизий не получится - архивов всегда минимум в два раза меньше.
Как будто один архив за счёт вычислительных мощностей, при распаковке - не может писать на диск, много архивов.

Кстати, вот здесь: >>38589 по ссылке
>http://www.codenet.ru/progr/alg/normalize/
внутри, есть код, и ссылка на программу с описанием её:
>http://www.codenet.ru/np-includes/upload/2007/08/21/128152.zip
Программа произодит нормализацию исходного кода файлов.
Я попробовал сделать нормализацию, и вижу в шестнадцатиричном редакторе
шестнадцатиричный шум наподобие крипторандома.
Автор пишет, что нормализация означает, что:
>в получаемом файле соотношение 0 и 1 всегда почти точно 50% на 50%
Так вот, программа эта, нормализованный файл - может денормализовать назад, в прежний вид.
(я нормализовывал ею файл этого же архива). После денормализации - архив снова открывается архиватором.
А это значило бы, что при помощи подобных программ, в процессе денормализации данных,
можно было бы снизить энтропию (то есть почти равномерное распределение нулей и единиц в бинарном коде файла).

Это получается - что-то типа синергетической архивации, основанной на негэнтропии.

Показать весь текст
Ответы38624

62 20 апр 2018, 02:23 62 38624

>>38622
Ты нихуя не понял. Файлы не хранят по одному биту и в архивы пишутся не по одному биту. Ты можешь взять любое N, например - 10. Т.е. каждый файл будет хранить 10 бит и всего может существовать 1024 разных файла размером 10 бит, 1025-й уже будет копией одного из предыдущих. Если мы эти 10-тибитные файлы пожмем универсальной суперфункцией до 9 бит, то получим 512 различных архивов. 513-й уже будет копией одного из существующих архивов. А из 512 возможных архивов сделать 1024 исходных файла, очевидно, невозможно.

Все существующие архиваторы занимаются удалением избыточности, т.е. фактически просто переписывают исходное сообщение другим алфавитом, созданным специально для этого сообщения. Попробуй сжать рандомные данные (где нет избыточности) любым существующим архиватором и результат будет больше исходных данных.

Ответы38628

63 20 апр 2018, 06:50 63 38628

>>38624
>А из 512 возможных архивов сделать 1024 исходных файла, очевидно, невозможно.
Когда разархивируешь какой-нибудь zip ты из одного файла много делаешь же.
>Попробуй сжать рандомные данные (где нет избыточности) любым существующим архиватором и результат будет больше исходных данных.
Так вот я и намекал выше на архивацию с уменьшением энтропии - то есть работающую, на принципах синергетической самоорганизации.

Ответы3862938630

64 20 апр 2018, 13:58 64 38629

>>38628
>Так вот я и намекал выше на архивацию с уменьшением энтропии
Двоичная форма - это запись с минимально возможной энтропией. Ее уже невозможно там уменьшить.

65 20 апр 2018, 14:03 65 38630

>>38628
>Когда разархивируешь какой-нибудь zip ты из одного файла много делаешь же.
Ты наркоман, чтоле? В последний раз, предельный случай:
У нас есть информация размером 2 бита. Все возможные варианты: 00 01 10 11
У нас есть функция, сжимающая информацию на один бит. Все возможные результаты: 0 1
Мощность множества "архивов" меньше мощности множества "данных". Обратное восстановление невозможно.

Ответы3864838651

66 20 апр 2018, 18:01 66 38633

>>38621
>Допустим, у нас есть информация размером N бит и супер функция, которая сжимает ее хотя бы на один бит (гарантированно).
Для меня не очень понятно, как невозможность существования такой функции может быть неочевидна для твоего собеседника.

67 21 апр 2018, 06:11 67 38648

>>38039 (OP)
Я ОП, и я вернулся.
Итак, самым эффективным алгоритмом генерации оказался - тест Миллера-Рабина,
сомещённый с циклом перебора нечётных, имеющих вид 6k±1.
За подсказку - спасибо >>38576-анону.
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 миллионов.

>>38630
Двумя битами можно кодировать степень двойки в порождателе инфы,
для дальнейшего перебора всех вариантов от 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
И хотя алгоритм и подвисает, но это намного быстрее, чем прочёсывать все простые числа по каким-то базам данных и диапазонам.

67 21 апр 2018, 06:11 67 38648

>>38039 (OP)
Я ОП, и я вернулся.
Итак, самым эффективным алгоритмом генерации оказался - тест Миллера-Рабина,
сомещённый с циклом перебора нечётных, имеющих вид 6k±1.
За подсказку - спасибо >>38576-анону.
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 миллионов.

>>38630
Двумя битами можно кодировать степень двойки в порождателе инфы,
для дальнейшего перебора всех вариантов от 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
И хотя алгоритм и подвисает, но это намного быстрее, чем прочёсывать все простые числа по каким-то базам данных и диапазонам.

Показать весь текст
Ответы3864942379

68 21 апр 2018, 06:23 68 38649

>>38648
>можно было бы использовать список простых чисел, и сохранять только индексы их.
Даже не индексы, а смещения индексов. Ведь они возрастают, как и сами числа:
Prime factorization:
5×7×11×29×199×1213×5477×1160608367×316134229883×323004876255732144171530186386683923776150893770761
Простые числа, на которые факторизуется составное число - возрастают существенно, а вот индексы - не очень.
К тому же, с ростом значения диапазона натуральных - количество простых чисел в диапазоне убывает.
Процент простых чисел в натуральных - наглядно видно здесь: >>38589, на второй картинке.
Таким образом, если у числа много одинакоых простых делителей можно записать степень, либо индекс простого, и нули за индексом. И эти нули потом, если их много - проще ужать потом ещё и архиватором.
Дальше уже - не индекс, а смещение индекса относительно индекса предыдущего простого.

69 21 апр 2018, 10:39 69 38651

>>38630
Тогда, по индукции, архивирование не может быть произведено ни для какой строки.

Ответы38652

70 21 апр 2018, 14:04 70 38652

>>38651
Так и есть. Арифметический архиватор принципиально невозможен. Это как нарушить закон сохранения.
Но если ОП не верит, пусть попробует. Я когда-то пробовал: и с простыми множителями и с их индексами - в большинстве случаев "сжатый" результат будет больше исходных данных.

Ответы38653

71 21 апр 2018, 14:27 71 38653

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

Рассмотрим функцию f такую, что
f(0) = 00, f(1) = 11, f(01) = 01, f(10) = 10.

Тогда ровно половину двухбитовых архивов удастся закодировать одним битом.

Ответы3865438655

72 21 апр 2018, 14:46 72 38654

>>38653
Как ты в потоке отличишь [0, 1] от [01]? Нужен еще один бит, чтобы указать, когда там однобитный архив, а когда двухбитный, иначе будет неопределенность.

Ответы38656

73 21 апр 2018, 14:57 73 38655

>>38653
Этот способ кодирования используется по другому: если первый бит 1, то после него один бит сжатых данных. Если первый бит 0, то если второй бит 1, то после него джва бита сжатых данных. Если первый бит 0, второй бит 0, третий бит 1, то после него 4 бита сжатых данных и т.п.
1[0..1]
01[00..11]
001[0000..1111]
...
Потом составляется частотная таблица для каждого байта исходных данных и наиболее часто встречающимся байтам назначаются наименее длинные коды. Два байта, которые встречаются чаще всего будут иметь размер по два бита каждый. Следующие 4 байта по частоте будут 4 бита в длину. А наименее частые байты будут иметь длину в несколько байт. Если данные не рандомны (т.е. частота всех байт не одинакова), то результирующий архив будет меньше исходных данных.

Ответы3866738668

74 21 апр 2018, 15:40 74 38656

>>38654
А разве кто-то что-то говорил про поток?

Ответы38658

75 21 апр 2018, 16:42 75 38658

>>38656
А надо бы о нем задуматься, ведь данные надо не только сжать, но еще и как-то хранить и расжать потом.

96 Кб, 514x563
76 22 апр 2018, 00:50 76 38667

>>38655
Чё-то я не пойму как разжать, твоими условиями - вот это двоичное число: 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.
В общем виде, текст ААААБВВГВБДДДАААААГБВД - кодируется кодом Хаффмана, таблицей с деревом Хаффмана,
а также контрольной суммой, от которой надо отнимать повторения каждой буквы из таблицы.

96 Кб, 514x563
76 22 апр 2018, 00:50 76 38667

>>38655
Чё-то я не пойму как разжать, твоими условиями - вот это двоичное число: 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.
В общем виде, текст ААААБВВГВБДДДАААААГБВД - кодируется кодом Хаффмана, таблицей с деревом Хаффмана,
а также контрольной суммой, от которой надо отнимать повторения каждой буквы из таблицы.

Показать весь текст
Ответы3866938673

77 22 апр 2018, 01:01 77 38668

15 Кб, 403x29947 Кб, 422x177

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

Ответы38670

78 22 апр 2018, 01:04 78 38669

>>38667
>Чё-то я не пойму как разжать, твоими условиями
Потому что сжимаешь своими условиями. А разжать ты их не сможешь, потому что при кодировании создаешь неопределенность.

>f(0) = 10, f(1) = 01, f(01) = 00, f(10) = 11
это compress-only архиватор. Таким алгоритмом потомкам можно википедию сжать, пусть поебутся, чтоб не скучали.

Ответы3867138673

79 22 апр 2018, 01:08 79 38670

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

Ответы38671

80 22 апр 2018, 02:09 80 38671

>>38669
Неопределённость можно было бы использовать при наличии вычислительных мощностей,
например, если есть быстрый квантовый компьютер.
Закодировал одним битом два состояния f(1) = 01, f(01) = 00, прицепил хеш полного файла, и всё.
Мне чё-то кажется, что даже при указании одной лишь длины файла количество коллизий резко уменьшится.

>>38670
Ишь ты какой? Ты откуда про мои 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 степень достигнута - следующий байт.

80 22 апр 2018, 02:09 80 38671

>>38669
Неопределённость можно было бы использовать при наличии вычислительных мощностей,
например, если есть быстрый квантовый компьютер.
Закодировал одним битом два состояния f(1) = 01, f(01) = 00, прицепил хеш полного файла, и всё.
Мне чё-то кажется, что даже при указании одной лишь длины файла количество коллизий резко уменьшится.

>>38670
Ишь ты какой? Ты откуда про мои 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 степень достигнута - следующий байт.

Показать весь текст

81 22 апр 2018, 06:30 81 38673

>>38667
>>38669
Вот что нашёл:
https://ru.wikipedia.org/wiki/Сжатие_без_потерь#Метод_сжатия_без_потерь
https://ru.wikipedia.org/wiki/Префиксный_код

Интересно, если поксорить рандом или уже сжатый и несжимаемый код - сам с собой,
можно снизить уменьшить энтропию и потом ещё ужать?
Или можно ли каким-то хитромудрым образом, вот той программой для денормализации файлов -
подобрать такой ключ, который выдаст преобразованный файл - с наименьшим числом единиц?

Ответы38674

82 22 апр 2018, 06:37 82 38674

>>38673
Бля, забыл что тогда будут сплошные нули.
У меня же есть XOR, вот там на сайте onion, в TOR'e - внутри BrainWallet'а.

Ответы38675

83 22 апр 2018, 07:36 83 38675

>>38674
Можно посчитать количество единиц в файле или битовой строке,
затем сравнить с половиной длины файла,
и если единиц больше половины длины этого бинарного кода - то сделать инверсию всего кода,
а потом дописать лишь один бит, символизирующий её
и ужать все те нули, образовавшиеся там, где было дофига единиц.
Если сделать так много раз, то я думаю можно было бы уменьшить энтропию
и свести код
01110111110
к какому-то такому
10001000001,
а потом расписав его в степень двойки так:
10000000000 (2^10) +
00001000000 (2^6)+
00000000001 (2^0)=
сохранить только показатели 0, 6, 10 или их смещения относительно друга 0, 6, 4.

Или представить длинное большое число, как сумму двух простых,
согласно бинарной проблеме Гольдбаха, а сами простые числа - сжать как PrimeGrid,
сделав из них чётные, и разделив дофига раз на два, например.

Ответы38731

84 23 апр 2018, 05:08 84 38681

74 Кб, 541x9009 Кб, 483x77

>>38453
>Наверняка и числа вида 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 из них - простые, ведь)
и кодировать только интервалы между этими индексами, ну потому что корни кубические эти,
в ряду суммы кубов - располагаются по возрастанию.

84 23 апр 2018, 05:08 84 38681

74 Кб, 541x9009 Кб, 483x77

>>38453
>Наверняка и числа вида 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 из них - простые, ведь)
и кодировать только интервалы между этими индексами, ну потому что корни кубические эти,
в ряду суммы кубов - располагаются по возрастанию.

Показать весь текст
Ответы38687

85 23 апр 2018, 14:42 85 38687

>>38681
>можно было бы использовать вместо чисел - только индексы простых чисел
Все равно результат будет занимать больше места, чем само число.
Натуральные числа - это и есть сжатое наилучшим алгоритмом множество произведений простых чисел.

Ответы38731

86 24 апр 2018, 10:34 86 38731

>>38687
Я так и понял, что в сумму кубов двоичное число не сжать.

>>38675
>степень двойки
>>38675
>сохранить только показатели 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-ной степени, или сумму их,
или произведение его с каким-либо небольшим числом.

86 24 апр 2018, 10:34 86 38731

>>38687
Я так и понял, что в сумму кубов двоичное число не сжать.

>>38675
>степень двойки
>>38675
>сохранить только показатели 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-ной степени, или сумму их,
или произведение его с каким-либо небольшим числом.

Показать весь текст
Ответы38751

87 24 апр 2018, 16:00 87 38751

>>38731
>Поэтому не знаю, даст ли произвольное длинное число, представляющее из себя сектор на диске,
>какое-либо разложение на корень n-ной степени, или сумму их,
>или произведение его с каким-либо небольшим числом.
Некоторые, конечно же, дадут. Но по отношению ко всем 256512 числам, которые может представить сектор на диске, их число будет ничтожно мало. Все же остальные будут "сжиматься" таким способом крайне неэффективно (станут намного больше самого исходного числа).

Ответы38757

88 24 апр 2018, 19:38 88 38757

>>38751
То есть ты намекаешь на длинный остаток.
Как например:
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-ной степени, причём какими бы большими они не были.
Или же, представить их - через праймориал.

88 24 апр 2018, 19:38 88 38757

>>38751
То есть ты намекаешь на длинный остаток.
Как например:
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-ной степени, причём какими бы большими они не были.
Или же, представить их - через праймориал.

Показать весь текст
Ответы387593876138782

89 24 апр 2018, 19:45 89 38759

>>38757
>Итан Чжан показал, или даже доказал, что интервал между простыми числами не может быть более 70 миллионов,
Нет. Он доказал, что есть бесконечное число пар простых чисел, между которыми не более 70 млн составных. Это просто приближение к доказательству вроде пока недоказанной гипотезы, что существует бесконечное число простых-близнецов.
В принципе же, разрыв между парой простых чисел может быть абсолютно любой.

Ответы3877338782

90 24 апр 2018, 19:52 90 38761

>>38757
>То есть ты намекаешь на длинный остаток
Нет. Я намекаю на то, что натуральный ряд - это уже архив. Там энтропия минимально возможная и сжать его даже на бит не получится. Лишь некоторую ничтожно малую часть этих чисел можно переписать более компактно. Оставшиеся же, перебьют всю сэкономленную память и сверху еще навалят на порядки больше, чем занимало само число.

Ответы38773

91 25 апр 2018, 00:57 91 38773

>>38761
Во всём ряду, может и да, но отдельные числа можно ещё больше сжать.
Так, например, натуральное число 18446744073709551614, имеющее бинарный вид:
1111111111111111111111111111111111111111111111111111111111111110
может быть выражено всего двумя битами: 1 и ещё 1 бит,
символизирующий инверсию оставшихся 63-х бит. Хочу подчеркнуть, что число натуральное.
И таких чисел в ряду - натуральных - много, на каждое из них - можно выделить и по биту,
если сжимать нули - многократными прогонами префиксного кодирования.

>>38759
Ну, между простыми числами-близнецами может быть ещё дофига простых чисел разных видов.
Я даже проверил - зациклив с рандомного числа алгоритм Миллера-Рабина для каждого конкретного нечётного.
И вот что получилось...

Простые числа длиной 1024 бита:
130341454124268511361589671683820282331561282068405574945037046867157404705885569876181968046817776443073022840838404286132626397576976602718965722741926326403746054664615428828902895650047026429699744843338645411810009738677202895562377441140885715679334820178662070173385328005700679135241947932745462464673
130341454124268511361589671683820282331561282068405574945037046867157404705885569876181968046817776443073022840838404286132626397576976602718965722741926326403746054664615428828902895650047026429699744843338645411810009738677202895562377441140885715679334820178662070173385328005700679135241947932745462464889
130341454124268511361589671683820282331561282068405574945037046867157404705885569876181968046817776443073022840838404286132626397576976602718965722741926326403746054664615428828902895650047026429699744843338645411810009738677202895562377441140885715679334820178662070173385328005700679135241947932745462465607
130341454124268511361589671683820282331561282068405574945037046867157404705885569876181968046817776443073022840838404286132626397576976602718965722741926326403746054664615428828902895650047026429699744843338645411810009738677202895562377441140885715679334820178662070173385328005700679135241947932745462465877
130341454124268511361589671683820282331561282068405574945037046867157404705885569876181968046817776443073022840838404286132626397576976602718965722741926326403746054664615428828902895650047026429699744843338645411810009738677202895562377441140885715679334820178662070173385328005700679135241947932745462465897
130341454124268511361589671683820282331561282068405574945037046867157404705885569876181968046817776443073022840838404286132626397576976602718965722741926326403746054664615428828902895650047026429699744843338645411810009738677202895562377441140885715679334820178662070173385328005700679135241947932745462466147
130341454124268511361589671683820282331561282068405574945037046867157404705885569876181968046817776443073022840838404286132626397576976602718965722741926326403746054664615428828902895650047026429699744843338645411810009738677202895562377441140885715679334820178662070173385328005700679135241947932745462466269
130341454124268511361589671683820282331561282068405574945037046867157404705885569876181968046817776443073022840838404286132626397576976602718965722741926326403746054664615428828902895650047026429699744843338645411810009738677202895562377441140885715679334820178662070173385328005700679135241947932745462466317
130341454124268511361589671683820282331561282068405574945037046867157404705885569876181968046817776443073022840838404286132626397576976602718965722741926326403746054664615428828902895650047026429699744843338645411810009738677202895562377441140885715679334820178662070173385328005700679135241947932745462466869
130341454124268511361589671683820282331561282068405574945037046867157404705885569876181968046817776443073022840838404286132626397576976602718965722741926326403746054664615428828902895650047026429699744843338645411810009738677202895562377441140885715679334820178662070173385328005700679135241947932745462467241

Простые числа длиной 2048 бит:
21894522688173756518387509995253958704268650919380741160068056991226576652537628754644264895435856354147612343217117209366305017382894505733026140913413882817495851973374969623377139375449641938210847324176820868735983294429307271769970891706180198116465335419602471925379728494564736572313661243905640883039531280416030435734976123313673612001126259164031919936749302013472219124881546261385713221731806830502862030086331885023727955202834481010696866904774814380192780846179486511261293778786507647997805206107563484930117826257855349238784801300846796108163038193745394400472632071926087475316262676417598331659257
21894522688173756518387509995253958704268650919380741160068056991226576652537628754644264895435856354147612343217117209366305017382894505733026140913413882817495851973374969623377139375449641938210847324176820868735983294429307271769970891706180198116465335419602471925379728494564736572313661243905640883039531280416030435734976123313673612001126259164031919936749302013472219124881546261385713221731806830502862030086331885023727955202834481010696866904774814380192780846179486511261293778786507647997805206107563484930117826257855349238784801300846796108163038193745394400472632071926087475316262676417598331660187
21894522688173756518387509995253958704268650919380741160068056991226576652537628754644264895435856354147612343217117209366305017382894505733026140913413882817495851973374969623377139375449641938210847324176820868735983294429307271769970891706180198116465335419602471925379728494564736572313661243905640883039531280416030435734976123313673612001126259164031919936749302013472219124881546261385713221731806830502862030086331885023727955202834481010696866904774814380192780846179486511261293778786507647997805206107563484930117826257855349238784801300846796108163038193745394400472632071926087475316262676417598331661021
21894522688173756518387509995253958704268650919380741160068056991226576652537628754644264895435856354147612343217117209366305017382894505733026140913413882817495851973374969623377139375449641938210847324176820868735983294429307271769970891706180198116465335419602471925379728494564736572313661243905640883039531280416030435734976123313673612001126259164031919936749302013472219124881546261385713221731806830502862030086331885023727955202834481010696866904774814380192780846179486511261293778786507647997805206107563484930117826257855349238784801300846796108163038193745394400472632071926087475316262676417598331667759
21894522688173756518387509995253958704268650919380741160068056991226576652537628754644264895435856354147612343217117209366305017382894505733026140913413882817495851973374969623377139375449641938210847324176820868735983294429307271769970891706180198116465335419602471925379728494564736572313661243905640883039531280416030435734976123313673612001126259164031919936749302013472219124881546261385713221731806830502862030086331885023727955202834481010696866904774814380192780846179486511261293778786507647997805206107563484930117826257855349238784801300846796108163038193745394400472632071926087475316262676417598331667767
21894522688173756518387509995253958704268650919380741160068056991226576652537628754644264895435856354147612343217117209366305017382894505733026140913413882817495851973374969623377139375449641938210847324176820868735983294429307271769970891706180198116465335419602471925379728494564736572313661243905640883039531280416030435734976123313673612001126259164031919936749302013472219124881546261385713221731806830502862030086331885023727955202834481010696866904774814380192780846179486511261293778786507647997805206107563484930117826257855349238784801300846796108163038193745394400472632071926087475316262676417598331671851
21894522688173756518387509995253958704268650919380741160068056991226576652537628754644264895435856354147612343217117209366305017382894505733026140913413882817495851973374969623377139375449641938210847324176820868735983294429307271769970891706180198116465335419602471925379728494564736572313661243905640883039531280416030435734976123313673612001126259164031919936749302013472219124881546261385713221731806830502862030086331885023727955202834481010696866904774814380192780846179486511261293778786507647997805206107563484930117826257855349238784801300846796108163038193745394400472632071926087475316262676417598331676729
21894522688173756518387509995253958704268650919380741160068056991226576652537628754644264895435856354147612343217117209366305017382894505733026140913413882817495851973374969623377139375449641938210847324176820868735983294429307271769970891706180198116465335419602471925379728494564736572313661243905640883039531280416030435734976123313673612001126259164031919936749302013472219124881546261385713221731806830502862030086331885023727955202834481010696866904774814380192780846179486511261293778786507647997805206107563484930117826257855349238784801300846796108163038193745394400472632071926087475316262676417598331677107
21894522688173756518387509995253958704268650919380741160068056991226576652537628754644264895435856354147612343217117209366305017382894505733026140913413882817495851973374969623377139375449641938210847324176820868735983294429307271769970891706180198116465335419602471925379728494564736572313661243905640883039531280416030435734976123313673612001126259164031919936749302013472219124881546261385713221731806830502862030086331885023727955202834481010696866904774814380192780846179486511261293778786507647997805206107563484930117826257855349238784801300846796108163038193745394400472632071926087475316262676417598331677737
21894522688173756518387509995253958704268650919380741160068056991226576652537628754644264895435856354147612343217117209366305017382894505733026140913413882817495851973374969623377139375449641938210847324176820868735983294429307271769970891706180198116465335419602471925379728494564736572313661243905640883039531280416030435734976123313673612001126259164031919936749302013472219124881546261385713221731806830502862030086331885023727955202834481010696866904774814380192780846179486511261293778786507647997805206107563484930117826257855349238784801300846796108163038193745394400472632071926087475316262676417598331679297

91 25 апр 2018, 00:57 91 38773

>>38761
Во всём ряду, может и да, но отдельные числа можно ещё больше сжать.
Так, например, натуральное число 18446744073709551614, имеющее бинарный вид:
1111111111111111111111111111111111111111111111111111111111111110
может быть выражено всего двумя битами: 1 и ещё 1 бит,
символизирующий инверсию оставшихся 63-х бит. Хочу подчеркнуть, что число натуральное.
И таких чисел в ряду - натуральных - много, на каждое из них - можно выделить и по биту,
если сжимать нули - многократными прогонами префиксного кодирования.

>>38759
Ну, между простыми числами-близнецами может быть ещё дофига простых чисел разных видов.
Я даже проверил - зациклив с рандомного числа алгоритм Миллера-Рабина для каждого конкретного нечётного.
И вот что получилось...

Простые числа длиной 1024 бита:
130341454124268511361589671683820282331561282068405574945037046867157404705885569876181968046817776443073022840838404286132626397576976602718965722741926326403746054664615428828902895650047026429699744843338645411810009738677202895562377441140885715679334820178662070173385328005700679135241947932745462464673
130341454124268511361589671683820282331561282068405574945037046867157404705885569876181968046817776443073022840838404286132626397576976602718965722741926326403746054664615428828902895650047026429699744843338645411810009738677202895562377441140885715679334820178662070173385328005700679135241947932745462464889
130341454124268511361589671683820282331561282068405574945037046867157404705885569876181968046817776443073022840838404286132626397576976602718965722741926326403746054664615428828902895650047026429699744843338645411810009738677202895562377441140885715679334820178662070173385328005700679135241947932745462465607
130341454124268511361589671683820282331561282068405574945037046867157404705885569876181968046817776443073022840838404286132626397576976602718965722741926326403746054664615428828902895650047026429699744843338645411810009738677202895562377441140885715679334820178662070173385328005700679135241947932745462465877
130341454124268511361589671683820282331561282068405574945037046867157404705885569876181968046817776443073022840838404286132626397576976602718965722741926326403746054664615428828902895650047026429699744843338645411810009738677202895562377441140885715679334820178662070173385328005700679135241947932745462465897
130341454124268511361589671683820282331561282068405574945037046867157404705885569876181968046817776443073022840838404286132626397576976602718965722741926326403746054664615428828902895650047026429699744843338645411810009738677202895562377441140885715679334820178662070173385328005700679135241947932745462466147
130341454124268511361589671683820282331561282068405574945037046867157404705885569876181968046817776443073022840838404286132626397576976602718965722741926326403746054664615428828902895650047026429699744843338645411810009738677202895562377441140885715679334820178662070173385328005700679135241947932745462466269
130341454124268511361589671683820282331561282068405574945037046867157404705885569876181968046817776443073022840838404286132626397576976602718965722741926326403746054664615428828902895650047026429699744843338645411810009738677202895562377441140885715679334820178662070173385328005700679135241947932745462466317
130341454124268511361589671683820282331561282068405574945037046867157404705885569876181968046817776443073022840838404286132626397576976602718965722741926326403746054664615428828902895650047026429699744843338645411810009738677202895562377441140885715679334820178662070173385328005700679135241947932745462466869
130341454124268511361589671683820282331561282068405574945037046867157404705885569876181968046817776443073022840838404286132626397576976602718965722741926326403746054664615428828902895650047026429699744843338645411810009738677202895562377441140885715679334820178662070173385328005700679135241947932745462467241

Простые числа длиной 2048 бит:
21894522688173756518387509995253958704268650919380741160068056991226576652537628754644264895435856354147612343217117209366305017382894505733026140913413882817495851973374969623377139375449641938210847324176820868735983294429307271769970891706180198116465335419602471925379728494564736572313661243905640883039531280416030435734976123313673612001126259164031919936749302013472219124881546261385713221731806830502862030086331885023727955202834481010696866904774814380192780846179486511261293778786507647997805206107563484930117826257855349238784801300846796108163038193745394400472632071926087475316262676417598331659257
21894522688173756518387509995253958704268650919380741160068056991226576652537628754644264895435856354147612343217117209366305017382894505733026140913413882817495851973374969623377139375449641938210847324176820868735983294429307271769970891706180198116465335419602471925379728494564736572313661243905640883039531280416030435734976123313673612001126259164031919936749302013472219124881546261385713221731806830502862030086331885023727955202834481010696866904774814380192780846179486511261293778786507647997805206107563484930117826257855349238784801300846796108163038193745394400472632071926087475316262676417598331660187
21894522688173756518387509995253958704268650919380741160068056991226576652537628754644264895435856354147612343217117209366305017382894505733026140913413882817495851973374969623377139375449641938210847324176820868735983294429307271769970891706180198116465335419602471925379728494564736572313661243905640883039531280416030435734976123313673612001126259164031919936749302013472219124881546261385713221731806830502862030086331885023727955202834481010696866904774814380192780846179486511261293778786507647997805206107563484930117826257855349238784801300846796108163038193745394400472632071926087475316262676417598331661021
21894522688173756518387509995253958704268650919380741160068056991226576652537628754644264895435856354147612343217117209366305017382894505733026140913413882817495851973374969623377139375449641938210847324176820868735983294429307271769970891706180198116465335419602471925379728494564736572313661243905640883039531280416030435734976123313673612001126259164031919936749302013472219124881546261385713221731806830502862030086331885023727955202834481010696866904774814380192780846179486511261293778786507647997805206107563484930117826257855349238784801300846796108163038193745394400472632071926087475316262676417598331667759
21894522688173756518387509995253958704268650919380741160068056991226576652537628754644264895435856354147612343217117209366305017382894505733026140913413882817495851973374969623377139375449641938210847324176820868735983294429307271769970891706180198116465335419602471925379728494564736572313661243905640883039531280416030435734976123313673612001126259164031919936749302013472219124881546261385713221731806830502862030086331885023727955202834481010696866904774814380192780846179486511261293778786507647997805206107563484930117826257855349238784801300846796108163038193745394400472632071926087475316262676417598331667767
21894522688173756518387509995253958704268650919380741160068056991226576652537628754644264895435856354147612343217117209366305017382894505733026140913413882817495851973374969623377139375449641938210847324176820868735983294429307271769970891706180198116465335419602471925379728494564736572313661243905640883039531280416030435734976123313673612001126259164031919936749302013472219124881546261385713221731806830502862030086331885023727955202834481010696866904774814380192780846179486511261293778786507647997805206107563484930117826257855349238784801300846796108163038193745394400472632071926087475316262676417598331671851
21894522688173756518387509995253958704268650919380741160068056991226576652537628754644264895435856354147612343217117209366305017382894505733026140913413882817495851973374969623377139375449641938210847324176820868735983294429307271769970891706180198116465335419602471925379728494564736572313661243905640883039531280416030435734976123313673612001126259164031919936749302013472219124881546261385713221731806830502862030086331885023727955202834481010696866904774814380192780846179486511261293778786507647997805206107563484930117826257855349238784801300846796108163038193745394400472632071926087475316262676417598331676729
21894522688173756518387509995253958704268650919380741160068056991226576652537628754644264895435856354147612343217117209366305017382894505733026140913413882817495851973374969623377139375449641938210847324176820868735983294429307271769970891706180198116465335419602471925379728494564736572313661243905640883039531280416030435734976123313673612001126259164031919936749302013472219124881546261385713221731806830502862030086331885023727955202834481010696866904774814380192780846179486511261293778786507647997805206107563484930117826257855349238784801300846796108163038193745394400472632071926087475316262676417598331677107
21894522688173756518387509995253958704268650919380741160068056991226576652537628754644264895435856354147612343217117209366305017382894505733026140913413882817495851973374969623377139375449641938210847324176820868735983294429307271769970891706180198116465335419602471925379728494564736572313661243905640883039531280416030435734976123313673612001126259164031919936749302013472219124881546261385713221731806830502862030086331885023727955202834481010696866904774814380192780846179486511261293778786507647997805206107563484930117826257855349238784801300846796108163038193745394400472632071926087475316262676417598331677737
21894522688173756518387509995253958704268650919380741160068056991226576652537628754644264895435856354147612343217117209366305017382894505733026140913413882817495851973374969623377139375449641938210847324176820868735983294429307271769970891706180198116465335419602471925379728494564736572313661243905640883039531280416030435734976123313673612001126259164031919936749302013472219124881546261385713221731806830502862030086331885023727955202834481010696866904774814380192780846179486511261293778786507647997805206107563484930117826257855349238784801300846796108163038193745394400472632071926087475316262676417598331679297

Показать весь текст
Ответы3877439121

92 25 апр 2018, 00:57 92 38774

>>38773
Простые числа длиной 4096 bit:
652847511922665051218342821505509360505472799862368633568780170538745984238166668012067318042425171493000391274259624160197650107291873808506689216240034938220221245930032199305948006645670800375358054981521364280623712444472308613777461406892411532021075448168109786072434294667042228646992211867788877495766692398047074302715717236431331194949079884375541133608089357670962195053633600079171675977808957516254418592651994078835346903333766010277887798264226256202944980219028678779858060203957762810913529347040540456105103604408908176444791718619284345489704506301110329022983689819824140988354988806218558891581812927042301282247588981375127638378966037895465948710323067785582924083374083196300144749326784485671226533936478706537934575380366710296906390842785413493838256752655933754149302160673331910960394041675049651633757853497099855509954720284269917359840926699780511948083290338559068928397359556520037318719291214305469977224683963954017831362210405053639986770514860371072137296085841335739070812637304503372574919575902068948992715756760971657107883394344324872799345511368099734406525430574930207642218154379802891909069947879122390885777274022704627660795382619271213806627167783627218483308419889081617252238409601
652847511922665051218342821505509360505472799862368633568780170538745984238166668012067318042425171493000391274259624160197650107291873808506689216240034938220221245930032199305948006645670800375358054981521364280623712444472308613777461406892411532021075448168109786072434294667042228646992211867788877495766692398047074302715717236431331194949079884375541133608089357670962195053633600079171675977808957516254418592651994078835346903333766010277887798264226256202944980219028678779858060203957762810913529347040540456105103604408908176444791718619284345489704506301110329022983689819824140988354988806218558891581812927042301282247588981375127638378966037895465948710323067785582924083374083196300144749326784485671226533936478706537934575380366710296906390842785413493838256752655933754149302160673331910960394041675049651633757853497099855509954720284269917359840926699780511948083290338559068928397359556520037318719291214305469977224683963954017831362210405053639986770514860371072137296085841335739070812637304503372574919575902068948992715756760971657107883394344324872799345511368099734406525430574930207642218154379802891909069947879122390885777274022704627660795382619271213806627167783627218483308419889081617252238411059
652847511922665051218342821505509360505472799862368633568780170538745984238166668012067318042425171493000391274259624160197650107291873808506689216240034938220221245930032199305948006645670800375358054981521364280623712444472308613777461406892411532021075448168109786072434294667042228646992211867788877495766692398047074302715717236431331194949079884375541133608089357670962195053633600079171675977808957516254418592651994078835346903333766010277887798264226256202944980219028678779858060203957762810913529347040540456105103604408908176444791718619284345489704506301110329022983689819824140988354988806218558891581812927042301282247588981375127638378966037895465948710323067785582924083374083196300144749326784485671226533936478706537934575380366710296906390842785413493838256752655933754149302160673331910960394041675049651633757853497099855509954720284269917359840926699780511948083290338559068928397359556520037318719291214305469977224683963954017831362210405053639986770514860371072137296085841335739070812637304503372574919575902068948992715756760971657107883394344324872799345511368099734406525430574930207642218154379802891909069947879122390885777274022704627660795382619271213806627167783627218483308419889081617252238411173
652847511922665051218342821505509360505472799862368633568780170538745984238166668012067318042425171493000391274259624160197650107291873808506689216240034938220221245930032199305948006645670800375358054981521364280623712444472308613777461406892411532021075448168109786072434294667042228646992211867788877495766692398047074302715717236431331194949079884375541133608089357670962195053633600079171675977808957516254418592651994078835346903333766010277887798264226256202944980219028678779858060203957762810913529347040540456105103604408908176444791718619284345489704506301110329022983689819824140988354988806218558891581812927042301282247588981375127638378966037895465948710323067785582924083374083196300144749326784485671226533936478706537934575380366710296906390842785413493838256752655933754149302160673331910960394041675049651633757853497099855509954720284269917359840926699780511948083290338559068928397359556520037318719291214305469977224683963954017831362210405053639986770514860371072137296085841335739070812637304503372574919575902068948992715756760971657107883394344324872799345511368099734406525430574930207642218154379802891909069947879122390885777274022704627660795382619271213806627167783627218483308419889081617252238412387
652847511922665051218342821505509360505472799862368633568780170538745984238166668012067318042425171493000391274259624160197650107291873808506689216240034938220221245930032199305948006645670800375358054981521364280623712444472308613777461406892411532021075448168109786072434294667042228646992211867788877495766692398047074302715717236431331194949079884375541133608089357670962195053633600079171675977808957516254418592651994078835346903333766010277887798264226256202944980219028678779858060203957762810913529347040540456105103604408908176444791718619284345489704506301110329022983689819824140988354988806218558891581812927042301282247588981375127638378966037895465948710323067785582924083374083196300144749326784485671226533936478706537934575380366710296906390842785413493838256752655933754149302160673331910960394041675049651633757853497099855509954720284269917359840926699780511948083290338559068928397359556520037318719291214305469977224683963954017831362210405053639986770514860371072137296085841335739070812637304503372574919575902068948992715756760971657107883394344324872799345511368099734406525430574930207642218154379802891909069947879122390885777274022704627660795382619271213806627167783627218483308419889081617252238415627
652847511922665051218342821505509360505472799862368633568780170538745984238166668012067318042425171493000391274259624160197650107291873808506689216240034938220221245930032199305948006645670800375358054981521364280623712444472308613777461406892411532021075448168109786072434294667042228646992211867788877495766692398047074302715717236431331194949079884375541133608089357670962195053633600079171675977808957516254418592651994078835346903333766010277887798264226256202944980219028678779858060203957762810913529347040540456105103604408908176444791718619284345489704506301110329022983689819824140988354988806218558891581812927042301282247588981375127638378966037895465948710323067785582924083374083196300144749326784485671226533936478706537934575380366710296906390842785413493838256752655933754149302160673331910960394041675049651633757853497099855509954720284269917359840926699780511948083290338559068928397359556520037318719291214305469977224683963954017831362210405053639986770514860371072137296085841335739070812637304503372574919575902068948992715756760971657107883394344324872799345511368099734406525430574930207642218154379802891909069947879122390885777274022704627660795382619271213806627167783627218483308419889081617252238419081
652847511922665051218342821505509360505472799862368633568780170538745984238166668012067318042425171493000391274259624160197650107291873808506689216240034938220221245930032199305948006645670800375358054981521364280623712444472308613777461406892411532021075448168109786072434294667042228646992211867788877495766692398047074302715717236431331194949079884375541133608089357670962195053633600079171675977808957516254418592651994078835346903333766010277887798264226256202944980219028678779858060203957762810913529347040540456105103604408908176444791718619284345489704506301110329022983689819824140988354988806218558891581812927042301282247588981375127638378966037895465948710323067785582924083374083196300144749326784485671226533936478706537934575380366710296906390842785413493838256752655933754149302160673331910960394041675049651633757853497099855509954720284269917359840926699780511948083290338559068928397359556520037318719291214305469977224683963954017831362210405053639986770514860371072137296085841335739070812637304503372574919575902068948992715756760971657107883394344324872799345511368099734406525430574930207642218154379802891909069947879122390885777274022704627660795382619271213806627167783627218483308419889081617252238421567
652847511922665051218342821505509360505472799862368633568780170538745984238166668012067318042425171493000391274259624160197650107291873808506689216240034938220221245930032199305948006645670800375358054981521364280623712444472308613777461406892411532021075448168109786072434294667042228646992211867788877495766692398047074302715717236431331194949079884375541133608089357670962195053633600079171675977808957516254418592651994078835346903333766010277887798264226256202944980219028678779858060203957762810913529347040540456105103604408908176444791718619284345489704506301110329022983689819824140988354988806218558891581812927042301282247588981375127638378966037895465948710323067785582924083374083196300144749326784485671226533936478706537934575380366710296906390842785413493838256752655933754149302160673331910960394041675049651633757853497099855509954720284269917359840926699780511948083290338559068928397359556520037318719291214305469977224683963954017831362210405053639986770514860371072137296085841335739070812637304503372574919575902068948992715756760971657107883394344324872799345511368099734406525430574930207642218154379802891909069947879122390885777274022704627660795382619271213806627167783627218483308419889081617252238422191
652847511922665051218342821505509360505472799862368633568780170538745984238166668012067318042425171493000391274259624160197650107291873808506689216240034938220221245930032199305948006645670800375358054981521364280623712444472308613777461406892411532021075448168109786072434294667042228646992211867788877495766692398047074302715717236431331194949079884375541133608089357670962195053633600079171675977808957516254418592651994078835346903333766010277887798264226256202944980219028678779858060203957762810913529347040540456105103604408908176444791718619284345489704506301110329022983689819824140988354988806218558891581812927042301282247588981375127638378966037895465948710323067785582924083374083196300144749326784485671226533936478706537934575380366710296906390842785413493838256752655933754149302160673331910960394041675049651633757853497099855509954720284269917359840926699780511948083290338559068928397359556520037318719291214305469977224683963954017831362210405053639986770514860371072137296085841335739070812637304503372574919575902068948992715756760971657107883394344324872799345511368099734406525430574930207642218154379802891909069947879122390885777274022704627660795382619271213806627167783627218483308419889081617252238422857
652847511922665051218342821505509360505472799862368633568780170538745984238166668012067318042425171493000391274259624160197650107291873808506689216240034938220221245930032199305948006645670800375358054981521364280623712444472308613777461406892411532021075448168109786072434294667042228646992211867788877495766692398047074302715717236431331194949079884375541133608089357670962195053633600079171675977808957516254418592651994078835346903333766010277887798264226256202944980219028678779858060203957762810913529347040540456105103604408908176444791718619284345489704506301110329022983689819824140988354988806218558891581812927042301282247588981375127638378966037895465948710323067785582924083374083196300144749326784485671226533936478706537934575380366710296906390842785413493838256752655933754149302160673331910960394041675049651633757853497099855509954720284269917359840926699780511948083290338559068928397359556520037318719291214305469977224683963954017831362210405053639986770514860371072137296085841335739070812637304503372574919575902068948992715756760971657107883394344324872799345511368099734406525430574930207642218154379802891909069947879122390885777274022704627660795382619271213806627167783627218483308419889081617252238423281

Как видишь, отличаются они - лишь десятками тысяч. В википедии, в статье про сектор диска - я вижу следующее:
Новые жесткие диски используют размер сектора 4096 байт (4 Кбайт), известный как расширенный формат (Advanced Format),
и эти числа - как раз длиною в сектор.

92 25 апр 2018, 00:57 92 38774

>>38773
Простые числа длиной 4096 bit:
652847511922665051218342821505509360505472799862368633568780170538745984238166668012067318042425171493000391274259624160197650107291873808506689216240034938220221245930032199305948006645670800375358054981521364280623712444472308613777461406892411532021075448168109786072434294667042228646992211867788877495766692398047074302715717236431331194949079884375541133608089357670962195053633600079171675977808957516254418592651994078835346903333766010277887798264226256202944980219028678779858060203957762810913529347040540456105103604408908176444791718619284345489704506301110329022983689819824140988354988806218558891581812927042301282247588981375127638378966037895465948710323067785582924083374083196300144749326784485671226533936478706537934575380366710296906390842785413493838256752655933754149302160673331910960394041675049651633757853497099855509954720284269917359840926699780511948083290338559068928397359556520037318719291214305469977224683963954017831362210405053639986770514860371072137296085841335739070812637304503372574919575902068948992715756760971657107883394344324872799345511368099734406525430574930207642218154379802891909069947879122390885777274022704627660795382619271213806627167783627218483308419889081617252238409601
652847511922665051218342821505509360505472799862368633568780170538745984238166668012067318042425171493000391274259624160197650107291873808506689216240034938220221245930032199305948006645670800375358054981521364280623712444472308613777461406892411532021075448168109786072434294667042228646992211867788877495766692398047074302715717236431331194949079884375541133608089357670962195053633600079171675977808957516254418592651994078835346903333766010277887798264226256202944980219028678779858060203957762810913529347040540456105103604408908176444791718619284345489704506301110329022983689819824140988354988806218558891581812927042301282247588981375127638378966037895465948710323067785582924083374083196300144749326784485671226533936478706537934575380366710296906390842785413493838256752655933754149302160673331910960394041675049651633757853497099855509954720284269917359840926699780511948083290338559068928397359556520037318719291214305469977224683963954017831362210405053639986770514860371072137296085841335739070812637304503372574919575902068948992715756760971657107883394344324872799345511368099734406525430574930207642218154379802891909069947879122390885777274022704627660795382619271213806627167783627218483308419889081617252238411059
652847511922665051218342821505509360505472799862368633568780170538745984238166668012067318042425171493000391274259624160197650107291873808506689216240034938220221245930032199305948006645670800375358054981521364280623712444472308613777461406892411532021075448168109786072434294667042228646992211867788877495766692398047074302715717236431331194949079884375541133608089357670962195053633600079171675977808957516254418592651994078835346903333766010277887798264226256202944980219028678779858060203957762810913529347040540456105103604408908176444791718619284345489704506301110329022983689819824140988354988806218558891581812927042301282247588981375127638378966037895465948710323067785582924083374083196300144749326784485671226533936478706537934575380366710296906390842785413493838256752655933754149302160673331910960394041675049651633757853497099855509954720284269917359840926699780511948083290338559068928397359556520037318719291214305469977224683963954017831362210405053639986770514860371072137296085841335739070812637304503372574919575902068948992715756760971657107883394344324872799345511368099734406525430574930207642218154379802891909069947879122390885777274022704627660795382619271213806627167783627218483308419889081617252238411173
652847511922665051218342821505509360505472799862368633568780170538745984238166668012067318042425171493000391274259624160197650107291873808506689216240034938220221245930032199305948006645670800375358054981521364280623712444472308613777461406892411532021075448168109786072434294667042228646992211867788877495766692398047074302715717236431331194949079884375541133608089357670962195053633600079171675977808957516254418592651994078835346903333766010277887798264226256202944980219028678779858060203957762810913529347040540456105103604408908176444791718619284345489704506301110329022983689819824140988354988806218558891581812927042301282247588981375127638378966037895465948710323067785582924083374083196300144749326784485671226533936478706537934575380366710296906390842785413493838256752655933754149302160673331910960394041675049651633757853497099855509954720284269917359840926699780511948083290338559068928397359556520037318719291214305469977224683963954017831362210405053639986770514860371072137296085841335739070812637304503372574919575902068948992715756760971657107883394344324872799345511368099734406525430574930207642218154379802891909069947879122390885777274022704627660795382619271213806627167783627218483308419889081617252238412387
652847511922665051218342821505509360505472799862368633568780170538745984238166668012067318042425171493000391274259624160197650107291873808506689216240034938220221245930032199305948006645670800375358054981521364280623712444472308613777461406892411532021075448168109786072434294667042228646992211867788877495766692398047074302715717236431331194949079884375541133608089357670962195053633600079171675977808957516254418592651994078835346903333766010277887798264226256202944980219028678779858060203957762810913529347040540456105103604408908176444791718619284345489704506301110329022983689819824140988354988806218558891581812927042301282247588981375127638378966037895465948710323067785582924083374083196300144749326784485671226533936478706537934575380366710296906390842785413493838256752655933754149302160673331910960394041675049651633757853497099855509954720284269917359840926699780511948083290338559068928397359556520037318719291214305469977224683963954017831362210405053639986770514860371072137296085841335739070812637304503372574919575902068948992715756760971657107883394344324872799345511368099734406525430574930207642218154379802891909069947879122390885777274022704627660795382619271213806627167783627218483308419889081617252238415627
652847511922665051218342821505509360505472799862368633568780170538745984238166668012067318042425171493000391274259624160197650107291873808506689216240034938220221245930032199305948006645670800375358054981521364280623712444472308613777461406892411532021075448168109786072434294667042228646992211867788877495766692398047074302715717236431331194949079884375541133608089357670962195053633600079171675977808957516254418592651994078835346903333766010277887798264226256202944980219028678779858060203957762810913529347040540456105103604408908176444791718619284345489704506301110329022983689819824140988354988806218558891581812927042301282247588981375127638378966037895465948710323067785582924083374083196300144749326784485671226533936478706537934575380366710296906390842785413493838256752655933754149302160673331910960394041675049651633757853497099855509954720284269917359840926699780511948083290338559068928397359556520037318719291214305469977224683963954017831362210405053639986770514860371072137296085841335739070812637304503372574919575902068948992715756760971657107883394344324872799345511368099734406525430574930207642218154379802891909069947879122390885777274022704627660795382619271213806627167783627218483308419889081617252238419081
652847511922665051218342821505509360505472799862368633568780170538745984238166668012067318042425171493000391274259624160197650107291873808506689216240034938220221245930032199305948006645670800375358054981521364280623712444472308613777461406892411532021075448168109786072434294667042228646992211867788877495766692398047074302715717236431331194949079884375541133608089357670962195053633600079171675977808957516254418592651994078835346903333766010277887798264226256202944980219028678779858060203957762810913529347040540456105103604408908176444791718619284345489704506301110329022983689819824140988354988806218558891581812927042301282247588981375127638378966037895465948710323067785582924083374083196300144749326784485671226533936478706537934575380366710296906390842785413493838256752655933754149302160673331910960394041675049651633757853497099855509954720284269917359840926699780511948083290338559068928397359556520037318719291214305469977224683963954017831362210405053639986770514860371072137296085841335739070812637304503372574919575902068948992715756760971657107883394344324872799345511368099734406525430574930207642218154379802891909069947879122390885777274022704627660795382619271213806627167783627218483308419889081617252238421567
652847511922665051218342821505509360505472799862368633568780170538745984238166668012067318042425171493000391274259624160197650107291873808506689216240034938220221245930032199305948006645670800375358054981521364280623712444472308613777461406892411532021075448168109786072434294667042228646992211867788877495766692398047074302715717236431331194949079884375541133608089357670962195053633600079171675977808957516254418592651994078835346903333766010277887798264226256202944980219028678779858060203957762810913529347040540456105103604408908176444791718619284345489704506301110329022983689819824140988354988806218558891581812927042301282247588981375127638378966037895465948710323067785582924083374083196300144749326784485671226533936478706537934575380366710296906390842785413493838256752655933754149302160673331910960394041675049651633757853497099855509954720284269917359840926699780511948083290338559068928397359556520037318719291214305469977224683963954017831362210405053639986770514860371072137296085841335739070812637304503372574919575902068948992715756760971657107883394344324872799345511368099734406525430574930207642218154379802891909069947879122390885777274022704627660795382619271213806627167783627218483308419889081617252238422191
652847511922665051218342821505509360505472799862368633568780170538745984238166668012067318042425171493000391274259624160197650107291873808506689216240034938220221245930032199305948006645670800375358054981521364280623712444472308613777461406892411532021075448168109786072434294667042228646992211867788877495766692398047074302715717236431331194949079884375541133608089357670962195053633600079171675977808957516254418592651994078835346903333766010277887798264226256202944980219028678779858060203957762810913529347040540456105103604408908176444791718619284345489704506301110329022983689819824140988354988806218558891581812927042301282247588981375127638378966037895465948710323067785582924083374083196300144749326784485671226533936478706537934575380366710296906390842785413493838256752655933754149302160673331910960394041675049651633757853497099855509954720284269917359840926699780511948083290338559068928397359556520037318719291214305469977224683963954017831362210405053639986770514860371072137296085841335739070812637304503372574919575902068948992715756760971657107883394344324872799345511368099734406525430574930207642218154379802891909069947879122390885777274022704627660795382619271213806627167783627218483308419889081617252238422857
652847511922665051218342821505509360505472799862368633568780170538745984238166668012067318042425171493000391274259624160197650107291873808506689216240034938220221245930032199305948006645670800375358054981521364280623712444472308613777461406892411532021075448168109786072434294667042228646992211867788877495766692398047074302715717236431331194949079884375541133608089357670962195053633600079171675977808957516254418592651994078835346903333766010277887798264226256202944980219028678779858060203957762810913529347040540456105103604408908176444791718619284345489704506301110329022983689819824140988354988806218558891581812927042301282247588981375127638378966037895465948710323067785582924083374083196300144749326784485671226533936478706537934575380366710296906390842785413493838256752655933754149302160673331910960394041675049651633757853497099855509954720284269917359840926699780511948083290338559068928397359556520037318719291214305469977224683963954017831362210405053639986770514860371072137296085841335739070812637304503372574919575902068948992715756760971657107883394344324872799345511368099734406525430574930207642218154379802891909069947879122390885777274022704627660795382619271213806627167783627218483308419889081617252238423281

Как видишь, отличаются они - лишь десятками тысяч. В википедии, в статье про сектор диска - я вижу следующее:
Новые жесткие диски используют размер сектора 4096 байт (4 Кбайт), известный как расширенный формат (Advanced Format),
и эти числа - как раз длиною в сектор.

Показать весь текст
Ответы39121

93 25 апр 2018, 01:44 93 38782

>>38759
Да и вообще, судя по функции распределения простых чисел - она зависит от логарифма, причём натурального, и судя по этой таблице
https://ru.wikipedia.org/wiki/Функция_распределения_простых_чисел#Таблицы_для_пи-функции,_x_/_ln_x_и_li(x)
процент простых чисел далеко-далеко - приближается к 1% и там зависает около того.
Есть же график логарифмической функции, и PrimePI-функция подобна ей.

И ещё вопрос оставлю тут:
Аноны, кто-нибудь знает - как выдрать с исходного кода, отсюда >>38757,
по ссылкам внутри там - все фрагменты, да так их закомментировать - чтобы в одном 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[2]
хотя там довольно точно рассчитывается этот интегральный логарифм.

Ответы38785

94 25 апр 2018, 04:47 94 38785

>>38782
Поставил Anaconda (python со вшитым sympy), без всяких багов - попёрли цифры...

Интегральный логарифм с точностью до 1000 знаков:
>>> li(2).evalf(1000)
1.045163780117492784844588889194613136522615578151201575832909144075013205210359
53017271740562638335630602082976887474662228523978521965027902108233455784540551
59053003222632748284543905148534966228633054761993303044191709434064183547149667
28596717017227338273714300125193836755515319447162976529780078148971487790319821
88519147113706991634634546145669268395700985294401943733041485320549175590426740
34376055257631453647013996141578816205226945882167913779577985755793070640280590
88488920257316919757992888222796598747399061809849093348573555554633208717494295
44429144879540630078900509249372759973792879832401077413460701742686305761355494
51725696332316233096424132629787724067443606625192514864611488915201308403944647
50402167878403958119211513737654364343272889716990374103843991215975681213659120
87965726714423273237468687426861913799539868695073624705150351784646192104683318
74813866025467134576495035178662403288015619622921383812609964490733284014730018
44780347826133407814725434678125931835111

95 25 апр 2018, 07:12 95 38786

>>38039 (OP)
Я принёс пи-функцию из 2015-го года:
pi(10^27) = 16,352,460,426,841,680,446,427,399
http://www.mersenneforum.org/showthread.php?t=20473
Значений больше - не вижу.
МОжно засунуть эти числа в исходник, чтоб быстрее дальше считать?
А то не очень хочется перебирать по-новой - столька многа цифар.

96 6 мая 2018, 01:21 96 39121

>>38773
>>38774
Для длинной последовательности простых чисел, можно записать их в виде разницы между текущим простым числом и предыдущим.
Разницу - записать не цифрами а байтами, и на каждое простое число, выражаемое в виде разницы - выделить
определённое число байт. По-сути, эта разница кодирует количество составных натуральных до очередного простого.
Для получения энного числа, нужно просуммировать все разницы до энного, и прибавить результат к первому простому,
записанному в виде числа.
Видно, что второе 4096-битное число отличается от первого, также, как отличается
411059 от 409601. 411059 - 409601 = 1458 = 10110110010(2) = 00000101 10110010 - и это два байта.
Таким образом, на запись каждого 4096-битного числа может уйти лишь два байта,
вместо записи всех цифр каждого числа.
2^4096 = 10^x; x = 1233, то есть 1233 байта/2 байта - сжатие в 616,5 раз.
К тому же, в длинном файле с последовательными простыми числами - многие числа могут повторяться,
что позволит ещё больше сжать файл - при помощи кода Хаффмана.

Ответы391223912339128

97 6 мая 2018, 01:28 97 39122

>>39121
>К тому же, в длинном файле с последовательными простыми числами - многие числа могут повторяться,
многие разницы между ними, хотел сказать.

Ответы3912339128

98 6 мая 2018, 01:33 98 39123

>>39121
>>39122
http://oeis.org/A001223

Ответы3912439128

99 6 мая 2018, 01:40 99 39124

>>39123
Там, кстати, есть функция Якобсталля для рассчета интервалов между простыми числами.

Ответы39128

100 6 мая 2018, 09:03 100 39128

>>39121
>>39122
>>39123
>>39124
И всё-же - хреновая идея. Первые 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,
и через каждый миллион - сумму миллиона предыдущих, чтоб ускорить рассчёт.
Тогда, можно будет прикрутить и корректирующие коды какие-нибудь, по контрольной сумме,
или восстанавливать целые блоки по этим суммам, если где-то повреждён хоть один бит.

101 28 мая 2018, 22:12 101 39916

>>38039 (OP)
Запхнул алгоритм Миллера-Рабина - в Javascript BigInteger, вот сюда:
https://github.com/username1565/BigInteger/commit/5bfea9f1f2db6dbd2933558dd26ab59e91a2921a
Теперь, можно в браузере, через эту HTML-страницу
https://github.com/username1565/BigInteger/blob/master/Miller-Rabin_test.html,
проверять на простоту - пиздатые числа и генерировать простые из них.
Для этого надо скачать BigInteger.js и эту страницу, закинуть их в одну папку, и открыть в браузере html-страницу.
В исходном коде - страницы можно также прописать любое число, числа, и цикл для проверки списка чисел.

Ответы41072

102 28 июня 2018, 22:02 102 41072

>>39916
Что вы тут, скучаете?
А я вам - немного факторизации, покушать принёс:
Я переписал ρ-метод факторизации Джона Полларда (с оптимизацией от Ричарда Брента).
Реализация на 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.

102 28 июня 2018, 22:02 102 41072

>>39916
Что вы тут, скучаете?
А я вам - немного факторизации, покушать принёс:
Я переписал ρ-метод факторизации Джона Полларда (с оптимизацией от Ричарда Брента).
Реализация на 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.

Показать весь текст
Ответы42048

103 10 авг 2018, 17:19 103 42024

>>38039 (OP)
Я вам тут 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/

Ответы42357

104 10 авг 2018, 22:12 104 42048

>>41072
Фу, погромист. Бвэээ

Ответы42055

105 11 авг 2018, 04:10 105 42055

>>42048
Это чё за блевотина?!! Аж самому тошнит. А ну-ка веник и савок в руки, и прибирай за собой.

Ответы42056

106 11 авг 2018, 04:12 106 42056

>>42055
Только веником по совку бливотину не размажь, лучше тряпкой размажь.

107 23 авг 2018, 02:17 107 42357

>>42024
>Скоро закончу генерацию списков простых чисел среди 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 для любой части, получить простое число по индексу, и начать с него перебор.
Задача рассчета хорошо параллелится таким образом, и можете заливать туда да хоть разные части.

107 23 авг 2018, 02:17 107 42357

>>42024
>Скоро закончу генерацию списков простых чисел среди 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 для любой части, получить простое число по индексу, и начать с него перебор.
Задача рассчета хорошо параллелится таким образом, и можете заливать туда да хоть разные части.

Показать весь текст
Ответы42368

108 23 авг 2018, 20:59 108 42368

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

Ответы423694237142379

109 23 авг 2018, 21:00 109 42369

>>42368
10300, то есть.

110 23 авг 2018, 21:23 110 42371

>>42368
Там за простое число из двух миллионов цифр дают миллион долларов, вот анон и готовится.

Алсо, было бы неплохо на основании этих чисел вывести какую никакую формулу для нахождения простых чисел. Это я так толсто набросил

Ответы42373

111 23 авг 2018, 22:17 111 42373

>>42371
>Там за простое число из двух миллионов цифр дают миллион долларов
Попахивает пиздежом. И не такие уже находили.
https://www.youtube.com/watch?v=tlpYjrbujG0

Ответы42379

112 24 авг 2018, 18:04 112 42379

>>42368
>Нахуя это нужно?
Чтоб по торрентам раздавать и 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% в природе, среди натуральных.
Они диффицитные, и ими можно торговать.
И тут - рассчёт простых чисел приравнивается к майнингу, лол.
Я уже представляю себе биржи простых чисел, и блокчейн на них.

>>42373
>Попахивает пиздежом.
Да так и есть, походу...
>Там за простое число из двух миллионов цифр дают миллион долларов, вот анон и готовится.
Где там? Смотри какие тут значения в столбце 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, а уж тем более - все натуральные.

Есть ещё алгоритм поиска энного простого числа по интегральному логарифму: >>38648
но он долго работает при значениях овер триллион.
Я думаю, что список последовательных простых чисел может помочь отметить опорные точки,
или создать массивы для ускорения работы программ, оперирующих простыми числами.

112 24 авг 2018, 18:04 112 42379

>>42368
>Нахуя это нужно?
Чтоб по торрентам раздавать и 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% в природе, среди натуральных.
Они диффицитные, и ими можно торговать.
И тут - рассчёт простых чисел приравнивается к майнингу, лол.
Я уже представляю себе биржи простых чисел, и блокчейн на них.

>>42373
>Попахивает пиздежом.
Да так и есть, походу...
>Там за простое число из двух миллионов цифр дают миллион долларов, вот анон и готовится.
Где там? Смотри какие тут значения в столбце 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, а уж тем более - все натуральные.

Есть ещё алгоритм поиска энного простого числа по интегральному логарифму: >>38648
но он долго работает при значениях овер триллион.
Я думаю, что список последовательных простых чисел может помочь отметить опорные точки,
или создать массивы для ускорения работы программ, оперирующих простыми числами.

Показать весь текст
Ответы42420

113 26 авг 2018, 01:35 113 42420

>>42379
>можно найти число по смещению, оффсету
Ну и какой там у простых чисел оффсет? Как обычно, четыре пробела?

Ответы42433

114 26 авг 2018, 15:39 114 42433

>>42420
Во-первых, я не затачивал списки под быстрый поиск 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 достаточно хорошо их жмёт.

115 29 авг 2018, 15:37 115 42580

>>38039 (OP)
Аноны, я тут при помощи 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. В течении недели программа должна рассчитать.

Ответы43114

116 14 сен 2018, 11:30 116 43114

>>42580
Заебало, короче, считать онион домен - 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 программа - она использует процессор.

116 14 сен 2018, 11:30 116 43114

>>42580
Заебало, короче, считать онион домен - 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 программа - она использует процессор.

Показать весь текст
Ответы43115

117 14 сен 2018, 11:33 117 43115

>>43114
Там где начинается и кончается спойлер - по два знака процента должно быть, в строке. Никогда не спойлерил процентами...

118 15 сен 2018, 05:12 118 43158

>>38039 (OP)
Аноны, смотрите какое число нашёл!
Вольфрам говорит что между в этом диапазоне лишь два простых числа:
http://www.wolframalpha.com/input/?i=primes[2999999999933,3000000000013]

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

На этом числе - стопорятся алгоритмы, они дают сдвиг.
Что в этом числе такого особенного? Как выдоить с него - зиллиард баксов?

Ответы43159

119 15 сен 2018, 07:11 119 43159

>>43158
>2999999999933
>2999999983949
>между числами 2999999999933 и 3000000000013 есть ещё одно
Завязывал бы ты с простыми, от них кукухой можно двинуться.
>>11687-кун

Ответы43203

120 16 сен 2018, 22:45 120 43203

>>43159
Оо, внатуре! Перегенерировал - и всё норм.
С третьего - по четвёртый триллион теперь считаю,
пока мы в параллель тут, из клопа - циклопа на сишке пилим:
Охуенно быстро генерирует.
Знакомьтесь Сlang - Consecutive Lists Of Primes: ttps://github.com/username1565/cyclop

Ответы4320443234

121 16 сен 2018, 22:46 121 43204

>>43203
>ttps
https://

122 17 сен 2018, 17:34 122 43234

>>43203
>Сlang - Consecutive Lists Of Prime
Почему не CLOP?

Ответы4325143252

123 18 сен 2018, 06:46 123 43251

>>43234
Я иконку с клопом не нашёл, и звучит как-то мерзко...

Ответы43265

124 18 сен 2018, 06:48 124 43252

>>43234
Я тут, у себя, диалог для ввода параметров написал, кстати.

29 Кб, 312x320
125 18 сен 2018, 15:11 125 43265

>>43251
>Я иконку с клопом не нашёл

Ответы4328143302

126 18 сен 2018, 19:06 126 43281

>>43265
Ну хочь - форкни, откомпиль, да сам повешай клопа своего. Я там батник сунул и описание компиляции.
У меня же - циклопом прога будет зваться. Он таким няшный на windows 8.1 в больших значках смотрится...

127 18 сен 2018, 23:39 127 43302

46 Кб, 500x525367 Кб, 500x52584 Кб, 256x256

>>43265
Нашёл тут, картинку получше, с бОльшим разрешением: 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... И главное - все они с прозрачным фоном!

Ответы433044330584012

128 18 сен 2018, 23:41 128 43304

>>43302
>получаю multi-icon ico-файл - пик4.
.ico - тип файла не поддерживается. Можете влить туда третью пикчу - получите эту же ico.

129 18 сен 2018, 23:51 129 43305

>>43302
>И главное - все они с прозрачным фоном!
Это годно, когда на рабочем столе заставка и когда перетаскиваешь файл.

130 31 мая 2021, 20:32 130 84001

Есть число 420599303587838138310567954368696889132078473300110593927087135329323325211067643992189
Надо разложить на простые множители
Известно:
1)Их два
2)Число вида (2p-1)(2q-1) где p и q простые

Число так же равно 8576682859183712660439494656457(2^185) + 60149540478113987615*(2^92) + 29235325
Мне кажется я близок хэлп

131 1 июня 2021, 09:04 131 84012

>>43302
Я уж думал анон с тараканами себе пикчи нашел, а это два пикчи двухлетние.

Ответы84023

132 1 июня 2021, 15:17 132 84023

>>84012
А смешно таки они так вывалились

Обновить тред
« /math/В начало тредаВеб-версияНастройки/a//b//mu//s//vg/Все доски

Скачать тред только с превьюс превью и прикрепленными файлами

Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах.Подробнее

Пользуетесь скринридером — пишите, что можно улучшить.
Host-Food.ru — надёжный хостинг от 12 руб/мес | Free DNS
Зеркала М.Двача: m2ch.hk, m2ch.lib, m2chfapiswfw2wcakptqp4o6ltgchvjuxfab7urxlduraomtlnhw5xad.onion