# Nimber sequence CF of *Couples-are-Forever* up to 10^8

Data and statistical analyses for the sequence `CF` of nimbers (Grundy values) of the
combinatorial game *Couples-are-Forever*, computed for `CF(1), ..., CF(100000003)`.

## 

## Definition

`CF(1) = CF(2) = 0` and, for `n >= 3`,

&#x20;   CF(n) = mex { CF(i) xor CF(n-i) : 1 <= i <= floor(n/2) },



where `xor` is the bitwise exclusive or and `mex` is the least non-negative integer not in
the set. The first values are `CF(1), CF(2), ... = 0, 0, 1, 2, 0, 1, 2, 3, 1, 2, 3, 4, 0, ...`.
`CF(n)` is the nimber of *Couples-are-Forever* of size `n`. In the published files the value at index 0 is a placeholder
(`CF\\\[0] = 0`); the recurrence never uses it.

## 

## Results

Everything in this section is a statement about the computed range, except the part
explicitly marked as proved.

### Proved (consequence of the definition)

Since `CF(m)` is a mex, it is not in the set `{CF(i) xor CF(m-i)}`; taking `i = a` gives, for
every `1 <= a <= floor(m/2)` and `m >= 3`,

&#x20;   CF(m) xor CF(m-a) != CF(a).



In particular, if `CF(a) = 0` then `CF(m) != CF(m-a)` for all `m >= 2a`: the lags equal to the
positions of the value 0 are forbidden. With `a = 1, 2` this shows that two equal values
are always at distance at least 3 (apart from the base case `CF(1) = CF(2) = 0`).

### Observed

* **Values** The maximum is 325,
attained once (at `i = 19,739,544`).
The value 0 occurs only at `i = 0` (placeholder), 1, 2, 5, 13, 21, 31, 47, 73, 99, 125,
151, 177, 315 and 409.
* **Support rule.** For `i >= 10^5`, a value `v` occurs only if `popcount(v \\\& 0x1EE)` is
odd (`0x1EE = 111101110` in binary). The exceptions are 1,585 occurrences of 116 distinct
values, all at `i <= 20,628` (the last one is the value 277 at `i = 20,628`). Column
`in\\\_rule` of the CSV marks the values that satisfy the rule.
* **Gaps between consecutive occurrences of the same value.** The minimum gap is 3 for every value. The same gaps
dominate for all values: among the 142 values that occur at least 2000 times, 23 and 26
are among the six most frequent gaps for all of them, 3 for 141 of them and 20 for 138
of them (other frequent gaps: 6, 17, 46, 43, 9).
* **Lag spectrum**.
`P(k) = Pr\\\[CF(i+k) = CF(i)]` for `1 <= k <= 20000`, over 100M positions
`i >= 10^6`; the baseline for independent values is 1.158%.
`P(k) = 0` exactly for the lags 1, 2, 5, 13, 21, 31, 47, 73, 99, 125, 151, 177, 315, 409
(the positions of 0, as proved above); the largest values are about 8.6%.
The peaks come in triples `(c-3, c, c+3)` centered near `nT` with the **non-integer**
period `T \\\~ 22.415`; the height of the groups oscillates with period `\\\~ 319.3` lags
(about 14.25 groups) and again with period `\\\~ 12,100`. The strongest fine frequencies are
`(1 + m/T)/3` for `m = 1, -2, 4, -5`. These periods are numerical estimates
(`T = 22.4150` was refined on a prefix of 10^7 terms). We have no theoretical explanation
of them yet.

###