[r-t] Bobs only Erin Triples (was: Composition search)
richard at ex-parrot.com
Sat Nov 28 08:52:56 UTC 2015
Philip Earis wrote:
> I think Richard has ruled out a perfect 7-part
> composition, and possibly further - I'm sure he'll be able
> to confirm.
As I mentioned the other day, I'm not sure I did. I looked
at the rather meagre notes I made when I last investigated
this, and there's no indication that I did eliminate it and
I made several comments about it perhaps being beyond the
scope of a reasonable search.
So I decided to take another look at it. The code I wrote
on Wednesday is considerably better than any of the previous
generations of search code I've used, in a significant part
because I cracked the problem of how to do efficient
rotation pruning in a multi-part search and in doing so came
up with a good way of parallelising the search.
As I speculated on Wednesday, this is done by applying the
normal one-part rotation pruning algorithm to a multi-part
search, and repeating for each conjugate part-end group.
In the case of the 7-part search, there are 120 conjugate
part-end groups which naturally divides the search space
into 120 roughly equal chunks. This is much more even
division than dividing by search prefix, especially in the
presence of rotation pruning, and there was less than a
factor of 2.5 difference between the largest and smallest of
the 120 searches. As no communication is required between
120 search processes, there's no need for multi-threading,
and they can be run independently on separate machines.
Increased computer speeds have helped too. Ten years ago,
which is the last time I seriously studied this, I used a
single-core 800 MHz processor; now even my laptop has a
dual-core 1.9 GHz processor, and the machines I actually
used had 2.66 GHz processors. But the clock speed (and
extra core) is not representative of the actual speed
increase, and in fact my laptop (with an 1.9 Ghz Intel
i3-3227U processor) ran the code about 1.95 times as fast as
the machines I actually used (with a 2.66 GHz Intel P8800
processor). This is because the Ivy Bridge
microarchitecture in my laptop is that much faster than the
On average each of the 120 search processes took 17 minutes
to complete and none exceeded 40 minutes. No blocks were
I also checked all larger part-end groups. The part-end
group cannot contain any elements conjugate to the in-course
falseness (i.e. a simple 3-cycle) which severely limits the
available part structures. If a multi-part bobs-only
extent of Erin exists, then the number of parts
must be one of 168, 60, 24, 21, 20, 12, 10, 8, 7, 6, 5, 4,
3, 2 or 1. I have now eliminated the 7-part and all larger
options. None even produced a set of mutually true blocks.
In fact, I think we can rule out several of these structures
on Q-set grounds: specifically the 168, 60, 24 and 8 part
structures. But I'd need to think a bit harder about it to
be certain. The point is moot anyway.
More information about the ringing-theory