Appendix B4
Estimating Euler Lengths
The construction algorithm presented in detail in Chapter 2 may be used in its unrestricted standard format in order to search exhaustively for Euler representations. However, there are a number of different ways of modifying the algorithm so that the search space is greatly reduced, in the hope that other representations providing reasonable upper bounds may still be found.
The algorithm may be considered to be a recursive function within a main loop. The first modification is to introduce an early abort, whereby each iteration of the main loop must produce an intermediate result at least as good as the previous, otherwise we drop back up to the previous level of recursion. The second modification is to cap the number of iterations allowed at each level of recursion. The third, and simplest, method, is to end the loop at 1 rather than 0. These modifications can be used separately and together in various combinations to produce a set of variants that each walk through different restrictions to the total search space. The algorithm also allows the initial estimate to be altered, which further restricts the search space. However, in this last case, selecting too low an initial estimate may cause a good solution to be missed.
I have found that switching between different variants, using any previous best upper bound as an initial estimate for each new run, will, within a few minutes execution time for each method, quickly produce a reasonable estimate, which may then be used to speed up the unmodified algorithm, or, alternatively, be used as an upper bound for Meyrignac's program Euler2000.
In this way, a tables of estimates can be built up, which itself may give suggestions as to initial estimates for larger bases.
The best results I have obtained, most recent first, are :
14/08/2000 : a solution for (23,1,434) with base x = 48 :
4823 = (47, 46, 38, 37, 35, 33, 31, 29, 28, 4x26, 25, 24, 2x23, 3x22, 2x20, 19, 18, 17, 6x16, 3x15, 5x14, 10x13, 6x12, 11, 2x10, 11x9, 12x8, 10x7, 19x6, 41x5, 52x4, 182x3, 18x2, 31x1)23
09/08/2000 : a solution for (31,1,11265) with base x = 33 :
3331 = (2x32, 31, 30, 29, 2x28, 27, 26, 25, 3x24, 3x23, 2x21, 19, 2x18, 10x17, 8x16, 15, 12x14, 15x13, 19x12, 28x11, 3x10, 6x9, 56x8, 100x7, 109x6, 121x5, 1212x4, 1490x3, 7076x2, 978x1)31
21/06/2000 : a solution for (26,1,869) with base x = 27 :
2726 = (2x26, 25, 2x24, 23, 2x21 ,6x20, 3x19, 14x18, 5x17, 5x16, 11x15, 5x14, 6x13, 4x12, 9x11, 9x10, 35x9, 6x8, 29x7, 23x6, 5x5, 195x4, 193x3, 141x2, 157x1)26
15/06/2000 : a solution for (32,1,6038) with base x = 31 :
3132 = (2x30, 2x29, 28, 2x27, 24, 23, 22, 3x20, 6x19, 18, 2x17, 10x16, 9x15, 2x14, 17x13, 14x12, 32x11, 10, 9x9, 16x8, 78x7, 55x6, 547x5, 43x4, 3769x3, 1407x2, 7x1)32
12/05/2000 : a solution for (27,1,1059) with base x = 35 :
3527 = (2x34, 2x31, 4x28, 26, 25, 2x22, 4x21, 5x20, 3x19, 4x18, 17, 5x16, 10x15, 7x14, 2x13, 8x12, 15x11, 11x9, 19x8, 41x7, 44x6, 190x5, 96x4, 380x3, 21x2, 181x1)27
09/05/2000 : a solution for (27,1,1363) with base x = 30 :
3027 = (2x29, 28, 26, 3x25, 23, 5x21, 3x20, 6x19, 8x17, 16, 8x15, 8x14, 5x13, 17x12, 18x10, 22x9, 6x8, 26x7, 106x6, 17x5, 54x4, 627x3, 324x2, 94x1)27
04/05/2000 : a solution for (28,1,1975) with base x = 35 :
3528 = (34, 2x33, 32, 31, 3x30, 2x29, 28, 4x27, 2x26, 5x25, 24, 2x23, 2x22, 3x21, 3x20, 2x19, 2x18, 2x17, 10x16, 2x15, 14, 5x13, 2x12, 16x11, 11x10, 30x9, 42x8, 56x7, 88x6, 156x5, 454x4, 127x3, 742x2, 194x1)28
04/05/2000 : a solution for (28,1,2612) with base x = 36 :
3628 = (2x35, 33, 29, 28, 4x26, 25, 4x23, 4x22, 2x21, 3x20, 7x18, 16, 5x15, 14, 5x13, 3x12, 2x11, 22x10, 21x9, 15x8, 46x7, 146x6, 13x5, 268x4, 1203x3, 697x2, 134x1)28
02/05/2000 : a solution for (29,1,3989) with base x = 40 :
4029 = (2x39, 35, 2x34, 2x31, 30, 26, 23, 2x20, 5x19, 7x17, 9x16, 7x15, 6x14, 13, 18x12, 11, 6x10, 12x9, 19x8, 26x7, 115x6, 319x5, 337x4, 488x3, 1131x2, 1470x1)29