[r-t] Bobs only Erin Triples (was: Composition search)

Richard Smith 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 
Penryn microarchitecture.

On average each of the 120 search processes took 17 minutes 
to complete and none exceeded 40 minutes.  No blocks were 
found.

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.

RAS




More information about the ringing-theory mailing list