Necessary conditions for the existence of a Skolem sequence

Theorem

A Skolem sequence of order $n$ can only exist if $n\equiv 0,1 (\bmod{4})$.

Proof

Let $S$ be a Skolem sequence of order $n$ and let $a_i$ and $b_i$ be the positions of the first and second occurrences respectively of the integer $i$ in $S$, where $1 \le i \le n$.

We can thus conclude that $b_i - a_i = i,$ for each $i$ from 1 to $n$.

Summing both sides of this equation we obtain:

$\displaystyle \sum_i^n b_i - \sum_i^n a_i = \sum_i^n i = \frac{n(n + 1)}{2}$

Now the $a_i$ and the $b_i$ represent the positions in the sequence from $1$ to $2n$, so we can see that:

$\displaystyle \sum_i^n b_i + \sum_i^n a_i = \frac{2n(2n + 1)}{2} = n(2n + 1)$

Summing the previous two equations we obtain the identity:

$\displaystyle \sum_i^n b_i = \frac{n(5n + 3)}{4}$

The left hand side of this last equality is a sum of positions and thus must be integer.

We conclude that the right hand side must also be an integer, which occurs exactly when: $n \equiv 0, 1 (\bmod{4})$.

$\blacksquare$

Sources

• Th. Skolem, On certain distributions of integers in pairs with given differences, Math. Scand. 5 (1957) 57-68.