Problem statement: You are given an integer $$$N$$$ and the task is to output an integer sequence $$$a_1, \ldots, a_m$$$, such that $$$1 \leq a_i \leq N$$$ and $$$a_i + a_j \neq a_k + a_l$$$ for $$$i \neq j, k \neq l, (i,\ j) \neq (k,\ l)$$$ (i. e. all $$$\frac{m(m-1)}{2} $$$ pairwise sums should be different). The goal is to maximize $$$m$$$ — the length of resulting sequence.

This problem comes from RUCODE recent competition, it had a requirement for answer $$$m \geq \frac{\sqrt{N}}{2}$$$. Also there was a requirement for $$$a_i \neq a_j,\ i \neq j$$$, but in reality in makes almost no sense since if $$$m \geq 3$$$ and if $$$a_i == a_j$$$ for some $$$i \neq j$$$, than $$$a_k + a_i == a_k + a_j$$$ for any $$$k \neq i,\ k \neq j$$$. Since case $$$m < 3$$$ is obvious, we will further assume that all numbers in a sequence are different.

The solution to this problem comes from the fact that...

So, if we take largest prime $$$p$$$ that $$$2p ^ 2 + (p ^ 2 + 1) \bmod (2p) <= N$$$, we will get a sequence with $$$m \approx \sqrt{\frac{N}{2}} = \frac{\sqrt{N}}{\sqrt{2}} = lb_1(N)$$$, which is enough to solve the original problem.

Now there some interesting questions:

1. Can we get some upper bound for $$$m$$$?

2. How can we compute the longest possible (an optimal) sequence for some small $$$N$$$?

Here are my humble answers:

1). Since $$$a_i + a_j < 2N$$$, then by Dirichlet's principle we get $$$\frac{m(m-1)}{2} < 2N \Rightarrow m^2 < 4N \Rightarrow m < 2\sqrt{N}$$$. So our construction is $$$ub_1 = 2\sqrt{2} \approx 2.82$$$ times shorter than this upper bound.

2). I wrote a recursive bruteforce, it can find the optimal answer for $$$N = 64$$$ in about $$$10$$$ seconds.

#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;

int mx, n;
__uint128_t best;

void go(__uint128_t nums, __uint128_t sums, int last = 0, int dep = 0) {
    if (dep > mx) best = nums, mx = dep;
    for (int i = last + 1; i <= n; ++i) {
        if ((sums & (nums << i)) == 0) {
            go(nums | (__uint128_t)(1) << i, sums | (nums << i), i, dep + 1);
        }
    }
}

void solve(int N) {
    best = mx = 0, n = N;
    go(0, 0);
    for (int i = 0; i < 128; ++i) {
        if (best >> i & 1) cout << i << ' ';
    } 
    cout << '\n';
}

int main() {
    solve(64);
}

These questions brings us to some more challenging problems:

1. Can we improve aforementioned lower bound construction? Or write some code, which will build longer sequence with some bruteforce and pruning?

2. Can we improve above the algorithm for finding the optimal sequence? Maybe get some polynomial solution (or prove that it lies somewhere in NP class)?

3. Can we improve upper bound for $$$m$$$?

Really wanna find some answers on these questions, appreciate any of your thoughts!

UPD1: thanks to nor, we now have an upper bound $$$m < (1 + \varepsilon) \sqrt{N} = ub_2(N)$$$, which brings us to the $$$\underset{N \to \infty}{\lim}\dfrac{ub_2(N)}{lb_1(N)} = \sqrt{2} \approx 1.41$$$ which is a massive improvement! Proof can be found here. Turns out that this problem was researched even before the era of computers!