The Chase
Algorithms
Side
This algorithm produces all numbers having the same total stopping time than a given seed, using the coalescence of threads described in a `2^n` basis.
For example in basis 16:
`{:(16x,rarr,8x,rarr,4x,rarr,2x,rarr,x),
(16x+1,rarr,24x+2,rarr,12x+1,rarr,18x+2,rarr,9x+1),
(16x+2,rarr,8x+1,rarr,12x+2,rarr,6x+1,rarr,9x+2),
(16x+3,rarr,24x+5,rarr,36x+8,rarr,18x+4,rarr,9x+),
(16x+4,rarr,8x+2,rarr,4x+1,rarr,6x+2,rarr,3x+1),
(16x+5,rarr,24x+8,rarr,12x+4,rarr,6x+2,rarr,3x+1),
(16x+6,rarr,8x+3,rarr,12x+5,rarr,18x+8,rarr,9x+4),
(16x+7,rarr,24x+11,rarr,36x+17,rarr,54x+26,rarr,27x+13),
(16x+8,rarr,8x+4,rarr,4x+2,rarr,2x+1,rarr,3x+2),
(16x+9,rarr,24x+14,rarr,12x+7,rarr,18x+11,rarr,27x+17),
(16x+10,rarr,8x+5,rarr,12x+8,rarr,6x+4,rarr,3x+2),
(16x+11,rarr,24x+17,rarr,36x+26,rarr,18x+13,rarr,27x+20),
(16x+12,rarr,8x+6,rarr,4x+3,rarr,6x+5,rarr,9x+8),
(16x+13,rarr,24x+20,rarr,12x+10,rarr,6x+5,rarr,9x+8),
(16x+14,rarr,8x+7,rarr,12x+11,rarr,18x+17,rarr,27x+26),
(16x+15,rarr,24x+23,rarr,36x+35,rarr,54x+53,rarr,81x+80):}`
Thus, those properties:
- `16x+2` and `16x+3` have the same Total Stopping Time.
- `16x+4` and `16x+5` have the same Total Stopping Time.
- `16x+8` and `16x+10` have the same Total Stopping Time.
- `16x+12` and `16x+13` have the same Total Stopping Time.
The current Side algorithm uses an `2^(19)` (524288) basis: 393904 properties
Up and Down
Up and Down algorithms use the properties of general threads built in a `2^n*3^p` basis.
Those threads link equivalence classes with `U`, `D`, `T` and `B` functions:
`2^n3^p*x+ a \stackrel"thread"rarr 2^(n’)3^(p’)*x+ b`
A local completeness is defined by `(p’-p)/(n’-n)`.
As all (good) candidates have a completeness above 0,6, any local completeness above 0,6 doesn’t reduce the potential of the generated candidates using this thread.
For example:
`8x+3 \stackrel"U"rarr 12x+5 \stackrel"U"rarr 18x+8 \stackrel"D"rarr 9x+4`
The local completeness is of `2//3 gt 0,6`
`48x+24 \stackrel"D"rarr 24x+12 \stackrel"D"rarr 12x+6 \stackrel"D"rarr 6x+3 \stackrel"U"rarr 9x+5 \stackrel"T"rarr 18x+10 \stackrel"T"rarr 36x+20 \stackrel"B"rarr 24x+13 \stackrel"T"rarr 48x+26 \stackrel"B"rarr 32x+17`
The local completeness is `1 gt 0,6`
Down:
if `(8x+3)` is a good candidate of Total stopping time `s`, `(9x+4)` is a good candidate of Total stopping time `s-3`
if `(32x+17)` is a good candidate of Total stopping time `s`, `(48x+24)` is a good candidate of Total stopping time `s-1`
Up:
if `(9x+4)` is a good candidate of Total stopping time `s`, `(8x+3)` is a good candidate of Total stopping time `s+3`
if `(48x+24)` is a good candidate of Total stopping time `s`, `(32x+17)` is a good candidate of Total stopping time `s+1`
Currently the algorithms use all properties for basis bellow 600000, there are 326 of them.
Dive
The Dive algorithm is using brute force to search for new candidates at the level immediately bellow the current candidate,
so it tries for a candidate `x` all numbers between `x/3-d` and `x/3+d`, `d` being the width of the search.
If the candidate is not the absolute record for it’s total stopping time and its residue, we will eventually find a `y` in the area of `x/3` having the same total stopping time.
Strategy
The strategy is to improve a set of good candidate loop the following process:
- Run Side, Up and Down until no new candidates are generated.
- In the process the number of candidate is multiplied by several hundreds. Clean the set of candidates by discarding all candidates under presets level limits.
- Run Dive with increasing width until a new candidate is found or maximum width is reached.
- Clean the set of candidates by discarding all candidates included in another candidate’s Dive search interval.
Limits
Candidates generation is currently limited to 3 levels bellow local record (of the same residue) and 5 levels bellow global record (any residue)
Candidates generation is currently limited to Class 20000.