Решето Эратосфена. Погоня за простыми числами.

В теории чисел  много проблем, формулировка которых понятна школьнику, но решение не поддавалось или не поддаётся до сих пор многим поколениям математиков. Значительная часть таких проблем связана с распределением простых чисел в натуральном ряду. Эта статья – отчаянная попытка изложить полученные мной скромные результаты таким образом, чтобы они были занятны и понятны как для тех, кто смыслит в теории чисел не более бельмеса, так и для скушавших не одну собаку в этой области.

Для первой категории читателей необходимо введение, достаточно краткое, дабы не усыпить вторую категорию. Простым называется число, имеющее ровно два различных делителя – единицу и само это число. Остальные натуральные числа, кроме единицы, называются составными. Первые простые числа  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\, в которую записаны все числа, не делящиеся нацело на первые простые числа p₁, p₂, … p_k. Так в таблице Б\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\, т.е. q_i,j=q_i,1 + d\k \*(j-1). Здесь первый индекс означает номер строки, а второй номер столбца в таблице Б\k\. Обозначим через m\k\ число строк таблицы Б\k\, а через N число столбцов таблицы Б\k\, перенесенных в столбец таблицы А\k+1\. Выберем произвольный элемент a_i,j из таблицы А\k+1\. Вычислим разность a_i,j+1 — a_i,j между числами, стоящими в таблице А\k+1\ в одной строке и соседних столбцах. Очевидно, эти числа стояли в одной строке и в таблице Б\k\, а номера столбцов, в таблице Б\k\, содержащих эти числа, различаются на N. Поэтому
a_i,j+1 — a_i,j = N*d\k\. Таким образом, числа любой строки таблицы А\k+1\ образуют арифметическую прогрессию с разностью N*d\k\. Естественно выбрать N= p_k+1. Тогда a_i,j делится на p_k+1в том и только том случае, a_i,1 когда делится на p_k+1. Итак, в таблице А\k+1\ числа, делящиеся на вновь группируются в отдельные строки. Вычеркнув их, мы получим следующую таблицу Б\k+1\. Алгоритм получения таблицы Б\k+1\ из таблицы Б\k\ в достаточной мере ясен. Неосвещённым остался лишь вопрос о нахождении  строк для вычёркивания. Для этого годятся достаточно простые и грубые методы получения чисел, кратных p_k+1, но мы пока не будем их рассматривать, удовлетворившись до времени сознанием теоретической возможности.

Посмотрев внимательно на первый столбец таблиц А\3\ и Б\3\, мы можем заметить симметрию в числах их составляющих. Сумма первого и последнего числа в столбце равна 30. Такова же сумма второго и предпоследнего, третьего сверху и третьего снизу, четвёртого сверху и четвёртого снизу чисел. Предположим, что таким свойством обладает первый столбец таблицы Б\k\, т.е  a_i,1 + a_{m\k\ +1-i,1} = p₁*p₂*…*p_k = d\k\. Здесь m\k\ – число строк в таблице Б\k\. Отметим, что подобным свойством, только с другой суммой, будет обладать любой столбец таблицы Б\k\, поскольку каждое число в нём получено из числа в первом столбце и той же строке путём сложения с постоянным для этого столбца слагаемым.  Кроме того, аналогичное свойство выполняется для любого отрезка любой строки, поскольку строки представляют собой геометрическую прогрессию. Выберем произвольный элемент a_i,j таблицы Бk и число N>j. Вычислим сумму
a_i,j + a_{m\k\+1-i,N+1-j} =  a_i,1 + a_m\k\+1-i,N = a_1,1 + a_m\k\,N = 1+ a_m\k\,N.

Воспользовавшись тем, что a_1,m\k\ =  d\k\ – 1, и последняя строка таблицы  Б\k\, как и остальные строки, является арифметической прогрессией с разностью d\k\, получим
a_i,j + a_{m\k\+1-i,N+1-j} =  1+ d – 1 + d\k\*(N – 1) = d\k\*N.

Отсюда и из способа построения таблиц следует сохранение свойства симметрии в таблицах А\k+1\ и Б\k+1\.

Свойством центральной симметрии обладает любая подтаблица таблицы Б\k\, полученная усечением справа до N столбцов. Выберем любое N из таблицы Б\k\. Читатели, надеюсь, не забыли, что числа в этой таблице не делятся ни на одно из чисел, не  превосходящих  p_k. Покажем, что отрезок любой строки длиной N содержит числа, дающие разные остатки от деления на N. Предположим, что я ввожу читателя в заблуждение, и есть такие i, j и j1, что i<i1, i1-i<N и
a_i,j ≡ a_i1,j (mod N). Да не смущается сердце дилетанта. Сия устрашающая запись означает лишь, что a_i,j и a_i1,j дают одинаковый остаток при делении на N, а разность a_i1,j — a_i,j делится на N, т.е. a_i1,j — a_i,j = Q*N.
a_i1,j — a_i,j = d\k\*(i1-i) = p₁*p₂*…*p_k*(i1-i) = Q*N.

Поскольку N не делится ни на одно из простых чисел p₁, p₂, …, p_k, на эти числа делится Q. Значит, i1-i делится на N, что невозможно, поскольку i1-i<N.  Из только что доказанного следует, что отрезок длиной N любой строки  содержит ровно одно число, делящееся на N. В частности, это справедливо для крайнего левого отрезка любой строки длиной p_k+1.

Построим теперь по таблице Б\k\ таблицу А\k+1\. Как мы условились выше, в первый столбец последовательно перенесём p_k+1 столбцов. Заметим, что число p_k+1 стоит на втором сверху месте в первом столбце таблицы Б\k\. Для построения остальных столбцов таблицы А\k+1\, мы можем воспользоваться тем, что каждая строка новой таблицы должна представлять собой арифметическую прогрессию с разностью d\k+1\ = p₁*p₂*…*p_k* p_k+1.

Пусть m\k\ – количество строк в таблице Б\k\. Очевидно, в таблице А\k+1\ число строк M\k+1\  = m\k\*p_k+1.

В каждой строке из части таблицы Б\k\, перенесённой в первый столбец А\k+1\, как мы установили,  находился ровно один элемент, делящийся нацело на p_k+1. Следовательно, m\k+1\ = m\k\ *p_k+1 — m\k\ = m\k\*(p_k+1 – 1). Мы получили рекуррентную формулу для числа строк m\k+1\  = в таблице Б\k\. Проверив её для первых k, получим общую формулу.

m\k\ = (p₁ – 1)*(p₂ – 1)*…*(p_k – 1)

Как мы уже заметили, в таблице Б\k\ 1+a_m\k\,1 = d\k\ т.е. a_m\k\,1 = d\k\ — 1.

В то же время a_1,2 = 1 + d\k\ и a_1,2 — a_m\k\,1 =  2.

Поскольку и первая, и последняя строки – арифметические прогрессии с разностью d\k\, разность равная 2 сохранится при сдвиге вверху и внизу на равное число элементов вправо.

a_1,j+1 — a_m\k\,j =  2.

При переносе столбцов из таблицы Б\k\ в таблицу А\k+1\, на границах между принесенными столбцами получается разность равная 2.

Обозначим  через S2\k\ число пар соседних строк таблицы Б\k\, разность  элементов в каждом столбце которых равна 2. Тогда легко подсчитать число таких строк в таблице А\k+1\

S2\k+1\ = S2\k\*p_k+1 + p_k+1 -1 = (S2\k\ + 1)*p_k+1 – 1.

В каждой строке из каждой рассматриваемой пары в отрезке от первого до p_k+1-го элемента найдётся ровно один элемент, делящийся на p_k+1. При этом они, очевидно будут находиться в разных столбцах таблицы Б\k\. Поэтому из таблицы А\k+1\ будут вычеркнуты  2*S2\k\ строки из пар с разностью 2. Кроме того по одному элементу, делящемуся на p_k+1 найдется в верхней и нижней строке таблицы Б\k\. С учётом сказанного

S2\k+1\ = S2\k\*p_k+1 + p_k+1 -1- 2*S2\k\ — 2 = S2\k\*(p_k+1 – 2) + p_k+1 – 2 – 1 = (S2\k\ +1)*(p_k+1 – 2) – 1.

Полученная рекуррентная формула не очень удобна для получения общей формулы. Дело упрощается, если подсчитываемым парам строк прибавить пару из нижней и верхней строк. Тогда s2\k\ = S2\k\+1, а

s2\k+1\ = s2\k\*(p_k+1 – 2)

Новая рекуррентная формула действует, начиная с k = 2.

Для любых соседних строк из таблицы Б\k\, разность элементов из одного  столбца постоянное чётное число. Пусть g > 2 – чётное число. Обозначим  через sg\k\ число пар соседних строк таблицы Б\k\, разность  элементов в каждом столбце которых равна g. В таблице А\k+1\ число пар соседних строк с разностью g будет, очевидно, равно

sg\k+1\ = sg\k\*p_k+1

В каждой строке каждой пары в отрезке от первого до p_k+1-го элемента найдётся ровно один элемент, делящийся на p_k+1. Следовательно число пар строк с разностью g, оставшихся в таблице Б\k+1\, будет удовлетворять условию

sg\k+1\ ³  sg\k\*p_k+1 — 2sg\k\

Мне уже слышатся гневные возражения дотошных читателей. Почему это я знак равенства заменил неравенством, и почему клювик знака неравенства повернут именно в эту сторону?  Я мог бы отговориться тем, что неравенство у меня нестрогое, а потому допускает и равенство. В случае же равенства имею право вертеть клювом, куда мне вздумается. Но я не буду пользоваться этой уловкой и открою истинные мотивы моего поведения. Дело в том, что, при вычёркивании строки из таблицы А\k+1\ исчезает, естественно не пара строк. Соседними становятся строки, которые были выше и ниже вычеркнутой. Разности, которые были до вычёркивания, складываются, и никто не гарантирует, что результат не будет равен g. Таким образом возможно появление новых пар строк с разностью g.

Но тут можно ещё раз попытаться уличить автора. Если вычёркиваемая строка была общей для двух пар с разностью g, то в результате вычёркивания число пар с разностью g уменьшится сразу на 2, а не на одну пару. Не буду отрицать такой возможности. Пары строк с разностью g могут оказаться рядом, образуя тройку строк, в том случае, если g делится на 3. Но в этом случае удаляемая средняя строка  будет посчитана дважды – как нижняя строка для верхней и как верхняя строка для нижней пары. Поэтому равенство или неравенство не нарушится.

Пара строк с разностью 4 в результате вычёркивания строки могла появиться лишь один раз, при вычёркивании средней строки из таблицы А\2\. После этого в таблице не осталось тройки чисел с разностью между ними равной 2, поскольку в такой тройке хотя бы одно число делится на 3. Следовательно для разности 4, полученное выше неравенство превращается в равенство.

s4\k+1\ =  s4\k\*p_k+1 — 2s4\k\ = s4\k\*(p_k+1 – 2)

Рекуррентная формула для количества пар строк с разностью 4 совпала с такой же формулой для разности 2, с учётом того, что последняя строка таблицы Б\k\ объединяется в пару с первой строкой.

Таблица Б\2\ состоит из двух строк. Разность элементов в каждом столбце равна 4. Эти же строки образуют пару с разностью 2, если нижнюю строку считать первой, а верхнюю, со сдвигом на один элемент, второй.

Таким образом  в таблице Б\k\ число пар строк с разностью 2 равно числу пар строк с разностью 4.

s2\k\ = s4\k\ = (p₂-2)*(p₃-2)*….*(p_k-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.

Эти рассуждения показывают путь к вычислению количества пар строк для разных значений разности между ними. Мы не будем пока выводить соответствующие формулы.