Data and analyses by Rudini Sampaio, Universidade Federal do Ceará. Data licensed under CC BY 4.0; code under the MIT license.
Couples-are-Forever is a two-player impartial combinatorial game under normal play (the player who cannot move loses). A position of size n can be split into two smaller positions of sizes i and n−i, with 1 ≤ i ≤ n/2, except that positions of size 1 and 2 are terminal: a “couple” is forever and cannot be separated. The two parts are then played as a disjunctive sum.
By the Sprague–Grundy theorem, the game on a position of size n is equivalent to a Nim heap whose size is its nimber (Grundy value) CF(n). These nimbers satisfy
CF(1) = CF(2) = 0,
CF(n) = mex { CF(i) ⊕
CF(n−i) : 1 ≤ i ≤
⌊n/2⌋ } for n ≥ 3,
where ⊕ is the bitwise exclusive or and mex is the least non-negative integer that
does not belong to the set. The first values are
CF(1), CF(2), … = 0, 0, 1, 2, 0, 1, 2, 3, 1, 2, 3, 4, 0, …
The data below contain CF(n) for 1 ≤ n ≤ 100,000,003;
in CF.txt.xz, line n holds CF(n).
The largest value in this range is 325.
