В теории чисел много проблем, формулировка которых понятна школьнику, но решение не поддавалось или не поддаётся до сих пор многим поколениям математиков. Значительная часть таких проблем связана с распределением простых чисел в натуральном ряду. Эта статья – отчаянная попытка изложить полученные мной скромные результаты таким образом, чтобы они были занятны и понятны как для тех, кто смыслит в теории чисел не более бельмеса, так и для скушавших не одну собаку в этой области.
Для первой категории читателей необходимо введение, достаточно краткое, дабы не усыпить вторую категорию. Простым называется число, имеющее ровно два различных делителя – единицу и само это число. Остальные натуральные числа, кроме единицы, называются составными. Первые простые числа 2, 3, 5, 7, 11, 13, 17, 19 …
Число 6 составное, делится на 1, 2, 3, 6. Составными являются числа 8 и 9. Делители числа 8 – 1, 2, 4, 8. Делители числа 9 – 1, 3, 9. С древних времён для нахождения простых чисел применяется так называемое решето Эратосфена.
Представим себе для наглядности бесконечный ряд столбиков. На каждом из столбиков висит табличка с порядковым номером. Это картина натурального ряда 1; 2; 3; 4; 5; 6;….
От первого столбика идёт маляр, встречает табличку «2», и начинает красить после него каждый второй столбик, т.е. «4»; «6»; «8»;…..
Затем за дело берётся второй маляр. Он отправляется от второго столбика, за ним встречает номер «3» и начинает после него красить каждый третий столбик – «6»; «9»; «12»;…..
Продолжим мысленно этот процесс. У нас получится колонна маляров идущих друг за другом. Маляр №k находит k-й не крашенный столбик и, прочитав на нем порядковый номер, который мы обозначим буквой n, начинает после этого столбика красить каждый n-й. Малярам категорически запрещено обгонять впереди идущих, но уже окрашенные столбики разрешается не красить. В результате бесконечного процесса, или процессии маляров, некрашеными останутся столбики, номера которых – простые числа. Исключение составит первый столбик. Единицу не называют простым числом в приличном обществе. Но, думаю, возражений не последует, если назвать её сверхпростым числом.
Это возмутительно наглядное представление о решете Эратосфена позволяет, тем не менее, ярче высветить недостатки этого алгоритма и наметить пути его совершенствования. Более всего в нарисованной картине поражает вопиющее неравенство. Первый маляр неустанно машет кистью, красит каждый второй столбик. Но, если мы посмотрим на работу, к примеру, десятого, то ему вменяется в обязанность красить лишь каждый 29-й столбик. Да и тут этот лентяй наверняка воспользуется разрешением не красить уже покрашенное и не станет красить 58-й и 87-й столбики. Неискушенные, но любопытные читатели смогут сами подсчитать, с какого столбика наш маляр начнет работать кистью. Для того, чтобы устранить дискриминацию, оправдана попытка постепенно выводить из процесса тех, кто раньше других вступил в него.
Далее я буду строг, но справедлив. Постараюсь придерживаться строгих определений и доказательств, не перегружая читателей доказательством слишком простых и известных фактов.
Расположим натуральные числа в два ряда, заполняя таблицу из двух строк в порядке сверху вниз, слева направо. Число столбцов пока не будем уточнять, считая его достаточно большим.
1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 |
2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 | 18 | 20 | 22 | 24 | 26 |
Таблица А\1\
Во втором ряду собрались чётные числа. Запомнив первое число строки, как первое простое число, вычеркнем эту строку. Далее будем рассматривать и «просеивать» через решето только оставшиеся нечётные числа. Расположим их в новую таблицу из трёх строк. Порядок заполнения по-прежнему сверху вниз, слева направо.
1 | 7 | 13 | 19 | 25 | 31 | 37 | 43 | 49 | 55 | 61 | 67 | 73 | 79 | 85 |
3 | 9 | 15 | 21 | 27 | 33 | 39 | 45 | 51 | 57 | 63 | 69 | 75 | 81 | 87 |
5 | 11 | 17 | 23 | 29 | 35 | 41 | 47 | 53 | 59 | 65 | 71 | 77 | 83 | 89 |
Таблица А\2\
Во втором ряду вновь оказались числа с общим делителем. На этот раз делитель – следующее простое число 3. Вновь запомним первое число строки и вычеркнем всю строку, получив новую таблицу.
1 | 7 | 13 | 19 | 25 | 31 | 37 | 43 | 49 | 55 | 61 | 67 | 73 | 79 | 85 |
5 | 11 | 17 | 23 | 29 | 35 | 41 | 47 | 53 | 59 | 65 | 71 | 77 | 83 | 89 |
Таблица Б\2\
Читателей, уверовавших в вечную масленицу для кота, ожидает лёгкое разочарование. Если оставшиеся числа перенести в новую таблицу из пяти строк, строки состоящей из чисел, кратных 5 в новой таблице не найдётся. Поспешу утешить таких читателей. Перенесём в каждый столбец новой таблицы числа из пяти столбцов предыдущей. При переносе продолжаем сохранять порядок заполнения.
1 | 31 | 61 | 91 | 121 | 151 | 181 | 211 | 241 | 271 | 301 | 331 | 361 | 391 | 421 | 451 | 481 | 511 | 541 | 571 | 601 | 631 | 661 | 691 | 721 | 751 | 781 | 811 | 841 |
5 | 35 | 65 | 95 | 125 | 155 | 185 | 215 | 245 | 275 | 305 | 335 | 365 | 395 | 425 | 455 | 485 | 515 | 545 | 575 | 605 | 635 | 665 | 695 | 725 | 755 | 785 | 815 | 845 |
7 | 37 | 67 | 97 | 127 | 157 | 187 | 217 | 247 | 277 | 307 | 337 | 367 | 397 | 427 | 457 | 487 | 517 | 547 | 577 | 607 | 637 | 667 | 697 | 727 | 757 | 787 | 817 | 847 |
11 | 41 | 71 | 101 | 131 | 161 | 191 | 221 | 251 | 281 | 311 | 341 | 371 | 401 | 431 | 461 | 491 | 521 | 551 | 581 | 611 | 641 | 671 | 701 | 731 | 761 | 791 | 821 | 851 |
13 | 43 | 73 | 103 | 133 | 163 | 193 | 223 | 253 | 283 | 313 | 343 | 373 | 403 | 433 | 463 | 493 | 523 | 553 | 583 | 613 | 643 | 673 | 703 | 733 | 763 | 793 | 823 | 853 |
17 | 47 | 77 | 107 | 137 | 167 | 197 | 227 | 257 | 287 | 317 | 347 | 377 | 407 | 437 | 467 | 497 | 527 | 557 | 587 | 617 | 647 | 677 | 707 | 737 | 767 | 797 | 827 | 857 |
19 | 49 | 79 | 109 | 139 | 169 | 199 | 229 | 259 | 289 | 319 | 349 | 379 | 409 | 439 | 469 | 499 | 529 | 559 | 589 | 619 | 649 | 679 | 709 | 739 | 769 | 799 | 829 | 859 |
23 | 53 | 83 | 113 | 143 | 173 | 203 | 233 | 263 | 293 | 323 | 353 | 383 | 413 | 443 | 473 | 503 | 533 | 563 | 593 | 623 | 653 | 683 | 713 | 743 | 773 | 803 | 833 | 863 |
25 | 55 | 85 | 115 | 145 | 175 | 205 | 235 | 265 | 295 | 325 | 355 | 385 | 415 | 445 | 475 | 505 | 535 | 565 | 595 | 625 | 655 | 685 | 715 | 745 | 775 | 805 | 835 | 865 |
29 | 59 | 89 | 119 | 149 | 179 | 209 | 239 | 269 | 299 | 329 | 359 | 389 | 419 | 449 | 479 | 509 | 539 | 569 | 599 | 629 | 659 | 689 | 719 | 749 | 779 | 809 | 839 | 869 |
Таблица А\3\
О, радость! Числа, кратные 5 собрались теперь уже в две строки – вторую и девятую, предпоследнюю. Несложные размышления приводят нас к выводу, что особого чуда не произошло. Строки таблицы Б\2\ представляют из себя арифметические прогрессии с разностью 6. Поскольку на каждый столбец таблицы А\3\ пошло ровно 5 столбцов таблицы Б\2\, и брались они по порядку, каждая строка таблицы А\3\ представляет из себя арифметическую прогрессию с разностью равной 5*6=30. В первом столбце два числа делятся на 5 – второе и девятое. При сложении любого натурального числа с числом 30, кратным 5, полученная сумма будет иметь тот же остаток от деления на 5, что исходное число. Поэтому все числа кратные 5 расположились во второй и девятой строках. Удалим их, предварительно записав 5 в качестве очередного простого числа
1 | 31 | 61 | 91 | 121 | 151 | 181 | 211 | 241 | 271 | 301 | 331 | 361 | 391 | 421 | 451 | 481 | 511 | 541 | 571 | 601 | 631 | 661 | 691 | 721 | 751 | 781 | 811 | 841 |
7 | 37 | 67 | 97 | 127 | 157 | 187 | 217 | 247 | 277 | 307 | 337 | 367 | 397 | 427 | 457 | 487 | 517 | 547 | 577 | 607 | 637 | 667 | 697 | 727 | 757 | 787 | 817 | 847 |
11 | 41 | 71 | 101 | 131 | 161 | 191 | 221 | 251 | 281 | 311 | 341 | 371 | 401 | 431 | 461 | 491 | 521 | 551 | 581 | 611 | 641 | 671 | 701 | 731 | 761 | 791 | 821 | 851 |
13 | 43 | 73 | 103 | 133 | 163 | 193 | 223 | 253 | 283 | 313 | 343 | 373 | 403 | 433 | 463 | 493 | 523 | 553 | 583 | 613 | 643 | 673 | 703 | 733 | 763 | 793 | 823 | 853 |
17 | 47 | 77 | 107 | 137 | 167 | 197 | 227 | 257 | 287 | 317 | 347 | 377 | 407 | 437 | 467 | 497 | 527 | 557 | 587 | 617 | 647 | 677 | 707 | 737 | 767 | 797 | 827 | 857 |
19 | 49 | 79 | 109 | 139 | 169 | 199 | 229 | 259 | 289 | 319 | 349 | 379 | 409 | 439 | 469 | 499 | 529 | 559 | 589 | 619 | 649 | 679 | 709 | 739 | 769 | 799 | 829 | 859 |
23 | 53 | 83 | 113 | 143 | 173 | 203 | 233 | 263 | 293 | 323 | 353 | 383 | 413 | 443 | 473 | 503 | 533 | 563 | 593 | 623 | 653 | 683 | 713 | 743 | 773 | 803 | 833 | 863 |
29 | 59 | 89 | 119 | 149 | 179 | 209 | 239 | 269 | 299 | 329 | 359 | 389 | 419 | 449 | 479 | 509 | 539 | 569 | 599 | 629 | 659 | 689 | 719 | 749 | 779 | 809 | 839 | 869 |
Таблица Б\3\
Перейдём к общему описанию алгоритма поиска простых чисел. Предположим, что построена таблица Б\k\, в которую записаны все числа, не делящиеся нацело на первые простые числа p1, p2, … pk. Так в таблице Б\3\ входящие в неё числа не делятся на 2, 3, 5. Общий принцип построения по таблице Б\k\ таблиц А\k+1\ и Б\k+1\, а также свойства этих таблиц можно на примере таблиц Б\3\, А\4\ и Б\4\. Знаком обратного слеша будут выделяться номера таблиц и указываться соответствие параметров таблицам с этими номерами.
1 | 211 | 421 | 631 | 841 | 1051 | 1261 | 1471 | 1681 | 1891 | 2101 | 2311 | 2521 | 2731 | 2941 | 3151 | 3361 | 3571 | 3781 | 3991 | 4201 | 4411 | 4621 | 4831 |
7 | 217 | 427 | 637 | 847 | 1057 | 1267 | 1477 | 1687 | 1897 | 2107 | 2317 | 2527 | 2737 | 2947 | 3157 | 3367 | 3577 | 3787 | 3997 | 4207 | 4417 | 4627 | 4837 |
11 | 221 | 431 | 641 | 851 | 1061 | 1271 | 1481 | 1691 | 1901 | 2111 | 2321 | 2531 | 2741 | 2951 | 3161 | 3371 | 3581 | 3791 | 4001 | 4211 | 4421 | 4631 | 4841 |
13 | 223 | 433 | 643 | 853 | 1063 | 1273 | 1483 | 1693 | 1903 | 2113 | 2323 | 2533 | 2743 | 2953 | 3163 | 3373 | 3583 | 3793 | 4003 | 4213 | 4423 | 4633 | 4843 |
17 | 227 | 437 | 647 | 857 | 1067 | 1277 | 1487 | 1697 | 1907 | 2117 | 2327 | 2537 | 2747 | 2957 | 3167 | 3377 | 3587 | 3797 | 4007 | 4217 | 4427 | 4637 | 4847 |
19 | 229 | 439 | 649 | 859 | 1069 | 1279 | 1489 | 1699 | 1909 | 2119 | 2329 | 2539 | 2749 | 2959 | 3169 | 3379 | 3589 | 3799 | 4009 | 4219 | 4429 | 4639 | 4849 |
23 | 233 | 443 | 653 | 863 | 1073 | 1283 | 1493 | 1703 | 1913 | 2123 | 2333 | 2543 | 2753 | 2963 | 3173 | 3383 | 3593 | 3803 | 4013 | 4223 | 4433 | 4643 | 4853 |
29 | 239 | 449 | 659 | 869 | 1079 | 1289 | 1499 | 1709 | 1919 | 2129 | 2339 | 2549 | 2759 | 2969 | 3179 | 3389 | 3599 | 3809 | 4019 | 4229 | 4439 | 4649 | 4859 |
31 | 241 | 451 | 661 | 871 | 1081 | 1291 | 1501 | 1711 | 1921 | 2131 | 2341 | 2551 | 2761 | 2971 | 3181 | 3391 | 3601 | 3811 | 4021 | 4231 | 4441 | 4651 | 4861 |
37 | 247 | 457 | 667 | 877 | 1087 | 1297 | 1507 | 1717 | 1927 | 2137 | 2347 | 2557 | 2767 | 2977 | 3187 | 3397 | 3607 | 3817 | 4027 | 4237 | 4447 | 4657 | 4867 |
41 | 251 | 461 | 671 | 881 | 1091 | 1301 | 1511 | 1721 | 1931 | 2141 | 2351 | 2561 | 2771 | 2981 | 3191 | 3401 | 3611 | 3821 | 4031 | 4241 | 4451 | 4661 | 4871 |
43 | 253 | 463 | 673 | 883 | 1093 | 1303 | 1513 | 1723 | 1933 | 2143 | 2353 | 2563 | 2773 | 2983 | 3193 | 3403 | 3613 | 3823 | 4033 | 4243 | 4453 | 4663 | 4873 |
47 | 257 | 467 | 677 | 887 | 1097 | 1307 | 1517 | 1727 | 1937 | 2147 | 2357 | 2567 | 2777 | 2987 | 3197 | 3407 | 3617 | 3827 | 4037 | 4247 | 4457 | 4667 | 4877 |
49 | 259 | 469 | 679 | 889 | 1099 | 1309 | 1519 | 1729 | 1939 | 2149 | 2359 | 2569 | 2779 | 2989 | 3199 | 3409 | 3619 | 3829 | 4039 | 4249 | 4459 | 4669 | 4879 |
53 | 263 | 473 | 683 | 893 | 1103 | 1313 | 1523 | 1733 | 1943 | 2153 | 2363 | 2573 | 2783 | 2993 | 3203 | 3413 | 3623 | 3833 | 4043 | 4253 | 4463 | 4673 | 4883 |
59 | 269 | 479 | 689 | 899 | 1109 | 1319 | 1529 | 1739 | 1949 | 2159 | 2369 | 2579 | 2789 | 2999 | 3209 | 3419 | 3629 | 3839 | 4049 | 4259 | 4469 | 4679 | 4889 |
61 | 271 | 481 | 691 | 901 | 1111 | 1321 | 1531 | 1741 | 1951 | 2161 | 2371 | 2581 | 2791 | 3001 | 3211 | 3421 | 3631 | 3841 | 4051 | 4261 | 4471 | 4681 | 4891 |
67 | 277 | 487 | 697 | 907 | 1117 | 1327 | 1537 | 1747 | 1957 | 2167 | 2377 | 2587 | 2797 | 3007 | 3217 | 3427 | 3637 | 3847 | 4057 | 4267 | 4477 | 4687 | 4897 |
71 | 281 | 491 | 701 | 911 | 1121 | 1331 | 1541 | 1751 | 1961 | 2171 | 2381 | 2591 | 2801 | 3011 | 3221 | 3431 | 3641 | 3851 | 4061 | 4271 | 4481 | 4691 | 4901 |
73 | 283 | 493 | 703 | 913 | 1123 | 1333 | 1543 | 1753 | 1963 | 2173 | 2383 | 2593 | 2803 | 3013 | 3223 | 3433 | 3643 | 3853 | 4063 | 4273 | 4483 | 4693 | 4903 |
77 | 287 | 497 | 707 | 917 | 1127 | 1337 | 1547 | 1757 | 1967 | 2177 | 2387 | 2597 | 2807 | 3017 | 3227 | 3437 | 3647 | 3857 | 4067 | 4277 | 4487 | 4697 | 4907 |
79 | 289 | 499 | 709 | 919 | 1129 | 1339 | 1549 | 1759 | 1969 | 2179 | 2389 | 2599 | 2809 | 3019 | 3229 | 3439 | 3649 | 3859 | 4069 | 4279 | 4489 | 4699 | 4909 |
83 | 293 | 503 | 713 | 923 | 1133 | 1343 | 1553 | 1763 | 1973 | 2183 | 2393 | 2603 | 2813 | 3023 | 3233 | 3443 | 3653 | 3863 | 4073 | 4283 | 4493 | 4703 | 4913 |
89 | 299 | 509 | 719 | 929 | 1139 | 1349 | 1559 | 1769 | 1979 | 2189 | 2399 | 2609 | 2819 | 3029 | 3239 | 3449 | 3659 | 3869 | 4079 | 4289 | 4499 | 4709 | 4919 |
91 | 301 | 511 | 721 | 931 | 1141 | 1351 | 1561 | 1771 | 1981 | 2191 | 2401 | 2611 | 2821 | 3031 | 3241 | 3451 | 3661 | 3871 | 4081 | 4291 | 4501 | 4711 | 4921 |
97 | 307 | 517 | 727 | 937 | 1147 | 1357 | 1567 | 1777 | 1987 | 2197 | 2407 | 2617 | 2827 | 3037 | 3247 | 3457 | 3667 | 3877 | 4087 | 4297 | 4507 | 4717 | 4927 |
101 | 311 | 521 | 731 | 941 | 1151 | 1361 | 1571 | 1781 | 1991 | 2201 | 2411 | 2621 | 2831 | 3041 | 3251 | 3461 | 3671 | 3881 | 4091 | 4301 | 4511 | 4721 | 4931 |
103 | 313 | 523 | 733 | 943 | 1153 | 1363 | 1573 | 1783 | 1993 | 2203 | 2413 | 2623 | 2833 | 3043 | 3253 | 3463 | 3673 | 3883 | 4093 | 4303 | 4513 | 4723 | 4933 |
107 | 317 | 527 | 737 | 947 | 1157 | 1367 | 1577 | 1787 | 1997 | 2207 | 2417 | 2627 | 2837 | 3047 | 3257 | 3467 | 3677 | 3887 | 4097 | 4307 | 4517 | 4727 | 4937 |
109 | 319 | 529 | 739 | 949 | 1159 | 1369 | 1579 | 1789 | 1999 | 2209 | 2419 | 2629 | 2839 | 3049 | 3259 | 3469 | 3679 | 3889 | 4099 | 4309 | 4519 | 4729 | 4939 |
113 | 323 | 533 | 743 | 953 | 1163 | 1373 | 1583 | 1793 | 2003 | 2213 | 2423 | 2633 | 2843 | 3053 | 3263 | 3473 | 3683 | 3893 | 4103 | 4313 | 4523 | 4733 | 4943 |
119 | 329 | 539 | 749 | 959 | 1169 | 1379 | 1589 | 1799 | 2009 | 2219 | 2429 | 2639 | 2849 | 3059 | 3269 | 3479 | 3689 | 3899 | 4109 | 4319 | 4529 | 4739 | 4949 |
121 | 331 | 541 | 751 | 961 | 1171 | 1381 | 1591 | 1801 | 2011 | 2221 | 2431 | 2641 | 2851 | 3061 | 3271 | 3481 | 3691 | 3901 | 4111 | 4321 | 4531 | 4741 | 4951 |
127 | 337 | 547 | 757 | 967 | 1177 | 1387 | 1597 | 1807 | 2017 | 2227 | 2437 | 2647 | 2857 | 3067 | 3277 | 3487 | 3697 | 3907 | 4117 | 4327 | 4537 | 4747 | 4957 |
131 | 341 | 551 | 761 | 971 | 1181 | 1391 | 1601 | 1811 | 2021 | 2231 | 2441 | 2651 | 2861 | 3071 | 3281 | 3491 | 3701 | 3911 | 4121 | 4331 | 4541 | 4751 | 4961 |
133 | 343 | 553 | 763 | 973 | 1183 | 1393 | 1603 | 1813 | 2023 | 2233 | 2443 | 2653 | 2863 | 3073 | 3283 | 3493 | 3703 | 3913 | 4123 | 4333 | 4543 | 4753 | 4963 |
137 | 347 | 557 | 767 | 977 | 1187 | 1397 | 1607 | 1817 | 2027 | 2237 | 2447 | 2657 | 2867 | 3077 | 3287 | 3497 | 3707 | 3917 | 4127 | 4337 | 4547 | 4757 | 4967 |
139 | 349 | 559 | 769 | 979 | 1189 | 1399 | 1609 | 1819 | 2029 | 2239 | 2449 | 2659 | 2869 | 3079 | 3289 | 3499 | 3709 | 3919 | 4129 | 4339 | 4549 | 4759 | 4969 |
143 | 353 | 563 | 773 | 983 | 1193 | 1403 | 1613 | 1823 | 2033 | 2243 | 2453 | 2663 | 2873 | 3083 | 3293 | 3503 | 3713 | 3923 | 4133 | 4343 | 4553 | 4763 | 4973 |
149 | 359 | 569 | 779 | 989 | 1199 | 1409 | 1619 | 1829 | 2039 | 2249 | 2459 | 2669 | 2879 | 3089 | 3299 | 3509 | 3719 | 3929 | 4139 | 4349 | 4559 | 4769 | 4979 |
151 | 361 | 571 | 781 | 991 | 1201 | 1411 | 1621 | 1831 | 2041 | 2251 | 2461 | 2671 | 2881 | 3091 | 3301 | 3511 | 3721 | 3931 | 4141 | 4351 | 4561 | 4771 | 4981 |
157 | 367 | 577 | 787 | 997 | 1207 | 1417 | 1627 | 1837 | 2047 | 2257 | 2467 | 2677 | 2887 | 3097 | 3307 | 3517 | 3727 | 3937 | 4147 | 4357 | 4567 | 4777 | 4987 |
161 | 371 | 581 | 791 | 1001 | 1211 | 1421 | 1631 | 1841 | 2051 | 2261 | 2471 | 2681 | 2891 | 3101 | 3311 | 3521 | 3731 | 3941 | 4151 | 4361 | 4571 | 4781 | 4991 |
163 | 373 | 583 | 793 | 1003 | 1213 | 1423 | 1633 | 1843 | 2053 | 2263 | 2473 | 2683 | 2893 | 3103 | 3313 | 3523 | 3733 | 3943 | 4153 | 4363 | 4573 | 4783 | 4993 |
167 | 377 | 587 | 797 | 1007 | 1217 | 1427 | 1637 | 1847 | 2057 | 2267 | 2477 | 2687 | 2897 | 3107 | 3317 | 3527 | 3737 | 3947 | 4157 | 4367 | 4577 | 4787 | 4997 |
169 | 379 | 589 | 799 | 1009 | 1219 | 1429 | 1639 | 1849 | 2059 | 2269 | 2479 | 2689 | 2899 | 3109 | 3319 | 3529 | 3739 | 3949 | 4159 | 4369 | 4579 | 4789 | 4999 |
173 | 383 | 593 | 803 | 1013 | 1223 | 1433 | 1643 | 1853 | 2063 | 2273 | 2483 | 2693 | 2903 | 3113 | 3323 | 3533 | 3743 | 3953 | 4163 | 4373 | 4583 | 4793 | 5003 |
179 | 389 | 599 | 809 | 1019 | 1229 | 1439 | 1649 | 1859 | 2069 | 2279 | 2489 | 2699 | 2909 | 3119 | 3329 | 3539 | 3749 | 3959 | 4169 | 4379 | 4589 | 4799 | 5009 |
181 | 391 | 601 | 811 | 1021 | 1231 | 1441 | 1651 | 1861 | 2071 | 2281 | 2491 | 2701 | 2911 | 3121 | 3331 | 3541 | 3751 | 3961 | 4171 | 4381 | 4591 | 4801 | 5011 |
187 | 397 | 607 | 817 | 1027 | 1237 | 1447 | 1657 | 1867 | 2077 | 2287 | 2497 | 2707 | 2917 | 3127 | 3337 | 3547 | 3757 | 3967 | 4177 | 4387 | 4597 | 4807 | 5017 |
191 | 401 | 611 | 821 | 1031 | 1241 | 1451 | 1661 | 1871 | 2081 | 2291 | 2501 | 2711 | 2921 | 3131 | 3341 | 3551 | 3761 | 3971 | 4181 | 4391 | 4601 | 4811 | 5021 |
193 | 403 | 613 | 823 | 1033 | 1243 | 1453 | 1663 | 1873 | 2083 | 2293 | 2503 | 2713 | 2923 | 3133 | 3343 | 3553 | 3763 | 3973 | 4183 | 4393 | 4603 | 4813 | 5023 |
197 | 407 | 617 | 827 | 1037 | 1247 | 1457 | 1667 | 1877 | 2087 | 2297 | 2507 | 2717 | 2927 | 3137 | 3347 | 3557 | 3767 | 3977 | 4187 | 4397 | 4607 | 4817 | 5027 |
199 | 409 | 619 | 829 | 1039 | 1249 | 1459 | 1669 | 1879 | 2089 | 2299 | 2509 | 2719 | 2929 | 3139 | 3349 | 3559 | 3769 | 3979 | 4189 | 4399 | 4609 | 4819 | 5029 |
203 | 413 | 623 | 833 | 1043 | 1253 | 1463 | 1673 | 1883 | 2093 | 2303 | 2513 | 2723 | 2933 | 3143 | 3353 | 3563 | 3773 | 3983 | 4193 | 4403 | 4613 | 4823 | 5033 |
209 | 419 | 629 | 839 | 1049 | 1259 | 1469 | 1679 | 1889 | 2099 | 2309 | 2519 | 2729 | 2939 | 3149 | 3359 | 3569 | 3779 | 3989 | 4199 | 4409 | 4619 | 4829 | 5039 |
Таблица А\4\
1 | 211 | 421 | 631 | 841 | 1051 | 1261 | 1471 | 1681 | 1891 | 2101 | 2311 | 2521 | 2731 | 2941 | 3151 | 3361 | 3571 | 3781 | 3991 | 4201 | 4411 | 4621 | 4831 |
11 | 221 | 431 | 641 | 851 | 1061 | 1271 | 1481 | 1691 | 1901 | 2111 | 2321 | 2531 | 2741 | 2951 | 3161 | 3371 | 3581 | 3791 | 4001 | 4211 | 4421 | 4631 | 4841 |
13 | 223 | 433 | 643 | 853 | 1063 | 1273 | 1483 | 1693 | 1903 | 2113 | 2323 | 2533 | 2743 | 2953 | 3163 | 3373 | 3583 | 3793 | 4003 | 4213 | 4423 | 4633 | 4843 |
17 | 227 | 437 | 647 | 857 | 1067 | 1277 | 1487 | 1697 | 1907 | 2117 | 2327 | 2537 | 2747 | 2957 | 3167 | 3377 | 3587 | 3797 | 4007 | 4217 | 4427 | 4637 | 4847 |
19 | 229 | 439 | 649 | 859 | 1069 | 1279 | 1489 | 1699 | 1909 | 2119 | 2329 | 2539 | 2749 | 2959 | 3169 | 3379 | 3589 | 3799 | 4009 | 4219 | 4429 | 4639 | 4849 |
23 | 233 | 443 | 653 | 863 | 1073 | 1283 | 1493 | 1703 | 1913 | 2123 | 2333 | 2543 | 2753 | 2963 | 3173 | 3383 | 3593 | 3803 | 4013 | 4223 | 4433 | 4643 | 4853 |
29 | 239 | 449 | 659 | 869 | 1079 | 1289 | 1499 | 1709 | 1919 | 2129 | 2339 | 2549 | 2759 | 2969 | 3179 | 3389 | 3599 | 3809 | 4019 | 4229 | 4439 | 4649 | 4859 |
31 | 241 | 451 | 661 | 871 | 1081 | 1291 | 1501 | 1711 | 1921 | 2131 | 2341 | 2551 | 2761 | 2971 | 3181 | 3391 | 3601 | 3811 | 4021 | 4231 | 4441 | 4651 | 4861 |
37 | 247 | 457 | 667 | 877 | 1087 | 1297 | 1507 | 1717 | 1927 | 2137 | 2347 | 2557 | 2767 | 2977 | 3187 | 3397 | 3607 | 3817 | 4027 | 4237 | 4447 | 4657 | 4867 |
41 | 251 | 461 | 671 | 881 | 1091 | 1301 | 1511 | 1721 | 1931 | 2141 | 2351 | 2561 | 2771 | 2981 | 3191 | 3401 | 3611 | 3821 | 4031 | 4241 | 4451 | 4661 | 4871 |
43 | 253 | 463 | 673 | 883 | 1093 | 1303 | 1513 | 1723 | 1933 | 2143 | 2353 | 2563 | 2773 | 2983 | 3193 | 3403 | 3613 | 3823 | 4033 | 4243 | 4453 | 4663 | 4873 |
47 | 257 | 467 | 677 | 887 | 1097 | 1307 | 1517 | 1727 | 1937 | 2147 | 2357 | 2567 | 2777 | 2987 | 3197 | 3407 | 3617 | 3827 | 4037 | 4247 | 4457 | 4667 | 4877 |
53 | 263 | 473 | 683 | 893 | 1103 | 1313 | 1523 | 1733 | 1943 | 2153 | 2363 | 2573 | 2783 | 2993 | 3203 | 3413 | 3623 | 3833 | 4043 | 4253 | 4463 | 4673 | 4883 |
59 | 269 | 479 | 689 | 899 | 1109 | 1319 | 1529 | 1739 | 1949 | 2159 | 2369 | 2579 | 2789 | 2999 | 3209 | 3419 | 3629 | 3839 | 4049 | 4259 | 4469 | 4679 | 4889 |
61 | 271 | 481 | 691 | 901 | 1111 | 1321 | 1531 | 1741 | 1951 | 2161 | 2371 | 2581 | 2791 | 3001 | 3211 | 3421 | 3631 | 3841 | 4051 | 4261 | 4471 | 4681 | 4891 |
67 | 277 | 487 | 697 | 907 | 1117 | 1327 | 1537 | 1747 | 1957 | 2167 | 2377 | 2587 | 2797 | 3007 | 3217 | 3427 | 3637 | 3847 | 4057 | 4267 | 4477 | 4687 | 4897 |
71 | 281 | 491 | 701 | 911 | 1121 | 1331 | 1541 | 1751 | 1961 | 2171 | 2381 | 2591 | 2801 | 3011 | 3221 | 3431 | 3641 | 3851 | 4061 | 4271 | 4481 | 4691 | 4901 |
73 | 283 | 493 | 703 | 913 | 1123 | 1333 | 1543 | 1753 | 1963 | 2173 | 2383 | 2593 | 2803 | 3013 | 3223 | 3433 | 3643 | 3853 | 4063 | 4273 | 4483 | 4693 | 4903 |
79 | 289 | 499 | 709 | 919 | 1129 | 1339 | 1549 | 1759 | 1969 | 2179 | 2389 | 2599 | 2809 | 3019 | 3229 | 3439 | 3649 | 3859 | 4069 | 4279 | 4489 | 4699 | 4909 |
83 | 293 | 503 | 713 | 923 | 1133 | 1343 | 1553 | 1763 | 1973 | 2183 | 2393 | 2603 | 2813 | 3023 | 3233 | 3443 | 3653 | 3863 | 4073 | 4283 | 4493 | 4703 | 4913 |
89 | 299 | 509 | 719 | 929 | 1139 | 1349 | 1559 | 1769 | 1979 | 2189 | 2399 | 2609 | 2819 | 3029 | 3239 | 3449 | 3659 | 3869 | 4079 | 4289 | 4499 | 4709 | 4919 |
97 | 307 | 517 | 727 | 937 | 1147 | 1357 | 1567 | 1777 | 1987 | 2197 | 2407 | 2617 | 2827 | 3037 | 3247 | 3457 | 3667 | 3877 | 4087 | 4297 | 4507 | 4717 | 4927 |
101 | 311 | 521 | 731 | 941 | 1151 | 1361 | 1571 | 1781 | 1991 | 2201 | 2411 | 2621 | 2831 | 3041 | 3251 | 3461 | 3671 | 3881 | 4091 | 4301 | 4511 | 4721 | 4931 |
103 | 313 | 523 | 733 | 943 | 1153 | 1363 | 1573 | 1783 | 1993 | 2203 | 2413 | 2623 | 2833 | 3043 | 3253 | 3463 | 3673 | 3883 | 4093 | 4303 | 4513 | 4723 | 4933 |
107 | 317 | 527 | 737 | 947 | 1157 | 1367 | 1577 | 1787 | 1997 | 2207 | 2417 | 2627 | 2837 | 3047 | 3257 | 3467 | 3677 | 3887 | 4097 | 4307 | 4517 | 4727 | 4937 |
109 | 319 | 529 | 739 | 949 | 1159 | 1369 | 1579 | 1789 | 1999 | 2209 | 2419 | 2629 | 2839 | 3049 | 3259 | 3469 | 3679 | 3889 | 4099 | 4309 | 4519 | 4729 | 4939 |
113 | 323 | 533 | 743 | 953 | 1163 | 1373 | 1583 | 1793 | 2003 | 2213 | 2423 | 2633 | 2843 | 3053 | 3263 | 3473 | 3683 | 3893 | 4103 | 4313 | 4523 | 4733 | 4943 |
121 | 331 | 541 | 751 | 961 | 1171 | 1381 | 1591 | 1801 | 2011 | 2221 | 2431 | 2641 | 2851 | 3061 | 3271 | 3481 | 3691 | 3901 | 4111 | 4321 | 4531 | 4741 | 4951 |
127 | 337 | 547 | 757 | 967 | 1177 | 1387 | 1597 | 1807 | 2017 | 2227 | 2437 | 2647 | 2857 | 3067 | 3277 | 3487 | 3697 | 3907 | 4117 | 4327 | 4537 | 4747 | 4957 |
131 | 341 | 551 | 761 | 971 | 1181 | 1391 | 1601 | 1811 | 2021 | 2231 | 2441 | 2651 | 2861 | 3071 | 3281 | 3491 | 3701 | 3911 | 4121 | 4331 | 4541 | 4751 | 4961 |
137 | 347 | 557 | 767 | 977 | 1187 | 1397 | 1607 | 1817 | 2027 | 2237 | 2447 | 2657 | 2867 | 3077 | 3287 | 3497 | 3707 | 3917 | 4127 | 4337 | 4547 | 4757 | 4967 |
139 | 349 | 559 | 769 | 979 | 1189 | 1399 | 1609 | 1819 | 2029 | 2239 | 2449 | 2659 | 2869 | 3079 | 3289 | 3499 | 3709 | 3919 | 4129 | 4339 | 4549 | 4759 | 4969 |
143 | 353 | 563 | 773 | 983 | 1193 | 1403 | 1613 | 1823 | 2033 | 2243 | 2453 | 2663 | 2873 | 3083 | 3293 | 3503 | 3713 | 3923 | 4133 | 4343 | 4553 | 4763 | 4973 |
149 | 359 | 569 | 779 | 989 | 1199 | 1409 | 1619 | 1829 | 2039 | 2249 | 2459 | 2669 | 2879 | 3089 | 3299 | 3509 | 3719 | 3929 | 4139 | 4349 | 4559 | 4769 | 4979 |
151 | 361 | 571 | 781 | 991 | 1201 | 1411 | 1621 | 1831 | 2041 | 2251 | 2461 | 2671 | 2881 | 3091 | 3301 | 3511 | 3721 | 3931 | 4141 | 4351 | 4561 | 4771 | 4981 |
157 | 367 | 577 | 787 | 997 | 1207 | 1417 | 1627 | 1837 | 2047 | 2257 | 2467 | 2677 | 2887 | 3097 | 3307 | 3517 | 3727 | 3937 | 4147 | 4357 | 4567 | 4777 | 4987 |
163 | 373 | 583 | 793 | 1003 | 1213 | 1423 | 1633 | 1843 | 2053 | 2263 | 2473 | 2683 | 2893 | 3103 | 3313 | 3523 | 3733 | 3943 | 4153 | 4363 | 4573 | 4783 | 4993 |
167 | 377 | 587 | 797 | 1007 | 1217 | 1427 | 1637 | 1847 | 2057 | 2267 | 2477 | 2687 | 2897 | 3107 | 3317 | 3527 | 3737 | 3947 | 4157 | 4367 | 4577 | 4787 | 4997 |
169 | 379 | 589 | 799 | 1009 | 1219 | 1429 | 1639 | 1849 | 2059 | 2269 | 2479 | 2689 | 2899 | 3109 | 3319 | 3529 | 3739 | 3949 | 4159 | 4369 | 4579 | 4789 | 4999 |
173 | 383 | 593 | 803 | 1013 | 1223 | 1433 | 1643 | 1853 | 2063 | 2273 | 2483 | 2693 | 2903 | 3113 | 3323 | 3533 | 3743 | 3953 | 4163 | 4373 | 4583 | 4793 | 5003 |
179 | 389 | 599 | 809 | 1019 | 1229 | 1439 | 1649 | 1859 | 2069 | 2279 | 2489 | 2699 | 2909 | 3119 | 3329 | 3539 | 3749 | 3959 | 4169 | 4379 | 4589 | 4799 | 5009 |
181 | 391 | 601 | 811 | 1021 | 1231 | 1441 | 1651 | 1861 | 2071 | 2281 | 2491 | 2701 | 2911 | 3121 | 3331 | 3541 | 3751 | 3961 | 4171 | 4381 | 4591 | 4801 | 5011 |
187 | 397 | 607 | 817 | 1027 | 1237 | 1447 | 1657 | 1867 | 2077 | 2287 | 2497 | 2707 | 2917 | 3127 | 3337 | 3547 | 3757 | 3967 | 4177 | 4387 | 4597 | 4807 | 5017 |
191 | 401 | 611 | 821 | 1031 | 1241 | 1451 | 1661 | 1871 | 2081 | 2291 | 2501 | 2711 | 2921 | 3131 | 3341 | 3551 | 3761 | 3971 | 4181 | 4391 | 4601 | 4811 | 5021 |
193 | 403 | 613 | 823 | 1033 | 1243 | 1453 | 1663 | 1873 | 2083 | 2293 | 2503 | 2713 | 2923 | 3133 | 3343 | 3553 | 3763 | 3973 | 4183 | 4393 | 4603 | 4813 | 5023 |
197 | 407 | 617 | 827 | 1037 | 1247 | 1457 | 1667 | 1877 | 2087 | 2297 | 2507 | 2717 | 2927 | 3137 | 3347 | 3557 | 3767 | 3977 | 4187 | 4397 | 4607 | 4817 | 5027 |
199 | 409 | 619 | 829 | 1039 | 1249 | 1459 | 1669 | 1879 | 2089 | 2299 | 2509 | 2719 | 2929 | 3139 | 3349 | 3559 | 3769 | 3979 | 4189 | 4399 | 4609 | 4819 | 5029 |
209 | 419 | 629 | 839 | 1049 | 1259 | 1469 | 1679 | 1889 | 2099 | 2309 | 2519 | 2729 | 2939 | 3149 | 3359 | 3569 | 3779 | 3989 | 4199 | 4409 | 4619 | 4829 | 5039 |
Таблица Б\4\
Будем образовывать таблицу А\k+1\ перемещая по равному количеству столбцов таблицы Б\k\ в столбцы таблицы А\k+1\, соблюдая порядок заполнения сверху вниз, слева направо. Предположим, что строки таблицы Б\k\ представляют из себя арифметическую прогрессию с разностью d \k\, т.е. qi,j=qi,1 + d\k \*(j-1). Здесь первый индекс означает номер строки, а второй номер столбца в таблице Б\k\. Обозначим через m\k\ число строк таблицы Б\k\, а через N число столбцов таблицы Б\k\, перенесенных в столбец таблицы А\k+1\. Выберем произвольный элемент ai,j из таблицы А\k+1\. Вычислим разность ai,j+1 — ai,j между числами, стоящими в таблице А\k+1\ в одной строке и соседних столбцах. Очевидно, эти числа стояли в одной строке и в таблице Б\k\, а номера столбцов, в таблице Б\k\, содержащих эти числа, различаются на N. Поэтому
ai,j+1 — ai,j = N*d\k\. Таким образом, числа любой строки таблицы А\k+1\ образуют арифметическую прогрессию с разностью N*d\k\. Естественно выбрать N= pk+1. Тогда ai,j делится на pk+1в том и только том случае, ai,1 когда делится на pk+1. Итак, в таблице А\k+1\ числа, делящиеся на вновь группируются в отдельные строки. Вычеркнув их, мы получим следующую таблицу Б\k+1\. Алгоритм получения таблицы Б\k+1\ из таблицы Б\k\ в достаточной мере ясен. Неосвещённым остался лишь вопрос о нахождении строк для вычёркивания. Для этого годятся достаточно простые и грубые методы получения чисел, кратных pk+1, но мы пока не будем их рассматривать, удовлетворившись до времени сознанием теоретической возможности.
Посмотрев внимательно на первый столбец таблиц А\3\ и Б\3\, мы можем заметить симметрию в числах их составляющих. Сумма первого и последнего числа в столбце равна 30. Такова же сумма второго и предпоследнего, третьего сверху и третьего снизу, четвёртого сверху и четвёртого снизу чисел. Предположим, что таким свойством обладает первый столбец таблицы Б\k\, т.е ai,1 + am\k\ +1-i,1 = p1*p2*…*pk = d\k\. Здесь m\k\ – число строк в таблице Б\k\. Отметим, что подобным свойством, только с другой суммой, будет обладать любой столбец таблицы Б\k\, поскольку каждое число в нём получено из числа в первом столбце и той же строке путём сложения с постоянным для этого столбца слагаемым. Кроме того, аналогичное свойство выполняется для любого отрезка любой строки, поскольку строки представляют собой геометрическую прогрессию. Выберем произвольный элемент ai,j таблицы Бk и число N>j. Вычислим сумму
ai,j + am\k\+1-i,N+1-j = ai,1 + am\k\+1-i,N = a1,1 + am\k\,N = 1+ am\k\,N.
Воспользовавшись тем, что a1,m\k\ = d\k\ – 1, и последняя строка таблицы Б\k\, как и остальные строки, является арифметической прогрессией с разностью d\k\, получим
ai,j + am\k\+1-i,N+1-j = 1+ d – 1 + d\k\*(N – 1) = d\k\*N.
Отсюда и из способа построения таблиц следует сохранение свойства симметрии в таблицах А\k+1\ и Б\k+1\.
Свойством центральной симметрии обладает любая подтаблица таблицы Б\k\, полученная усечением справа до N столбцов. Выберем любое N из таблицы Б\k\. Читатели, надеюсь, не забыли, что числа в этой таблице не делятся ни на одно из чисел, не превосходящих pk. Покажем, что отрезок любой строки длиной N содержит числа, дающие разные остатки от деления на N. Предположим, что я ввожу читателя в заблуждение, и есть такие i, j и j1, что i<i1, i1-i<N и
ai,j ≡ ai1,j (mod N). Да не смущается сердце дилетанта. Сия устрашающая запись означает лишь, что ai,j и ai1,j дают одинаковый остаток при делении на N, а разность ai1,j — ai,j делится на N, т.е. ai1,j — ai,j = Q*N.
ai1,j — ai,j = d\k\*(i1-i) = p1*p2*…*pk*(i1-i) = Q*N.
Поскольку N не делится ни на одно из простых чисел p1, p2, …, pk, на эти числа делится Q. Значит, i1-i делится на N, что невозможно, поскольку i1-i<N. Из только что доказанного следует, что отрезок длиной N любой строки содержит ровно одно число, делящееся на N. В частности, это справедливо для крайнего левого отрезка любой строки длиной pk+1.
Построим теперь по таблице Б\k\ таблицу А\k+1\. Как мы условились выше, в первый столбец последовательно перенесём pk+1 столбцов. Заметим, что число pk+1 стоит на втором сверху месте в первом столбце таблицы Б\k\. Для построения остальных столбцов таблицы А\k+1\, мы можем воспользоваться тем, что каждая строка новой таблицы должна представлять собой арифметическую прогрессию с разностью d\k+1\ = p1*p2*…*pk* pk+1.
Пусть m\k\ – количество строк в таблице Б\k\. Очевидно, в таблице А\k+1\ число строк M\k+1\ = m\k\*pk+1.
В каждой строке из части таблицы Б\k\, перенесённой в первый столбец А\k+1\, как мы установили, находился ровно один элемент, делящийся нацело на pk+1. Следовательно, m\k+1\ = m\k\ *pk+1 — m\k\ = m\k\*(pk+1 – 1). Мы получили рекуррентную формулу для числа строк m\k+1\ = в таблице Б\k\. Проверив её для первых k, получим общую формулу.
m\k\ = (p1 – 1)*(p2 – 1)*…*(pk – 1)
Как мы уже заметили, в таблице Б\k\ 1+am\k\,1 = d\k\ т.е. am\k\,1 = d\k\ — 1.
В то же время a1,2 = 1 + d\k\ и a1,2 — am\k\,1 = 2.
Поскольку и первая, и последняя строки – арифметические прогрессии с разностью d\k\, разность равная 2 сохранится при сдвиге вверху и внизу на равное число элементов вправо.
a1,j+1 — am\k\,j = 2.
При переносе столбцов из таблицы Б\k\ в таблицу А\k+1\, на границах между принесенными столбцами получается разность равная 2.
Обозначим через S2\k\ число пар соседних строк таблицы Б\k\, разность элементов в каждом столбце которых равна 2. Тогда легко подсчитать число таких строк в таблице А\k+1\
S2\k+1\ = S2\k\*pk+1 + pk+1 -1 = (S2\k\ + 1)*pk+1 – 1.
В каждой строке из каждой рассматриваемой пары в отрезке от первого до pk+1-го элемента найдётся ровно один элемент, делящийся на pk+1. При этом они, очевидно будут находиться в разных столбцах таблицы Б\k\. Поэтому из таблицы А\k+1\ будут вычеркнуты 2*S2\k\ строки из пар с разностью 2. Кроме того по одному элементу, делящемуся на pk+1 найдется в верхней и нижней строке таблицы Б\k\. С учётом сказанного
S2\k+1\ = S2\k\*pk+1 + pk+1 -1- 2*S2\k\ — 2 = S2\k\*(pk+1 – 2) + pk+1 – 2 – 1 = (S2\k\ +1)*(pk+1 – 2) – 1.
Полученная рекуррентная формула не очень удобна для получения общей формулы. Дело упрощается, если подсчитываемым парам строк прибавить пару из нижней и верхней строк. Тогда s2\k\ = S2\k\+1, а
s2\k+1\ = s2\k\*(pk+1 – 2)
Новая рекуррентная формула действует, начиная с k = 2.
Для любых соседних строк из таблицы Б\k\, разность элементов из одного столбца постоянное чётное число. Пусть g > 2 – чётное число. Обозначим через sg\k\ число пар соседних строк таблицы Б\k\, разность элементов в каждом столбце которых равна g. В таблице А\k+1\ число пар соседних строк с разностью g будет, очевидно, равно
sg\k+1\ = sg\k\*pk+1
В каждой строке каждой пары в отрезке от первого до pk+1-го элемента найдётся ровно один элемент, делящийся на pk+1. Следовательно число пар строк с разностью g, оставшихся в таблице Б\k+1\, будет удовлетворять условию
sg\k+1\ ³ sg\k\*pk+1 — 2sg\k\
Мне уже слышатся гневные возражения дотошных читателей. Почему это я знак равенства заменил неравенством, и почему клювик знака неравенства повернут именно в эту сторону? Я мог бы отговориться тем, что неравенство у меня нестрогое, а потому допускает и равенство. В случае же равенства имею право вертеть клювом, куда мне вздумается. Но я не буду пользоваться этой уловкой и открою истинные мотивы моего поведения. Дело в том, что, при вычёркивании строки из таблицы А\k+1\ исчезает, естественно не пара строк. Соседними становятся строки, которые были выше и ниже вычеркнутой. Разности, которые были до вычёркивания, складываются, и никто не гарантирует, что результат не будет равен g. Таким образом возможно появление новых пар строк с разностью g.
Но тут можно ещё раз попытаться уличить автора. Если вычёркиваемая строка была общей для двух пар с разностью g, то в результате вычёркивания число пар с разностью g уменьшится сразу на 2, а не на одну пару. Не буду отрицать такой возможности. Пары строк с разностью g могут оказаться рядом, образуя тройку строк, в том случае, если g делится на 3. Но в этом случае удаляемая средняя строка будет посчитана дважды – как нижняя строка для верхней и как верхняя строка для нижней пары. Поэтому равенство или неравенство не нарушится.
Пара строк с разностью 4 в результате вычёркивания строки могла появиться лишь один раз, при вычёркивании средней строки из таблицы А\2\. После этого в таблице не осталось тройки чисел с разностью между ними равной 2, поскольку в такой тройке хотя бы одно число делится на 3. Следовательно для разности 4, полученное выше неравенство превращается в равенство.
s4\k+1\ = s4\k\*pk+1 — 2s4\k\ = s4\k\*(pk+1 – 2)
Рекуррентная формула для количества пар строк с разностью 4 совпала с такой же формулой для разности 2, с учётом того, что последняя строка таблицы Б\k\ объединяется в пару с первой строкой.
Таблица Б\2\ состоит из двух строк. Разность элементов в каждом столбце равна 4. Эти же строки образуют пару с разностью 2, если нижнюю строку считать первой, а верхнюю, со сдвигом на один элемент, второй.
Таким образом в таблице Б\k\ число пар строк с разностью 2 равно числу пар строк с разностью 4.
s2\k\ = s4\k\ = (p2-2)*(p3-2)*….*(pk-2)
Разность 6 может возникнуть лишь при вычёркивании строки, разности которой с соседними строками 2 и 4. При переносе чисел из таблицы Б\2\ в таблицу А\3\, образовались строки с разностями между ними 4;2;4;2;4;2;4;2;4. Очевидно, при вычёркивании любой строки получается новая разность равная 6. Нам необходимо вычеркнуть строки, состоящие из чисел, делящихся на 5. Таковы 2-я и 9-я строки. После вычёркивания этих строк в новой таблице Б\3\ останется 8 строк с разностями между ними 6;4;2;4;2;4;6. Эта последовательность повторится 7 раз для строк таблицы А\4\. Причём между повторами вставится разность 2, при переходе от одного переносимого столбца к другому.
6;4;2;4;2;4;6;2;6;4;2;4;2;4;6;2;6;4;2;4;2;4;6;2;6;4;2;4;2;4;6;2;6;4;2;4;2;4;6;2;6;4;2;4;2;4;6;2;6;4;2;4;2;4;6.
В таблице А\4\ содержится 56 строк которые можно разбить на 7 групп по 8 строк в каждой. Разность 6 может получиться при вычёркивании третьей, четвёртой, пятой или шестой строки из какой-либо группы. Поскольку каждая из групп получена перенесением столбцов из таблицы Б\3\, и номера строк в группе совпадают с номерами строк в таблице Б\3\, можно утверждать, что в таблице А\4\, для каждой из названных номеров строк, ровно в одной группе найдётся строка из чисел кратных 7. Таким образом вычёркивание ровно 4-х строк из таблицы А\4\ приведёт к появлению пар соседних строк с разностью 6. Дотошный читатель может убедиться в том, что разность 6 получается при вычёркивании строк 14 (6-я во 2-й группе), 21 (5-я в 3-й группе), 36 (4-я в 5-й группе), 43 (3-я в 6-й группе). При вычёркивании 2-й и 55-й строк образуется новая разность 10. При вычёркивании строк 25 и 32 образуется новая разность 8. Разность 8 может получиться лишь объединением разностей 2 и 6. Объединение равных разностей по 4 невозможно, поскольку из тройки натуральных чисел n, n+4, n+8 одно делится на 3. Разность 10 может получиться при объединении разностей 2 и 8, а также 4 и 6. В таблице Б\4\ получаются следующие разности между строками:
10;2;4;2;4;6;2;6;4;2;4;6;6;2;6;4;2;6;4;6;8;4;2;4;2;4;8;6;4;2;4;2;4;6;2;6;6;4;2;4;6;2;6;4;2;4;2;10.
Эти рассуждения показывают путь к вычислению количества пар строк для разных значений разности между ними. Мы не будем пока выводить соответствующие формулы.
Александр Петрович!
Вы сами понимаете, что вы совершили научное открытие?
Вас нужно выдвигать на Шнобелевскую премию. Только не знаю, как:)
Работа понравилась членам жюри. Поддерживаю правильный выбор.
Вы включены в длинный список победителей этого года. Приглашаем Вас на церемонию награждения в Москву 27 октября для получения специального диплома ОТ Знатоков Что? Где? Когда? и умной совы.
Более подробные сведения о вашей награде будут опубликованы на этом сайте 1 октября.
Благодарим за интерес к нашему проекту.
Светлана