Возрастающая последовательность натуральных чисел

[Ktina]

Дана возрастающая последовательность натуральных чисел $(a_n)$.
Известно, что среди сумм $a_i+a_j$, где $i\le j$ нет двух одинаковых.
Для каждого $n\in\mathbb N$ найти наименьшее возможное значение $a_n$.

Мне удалось найти только нижнюю границу:

$$a_n\ge \lceil\frac{1}{4}n^2+\frac{1}{4}n+\frac{1}{2}\rceil$$

Действительно, для каждого $a_n$ рассмотрим суммы $a_i+a_j$, где $i\le j$ и $i, j\le n$.
Таких сумм будет ровно $\frac{1}{2}n^2+\frac{1}{2}n$.
Поскольку эти суммы принимают только натуральные значения (наименьшее возможное из которых равно 2), а также поскольку нет двух одинаковых сумм, приходим к выводу, что наибольшая из этих сумм (а именно $a_n+a_n$) не меньше $\frac{1}{2}n^2+\frac{1}{2}n+1$. Но тогда $a_n\ge\lceil\frac{1}{4}n^2+\frac{1}{4}n+\frac{1}{2}\rceil$.

Но это - лишь нижняя граница, так как уже при $n=4$ мы не можем построить последовательность, удовлетворяющую условию задачи, если $a_4=\lceil\frac{1}{4}\cdot 4^2+\frac{1}{4}\cdot 4+\frac{1}{2}\rceil=6$ (тупым перебором можно в этом убедиться).

Пожалуйста, помогите разобраться.
Заранее благодарна!

[Sender]

Ну вот в OEIS есть что-то похожее: http://oeis.org/A005282

-- Пт авг 10, 2012 15:34:27 --

Хотя для данной задачи эта последовательность может служить лишь верхней оценкой. Например, наименьшее значение $a_4$ не превосходит 7, если взять последовательность ${a_n}=1, 2, 5, 7$.

[Cash]

Простое соображение, что все разности $a_i-a_j$(которых $\frac{n^2-n}{2}$) различны дает нам оценку $a_n\geq \frac{n^2-n}{2}+1$

Перебор на компьютере до $n\leq 9$ дает следующие результаты
$1,2,4,7,12,18,26,35,45$

(Соответствующие последовательности)

1,2
1,2,4
1,3,6,7
1,3,8,11,12
1,6,8,14,17,18
1,3,8,16,22,25,26
1,3,13,20,26,31,34,35
1,4,10,18,20,33,40,44,45

[Профессор Снэйп]

Есть ощущение, что там будут степени двойки

[Cash]

Предполагается, что нахождение этого минимального максимума - NP-полная задача
http://en.wikipedia.org/wiki/Golomb_ruler
http://en.wikipedia.org/wiki/Sidon_sequence

[megamix62]

Ответ: Треугольные числа

[arseniiv]

Почему?

Приведённые Cash числа

Cash в сообщении #604797 писал(а):

$1,2,4,7,12,18,26,35,45$

на треугольные не похожи — разности не те.

[maxal]

Cash в сообщении #604797 писал(а):

Перебор на компьютере до $n\leq 9$ дает следующие результаты
$1,2,4,7,12,18,26,35,45$

Это A003022(n)+1.