On 7/23/10, Fred lunnon <fred.lunnon@gmail.com> wrote:
For the counts f_3(n) of interleaving words in m = 3 dimensions, of length n for n = 0, ..., 8, I propose the values:
1, 3, 9, 27, 75, 189, 447, 951, 1911 ...
Value f_3(8) = 1911 further confirmed by 2-hour run of a million trials. If the words are assumed to be uniformly distributed, the expected number of trials to find all X = f_m(n) should be about X log X, by a standard cigarette card / Pokemon token collecting argument. The program performance is substantially worse, because uniform distribution of AP's skews words away from those with long blocks of fewer than m symbols: the situation might be improved by skewing the AP's deliberately to counterbalance the effect, but it's a delicate business. More satisfactory would be a viable deterministic algorithm! WFL