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 sase $$$m < 3$$$ is obvious, we further assume that all numbers in 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}}$$$, 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 $$$2\sqrt{2} \approx 2.82$$$ times shorter than this upper bound. Can you improve 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 for 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 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 want to find some answers on these questions, so feel free to comment!