Комплементарные числа

[Pavlovsky]

При построении магических квадратов, возникла вот такая задачка из теории (простых) чисел.

Задача. Найти 16 последовательных простых чисел, образующих 8 пар комплементарных чисел.

Последовательностью k пар комплементарных чисел, будем называть возрастающую последовательность 2k чисел, такую что все числа можно разбить на k пар сумма которых одинакова.

[omega]

Уточню: эта задача возникла при построении пандиагональных квадратов 4-го порядка из последовательных простых чисел.

Приведу для иллюстрации построенный мной пандиагональный квадрат 4-го порядка из произвольных простых чисел:

Код: Выбрать все

13 83 31 113
97 47 79 17
89 7 107 37
41 103 23 73

Вот набор 16 простых чисел, из которых составлен этот квадрат:

Код: Выбрать все

7 13 17 23 31 37 41 47 73 79 83 89 97 103 107 113

Очевидно, что набор состоит из 8 пар комплементарных (взаимно дополнительных) чисел, сумма чисел в каждой паре равна 120 (половина магической константы квадрата).

[mihailm]

A что компьютер то говорит?
И вообще ee можно решать без компьютера?
Аддитивная теория чисел это такая мутная тема) там насколько я понимаю и задач то решенных почти нет, на простые вопросы ответить не можем

[Pavlovsky]

Простую задачу я бы и сам решил. Ha готовое решение я не расчитываю. Буду рад любой мысли по-поводу. Компьютер говорит, что среди первых 50 миллионов простых чисел нет такой последовательности.

Ниже представлены все последовательности 14-ти последовательных простых чисел образующих 7 пар комплементарных чисел, среди первых 50 миллионов простых чисел.
Первое число медиана (половина суммы пары комплементарных чисел). Следующие 7 чисел смещение, для образования пары комплементарных чисел надо медиану сложить и вычесть co смещением.

8021811 10 20 22 40 52 58 62
20066025 2 16 22 38 62 64 82
62550600 11 17 19 23 29 37 43
102979590 29 37 47 59 71 73 83
110608470 1 19 29 31 47 73 79
136450140 11 59 61 67 77 91 107
162607725 4 26 34 52 62 64 76
353656545 2 28 56 62 68 76 92
390175935 4 8 14 22 34 52 56
489539985 2 16 28 58 68 98 104
591815055 2 14 16 28 44 68 74
593566935 2 14 56 58 62 64 98
609486540 17 29 31 43 53 71 73
622696515 2 16 22 26 44 52 62
633778593 26 40 44 50 64 76 86
683850999 10 32 38 88 100 110 122
783914670 13 17 29 37 43 47 53
951212625 4 16 28 32 56 58 74

[mihailm]

50 млн простых чисел это неплохо, правильно я понял что это не простые числа до 50 млн?

[Pavlovsky]

Это именно 50 миллионов простых чисел. Наибольшее из них равно 982451653.
[url=http://primes.utm.edu/lists/small/millions/]http://primes.utm.edu/lists/small/millions/[/url]

[mihailm]

Подозреваю что вряд ли новое скажу(

Ну где-нить в теории стал бы искать утверждения сокращающие перебор
Типа "числа вида 6k+1, в качестве первого простого числа брать бессмысленно, не получится из них комплиментарной последовательности"
Это видимо явно неверно (8021749 например имеет такой вид), но я про идею
Это раз
A второе (в помощь первому) анализировать надо имеющиеся комплиментарные последовательности
И перебор вести по замеченным особенностям КП (понятно, что их даже доказывать необязательно)

P.S. И третье комп для такой задачи взял бы Крей

[Pavlovsky]

P.S. И третье комп для такой задачи взял бы Крей

Да это бы было неплохо.
Если решать тупым перебором, то проверка на комплементарность тривиальна. Скажем первые 50 миллионов проверялись всего около часа. Это на обычном PC да еще на тормазнутой платформе 1C:Предприятие. Значит самое сложное сгенерировать простые числа где то до значений 10^12.

Ну где-нить в теории стал бы искать утверждения сокращающие перебор
Типа "числа вида 6k+1, в качестве первого простого числа брать бессмысленно, не получится из них комплиментарной последовательности"
Это видимо явно неверно (8021749 например имеет такой вид), но я про идею
Это раз
A второе (в помощь первому) анализировать надо имеющиеся комплиментарные последовательности
И перебор вести по замеченным особенностям КП (понятно, что их даже доказывать необязательно)

Я рассуждал аналогично. Если сгенерировать все простые числа технически невозможно, значит надо искать области, где появление длинных комплементарных последовательностей наиболее вероятно. Скажем рассмаривать арифметическую последовательность ak+b, для k=1,2,... Смысл в этом подходе есть, только при условии что a очень большое (скажем в районе миллиона). Увы проанализировав найденные последовательности из 14 чисел, все что нашел, что все медианы кратны 3. Шаг арифметической последовательности 3 - это конечно несерьезно.

Ну и до кучи:
Пусть даны различные простые числа (p1,p2,…,pk). Тогда последовательность из чисел не делящихся на заданные простые числа содержит бесконечное число комплементарных чисел, c медианами кратными p1*p2*…*pk/2.

[Pavlovsky]

Давно подозревал, что в математике уже все доказано и найдено.
[url=http://www.research.att.com/~njas/sequences/A055382]http://www.research.att.com/~njas/sequences/A055382[/url]
Последовательность из 8 пар комплементарных чисел начинается c 1071065111. Ссылку дал maxl.

[omega]

Ничего подобно! A где пандиагональный квадрат?
Из всех этих наборов ни один квадратик не сложился, я перепроверила (Макс проверял сам).