xvii. Sequence and Number Constructions

Target	Construction
any $x\in [0,2^k)$ as a subset sum	powers of two $1,2,4,\dots$
any $x\in [0,S]$ as a subset sum with few items	$1,2,4,\dots ,2^j$ and the remainder $S-(2^{j+1}-1)$ (binary splitting, used in bounded knapsack)
set with no 3-term arithmetic progression	numbers with no digit $2$ in base 3 (greedy Stanley sequence)
Sidon set (all pairwise sums distinct) of size $p$	$\{2pk+(k^2\mathrm{mod}p)\}$, $p$ prime (Erdős–Turán)
pairwise $\gcd >1$ but total $\gcd =1$	products of all but one of $k$ primes: $\{p_2\cdots p_k,\dots \}$, e.g. $6,10,15$
array with every subarray sum $\ne 0$ (or any prefix trick)	build prefix sums first, then take differences
$k$ distinct positive integers with sum $n$	$1,2,\dots ,k-1$ and $n-\left(\genfrac{}{}{0ex}{}{k}{2}\right)$ (needs $n-\left(\genfrac{}{}{0ex}{}{k}{2}\right)\ge k$)
numbers with a given xor and sum	$(x,(s-x)/2,(s-x)/2)$ when $s\ge x$ and $s-x$ is even
sum-free set in $[1,n]$	the upper half $(n/2,n]$, or all odd numbers

vector<int> apFree(int m) {                    // first m naturals (from 0) with no digit 2 in base 3: no 3-term AP
    vector<int> r;
    for (int x = 0; sz(r) < m; x++) { int y = x; bool ok = true; while (y) { if (y % 3 == 2) ok = false; y /= 3; } if (ok) r.push_back(x); }
    return r;
}
vector<int> sidonSet(int p) {                  // p prime: {2pk + (k^2 mod p)}, k < p, all pairwise sums distinct
    vector<int> r;
    for (int k = 0; k < p; k++) r.push_back(2 * p * k + (k * k) % p);
    return r;
}

Proof: no 3-term AP, and the Sidon property

No AP. Suppose $x+z=2y$ with $x<y<z$ all having base-3 digits in $\{0,1\}$. Then $2y$ has digits in $\{0,2\}$ with no carries, and $x+z$ also has no carries (digit sums are at most $2$). Comparing digit by digit, every digit of $x+z$ equals the corresponding digit of $2y$, which is $0$ or $2$, so $x$ and $z$ agree in every digit, contradicting $x<z$. Sidon. Write $a_k=2pk+(k^2\mathrm{mod}p)$ with $k^2\mathrm{mod}p<p$. If $a_i+a_j=a_k+a_l$, then reading the sum modulo $2p$ and dividing gives $i+j=k+l$ (the residues add up to less than $2p$) and $i^2+j^2\equiv k^2+l^2(\mathrm{mod}p)$. Then $\{i,j\}$ and $\{k,l\}$ have the same sum and, mod $p$, the same sum of squares, hence the same product mod $p$; they are the roots of the same quadratic over ${\mathbb{F}}_p$, so $\{i,j\}=\{k,l\}$. Checked for primes up to $31$ and the AP-free set up to 300 elements.

Proof: xor and sum

If $a\oplus b=x$ and $a+b=s$, then $s=x+2(a\&b)$, so $s\ge x$ and $s-x$ is even are necessary. With $h=(s-x)/2$, the triple $(x,h,h)$ has xor $x$ and sum $s$. Two numbers suffice iff additionally $h\&x=0$, namely $(x+h,h)$.

Related: Reachability, Bit Tricks.