1) Находится простое число r, не делящее n, которое не слишком велико (не превосходит C(log n)^5) и такое, что n имеет достаточно большой (не меньше 4(log n)^2) порядок в мультипликативной группе поля Z_r.

2) Проверяется выполнение равенств (x+a)^n = x^n+a для всех натуральных a \le 2\sqrt{r}log n с коэффициентами из кольца Z_n по модулю многочлена x^r-1.

3) Если число n проходит эти тесты, то оно является степенью простого, и остаётся лишь проверить, не является ли оно квадратом, кубом и т.д.

Вот найденные арифметические прогрессии:

Код:
[47, 257, 467, 677, 887, 1097, 1307]
[179, 389, 599, 809, 1019, 1229, 1439]
[199, 409, 619, 829, 1039, 1249, 1459]
[409, 619, 829, 1039, 1249, 1459, 1669]
[619, 829, 1039, 1249, 1459, 1669, 1879]
[829, 1039, 1249, 1459, 1669, 1879, 2089]
[881, 1091, 1301, 1511, 1721, 1931, 2141]
[1091, 1301, 1511, 1721, 1931, 2141, 2351]
[1453, 1663, 1873, 2083, 2293, 2503, 2713]
[3499, 3709, 3919, 4129, 4339, 4549, 4759]
[3709, 3919, 4129, 4339, 4549, 4759, 4969]
[3919, 4129, 4339, 4549, 4759, 4969, 5179]
[10529, 10739, 10949, 11159, 11369, 11579, 11789]
[10627, 10837, 11047, 11257, 11467, 11677, 11887]
[10837, 11047, 11257, 11467, 11677, 11887, 12097]
[10859, 11069, 11279, 11489, 11699, 11909, 12119]
[11069, 11279, 11489, 11699, 11909, 12119, 12329]
[11279, 11489, 11699, 11909, 12119, 12329, 12539]
[14423, 14633, 14843, 15053, 15263, 15473, 15683]
[20771, 20981, 21191, 21401, 21611, 21821, 22031]
[22697, 22907, 23117, 23327, 23537, 23747, 23957]
[30097, 30307, 30517, 30727, 30937, 31147, 31357]
[30307, 30517, 30727, 30937, 31147, 31357, 31567]
[31583, 31793, 32003, 32213, 32423, 32633, 32843]
[31793, 32003, 32213, 32423, 32633, 32843, 33053]
[32363, 32573, 32783, 32993, 33203, 33413, 33623]
[41669, 41879, 42089, 42299, 42509, 42719, 42929]
[75703, 75913, 76123, 76333, 76543, 76753, 76963]
[93281, 93491, 93701, 93911, 94121, 94331, 94541]
[95747, 95957, 96167, 96377, 96587, 96797, 97007]
120661 120871 121081 121291 121501 121711 121921
120737 120947 121157 121367 121577 121787 121997
120871 121081 121291 121501 121711 121921 122131
120947 121157 121367 121577 121787 121997 122207
129287 129497 129707 129917 130127 130337 130547
140603 140813 141023 141233 141443 141653 141863
153319 153529 153739 153949 154159 154369 154579
153529 153739 153949 154159 154369 154579 154789
182537 182747 182957 183167 183377 183587 183797
182747 182957 183167 183377 183587 183797 184007
205187 205397 205607 205817 206027 206237 206447
217351 217561 217771 217981 218191 218401 218611
269713 269923 270133 270343 270553 270763 270973

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