Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 10 ] 
Автор Сообщение
 Заголовок сообщения: Простой алгоритм получения простых чисел
СообщениеДобавлено: 05 фев 2021, 13:18 
Не в сети
Начинающий
Зарегистрирован:
19 апр 2015, 14:00
Сообщений: 32
Откуда: Краснодар
Cпасибо сказано: 0
Спасибо получено:
3 раз в 3 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Как известно, простые числа имеют вид (6К+1) либо (6К-1).
Однако числа такого вида содержат также составные числа.

Числа вида (6К+1) являются составными при условии, что
К=6ав+а+в
либо
К=6ав-а-в
где а и в натуральные числа. Получаем два разных набора значений К.

Числа вида (6К-1) являются составными при условии, что
К=6ав-а+в
или, что равнозначно
К=6ав+а-в
где а и в натуральные числа. Получаем два одинаковых набора для К.

Таким образом, список простых чисел (кроме чисел 2 и 3) можно получить,
если исключить из последовательности натуральных чисел значения К,
соответствующие составным числам. Отдельно для (6К+1) или (6К-1).
Проверил до простого числа 293, всё работает.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Простой алгоритм получения простых чисел
СообщениеДобавлено: 05 фев 2021, 14:26 
Не в сети
Последняя инстанция
Зарегистрирован:
14 июн 2011, 08:15
Сообщений: 3565
Cпасибо сказано: 50
Спасибо получено:
502 раз в 465 сообщениях
Очков репутации: 23

Добавить очки репутацииУменьшить очки репутации
Я взял [math]a=2,b=3[/math] и получил

[math]K_1=41, K_2=31[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Простой алгоритм получения простых чисел
СообщениеДобавлено: 05 фев 2021, 14:57 
Не в сети
Начинающий
Зарегистрирован:
19 апр 2015, 14:00
Сообщений: 32
Откуда: Краснодар
Cпасибо сказано: 0
Спасибо получено:
3 раз в 3 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
vorvalm
Замечательно!
Только надо получить набор всех значений К до выбранного.
Например, до 5.
Для (6К+1) и при условии К=6ав+а+в
Фиксируем а=1, прогоняем от в=1 до в=5
К=8;15;22;29;36
Далее фиксируем а=2, прогоняем от в=1 до в=5
К=15;28;41;54;67
Далее фиксируем а=3, прогоняем от в=1 до в=5
К=22;41;60;79;98
Далее фиксируем а=4, прогоняем от в=1 до в=5
К=29;54;79;104:129
Далее фиксируем а=5, прогоняем от в=1 до в=5
К=36;67;98;129;160
само собой повторы значений убираем

Таким же образом обсчитываем для (6К+1) и при условии К=6ав-а-в
Отдельно считаем набор значений для (6К-1).

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Простой алгоритм получения простых чисел
СообщениеДобавлено: 05 фев 2021, 17:28 
Не в сети
Последняя инстанция
Зарегистрирован:
14 июн 2011, 08:15
Сообщений: 3565
Cпасибо сказано: 50
Спасибо получено:
502 раз в 465 сообщениях
Очков репутации: 23

Добавить очки репутацииУменьшить очки репутации
В качестве примера приведите весь процесс определения составных чисел
хотя бы до 100.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Простой алгоритм получения простых чисел
СообщениеДобавлено: 05 фев 2021, 17:46 
Не в сети
Начинающий
Зарегистрирован:
19 апр 2015, 14:00
Сообщений: 32
Откуда: Краснодар
Cпасибо сказано: 0
Спасибо получено:
3 раз в 3 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
vorvalm
Ок. Это будет наилучший вариант. Но мне необходимо время, чтобы всё подробно изложить. Не берусь сказать сколько...

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Простой алгоритм получения простых чисел
СообщениеДобавлено: 05 фев 2021, 19:09 
Не в сети
Последняя инстанция
Зарегистрирован:
14 июн 2011, 08:15
Сообщений: 3565
Cпасибо сказано: 50
Спасибо получено:
502 раз в 465 сообщениях
Очков репутации: 23

Добавить очки репутацииУменьшить очки репутации
Vova_X
Торопиться не надо. Сделайте все по порядку.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: определения составных чисел до 100
СообщениеДобавлено: 05 фев 2021, 21:25 
Не в сети
Начинающий
Зарегистрирован:
19 апр 2015, 14:00
Сообщений: 32
Откуда: Краснодар
Cпасибо сказано: 0
Спасибо получено:
3 раз в 3 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Вот, вроде бы ничего не упустил.
Извиняюсь за оформление...
при составлении таблиц пользовался экселем
====================
определения составных чисел до 100
(и соответственно оставшихся простых)
===================================
Числа вида (6К+1) являются составными при условии, что
К=6ав+а+в
и
К=6ав-а-в

1. Строим таблицу для К=6ав+а+в
(с Генератором таблиц не смог разобраться, вставляю как есть...)

1 2 3 4 в
1 8 15 22 29
2 15 28 41 54
3 22 41 60 79
4 29 54 79 104
5 36 67 98 129
6 43 80 117 154
7 50 93 136 179
8 57 106 155 204
9 64 119 174 229
10 71 132 193 254
11 78 145 212 279
12 85 158 231 304
13 92 171 250 329
14 99 184 269 354
15 106 197 288 379
а

По условию нас интересуют значения К не превышающие 100,
поэтому удаляем значения превышающие 100. Кроме того,
замечаем, что таблица симметрична относительно диагонали.
Удаляем элементы над диагональю. Оставшиеся значения:

1 2 3 4 в
1 8
2 15 28
3 22 41 60
4 29 54 79
5 36 67 98
6 43 80
7 50 93
8 57
9 64
10 71
11 78
12 85
13 92
14 99
15
а

2. Строим таблицу для К=6ав-а-в

1 2 3 4 5 в
1 4 9 14 19 24
2 9 20 31 42 53
3 14 31 48 65 82
4 19 42 65 88 111
5 24 53 82 111 140
6 29 64 99 134 169
7 34 75 116 157 198
8 39 86 133 180 227
9 44 97 150 203 256
10 49 108 167 226 285
11 54 119 184 249 314
12 59 130 201 272 343
13 64 141 218 295 372
14 69 152 235 318 401
15 74 163 252 341 430
16 79 174 269 364 459
17 84 185 286 387 488
18 89 196 303 410 517
19 94 207 320 433 546
20 99 218 337 456 575
21 104 229 354 479 604
а

Аналогично удаляем значения превышающие 100 и элементы
над диагональю, так как таблица относительно диагонали симметрична.
Оставшиеся значения:

1 2 3 4 5 в
1 4
2 9 20
3 14 31 48
4 19 42 65 88
5 24 53 82
6 29 64 99
7 34 75
8 39 86
9 44 97
10 49
11 54
12 59
13 64
14 69
15 74
16 79
17 84
18 89
19 94
20 99
21
а

3. Составляем общий список оставшихся значений из обеих таблиц,
удаляем дубликаты и сортируем:

4
8
9
14
15
19
20
22
24
28
29
31
34
36
39
41
42
43
44
48
49
50
53
54
57
59
60
64
65
67
69
71
74
75
78
79
80
82
84
85
86
88
89
92
93
94
97
98
99

Полученный список значений для К определяет все
составные числа вида (6К+1). Если из натуральных чисел от 1 до 100
удалить полученные значения, то останутся только К соответствующие
простым числам вида (6К+1).
Вот эти значения после удаления и соответствующие им простые числа:

К 6К+1
1 7
2 13
3 19
5 31
6 37
7 43
10 61
11 67
12 73
13 79
16 97
17 103
18 109
21 127
23 139
25 151
26 157
27 163
30 181
32 193
33 199
35 211
37 223
38 229
40 241
45 271
46 277
47 283
51 307
52 313
55 331
56 337
58 349
61 367
62 373
63 379
66 397
68 409
70 421
72 433
73 439
76 457
77 463
81 487
83 499
87 523
90 541
91 547
95 571
96 577
100 601

4. Числа вида (6К-1) являются составными при условии, что
К=6ав-а+в

(Замечание: формулы
К=6ав-а+в
и
К=6ав+а-в
дают транспонированные таблицы одинаковых значений)

Строим таблицу для К=6ав-а+в

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 в
1 6 13 20 27 34 41 48 55 62 69 76 83 90 97 104
2 11 24 37 50 63 76 89 102 115 128 141 154 167 180 193
3 16 35 54 73 92 111 130 149 168 187 206 225 244 263 282
4 21 46 71 96 121 146 171 196 221 246 271 296 321 346 371
5 26 57 88 119 150 181 212 243 274 305 336 367 398 429 460
6 31 68 105 142 179 216 253 290 327 364 401 438 475 512 549
7 36 79 122 165 208 251 294 337 380 423 466 509 552 595 638
8 41 90 139 188 237 286 335 384 433 482 531 580 629 678 727
9 46 101 156 211 266 321 376 431 486 541 596 651 706 761 816
10 51 112 173 234 295 356 417 478 539 600 661 722 783 844 905
11 56 123 190 257 324 391 458 525 592 659 726 793 860 927 994
12 61 134 207 280 353 426 499 572 645 718 791 864 937 1010
13 66 145 224 303 382 461 540 619 698 777 856 935 1014
14 71 156 241 326 411 496 581 666 751 836 921 1006
15 76 167 258 349 440 531 622 713 804 895 986
16 81 178 275 372 469 566 663 760 857 954
17 86 189 292 395 498 601 704 807 910
18 91 200 309 418 527 636 745 854 963
19 96 211 326 441 556 671 786 901
20 101 222 343 464 585 706 827 948
а


Удаляем значения К превышающие 100, получаем

1 2 3 4 5 6 7 8 9 10 11 12 13 14 в
1 6 13 20 27 34 41 48 55 62 69 76 83 90 97
2 11 24 37 50 63 76 89
3 16 35 54 73 92
4 21 46 71 96
5 26 57 88
6 31 68
7 36 79
8 41 90
9 46
10 51
11 56
12 61
13 66
14 71
15 76
16 81
17 86
18 91
19 96
а

Сортируем, удаляем дубликаты, получаем список значений К
для составных чисел вида (6К-1):

6
11
13
16
20
21
24
26
27
31
34
35
36
37
41
46
48
50
51
54
55
56
57
61
62
63
66
68
69
71
73
76
79
81
83
86
88
89
90
91
92
96
97

Из натуральных чисел от 1 до 100
удаляем полученные значения. Останутся только значения К
соответствующие простым числам вида (6К-1).
Вот эти значения и соответствующие им простые числа:

К 6К-1
1 5
2 11
3 17
4 23
5 29
7 41
8 47
9 53
10 59
12 71
14 83
15 89
17 101
18 107
19 113
22 131
23 137
25 149
28 167
29 173
30 179
32 191
33 197
38 227
39 233
40 239
42 251
43 257
44 263
45 269
47 281
49 293
52 311
53 317
58 347
59 353
60 359
64 383
65 389
67 401
70 419
72 431
74 443
75 449
77 461
78 467
80 479
82 491
84 503
85 509
87 521
93 557
94 563
95 569
98 587
99 593
100 599

Объединяем оба списка простых чисел вида (6К+1) и вида (6К-1) в один для
возможности сравнения со стандартным списком:
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
101
103
107
109
113
127
131
137
139
149
151
157
163
167
173
179
181
191
193
197
199
211
223
227
229
233
239
241
251
257
263
269
271
277
281
283
293
307
311
313
317
331
337
347
349
353
359
367
373
379
383
389
397
401
409
419
421
431
433
439
443
449
457
461
463
467
479
487
491
499
503
509
521
523
541
547
557
563
569
571
577
587
593
599
601

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Простой алгоритм получения простых чисел
СообщениеДобавлено: 06 фев 2021, 10:25 
Не в сети
Начинающий
Зарегистрирован:
19 апр 2015, 14:00
Сообщений: 32
Откуда: Краснодар
Cпасибо сказано: 0
Спасибо получено:
3 раз в 3 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
здесь первая по счету таблица из предыдущего сообщения
числа вида 6К+1
таблица значений К=6ав+а+в

1234в
18152229
215284154
322416079
4295479104
5366798129
64380117154
75093136179
857106155204
964119174229
1071132193254
1178145212279
1285158231304
1392171250329
1499184269354
15106197288379
а


Как видно из таблицы, её столбцы и строки представляют собой арифметические прогрессии.
Первый член прогрессии равен (7х+1), а шаг (6х+1) где х номер столбца или строки.
Значения К для чисел вида (6К+1) соответствующие простым числам это остаточные значения, которые
не вошли в эти прогрессии. Это к вопросу поиска закономерностей распределения простых чисел.

Аналогично имеем для вида (6К+1) и К=6ав-а-в первый член (5х-1) и шаг (6х-1).

Для вида (6К-1) и К=6ав-а+в первый член (5х+1) и шаг (6х+1),
либо первый член (7х-1) и шаг (6х-1) в зависимости от того строки это или столбцы.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Простой алгоритм получения простых чисел
СообщениеДобавлено: 06 фев 2021, 13:34 
Не в сети
Последняя инстанция
Зарегистрирован:
14 июн 2011, 08:15
Сообщений: 3565
Cпасибо сказано: 50
Спасибо получено:
502 раз в 465 сообщениях
Очков репутации: 23

Добавить очки репутацииУменьшить очки репутации
Vova_X
Извините, но я не вижу преимущество вашего метода
по сравнению с элементарным решетом Эратосфена.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Дополнение - получение выражений для К
СообщениеДобавлено: 06 фев 2021, 14:25 
Не в сети
Начинающий
Зарегистрирован:
19 апр 2015, 14:00
Сообщений: 32
Откуда: Краснодар
Cпасибо сказано: 0
Спасибо получено:
3 раз в 3 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Дополнение - получение выражений для К
=============
Пусть С=6К+1
и
С=(6а-1)(6в-1)
тогда
6К+1=(6а-1)(6в-1)
6К+1=36ав-6а-6в+1
6К=36ав-6а-6в
К=6ав-а-в
============== и аналогично:
С=6К+1
С=(6а+1)(6в+1)
6К+1=(6а+1)(6в+1)
6К+1=36ав+6а+6в+1
6К=36ав+6а+6в
К=6ав+а+в
==============
С=6К-1
С=(6а-1)(6в+1)
6К-1=(6а-1)(6в+1)
6К-1=36ав+6а-6в-1
6К=36ав+6а-6в
К=6ав+а-в
===============
С=6К-1
С=(6а+1)(6в-1)
6К-1=(6а+1)(6в-1)
6К-1=36ав-6а+6в-1
6К=36ав-6а+6в
К=6ав-а+в
===============

Было бы интересно получить явную зависимость для вычисления
значений а и в по заданному К. Может быть у кого-то есть мысли на этот счёт?

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 10 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Простой но сложный тест простых чисел

в форуме Теория чисел

satvaldyev

6

232

15 июл 2023, 20:22

Алгоритм простых чисел и не кратных 2-3-5-11. в спирали

в форуме Размышления по поводу и без

ammo77

1

172

14 фев 2020, 16:37

Множество простых чисел и пар простых чисел-близнецов бескон

в форуме Размышления по поводу и без

korolchukvasily

2

257

28 июн 2023, 11:23

Простой житейский смысл комплексных чисел

в форуме Размышления по поводу и без

Sln345

142

1853

21 окт 2021, 19:51

Свойства простых чисел

в форуме Палата №6

Galina Alexandrovna

13

1569

21 июл 2016, 07:14

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

в форуме Теория чисел

Claudia

5

591

18 июн 2018, 13:13

Анализ простых чисел

в форуме Теория чисел

Nozdre

18

1149

20 май 2019, 23:01

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

в форуме Задачи со школьных и студенческих олимпиад

Xenia1996

3

380

13 ноя 2019, 00:07

Задача для простых чисел

в форуме Размышления по поводу и без

ammo77

0

253

18 мар 2020, 23:19

Закономерность простых чисел

в форуме Размышления по поводу и без

ammo77

0

265

11 мар 2020, 01:42


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 15


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved