Appendix B1

Estimates for Euler lengths

The following tables give estimates and the actual values, for Euler lengths to the power m for m between 5 and 22, and for base x = 4 as high as possible.

The legend is as follows:

#1 = no loop cap

#2 = no loop cap, amended to start from 1

#3 = standard

#4 = standard, amended loop start from 1

#5 = actual value / current best

* indicates where the amended version of either algorithm gives a better result

\$ indicates where the standard algorithm gives a better result than without loop capping

^ indicates where removing the loop capping gives the better estimate

= indicates where the actual value is less than any estimate

As x rises, the condition of the amended versions of the algorithm, that each lesser power appears at least once in the Euler representation, becomes too restrictive, since often the loop cap at any given point will be zero and so the loop is never entered. At this value of x, the initial feed value cannot be improved upon. Where this happens, a line of dashes is placed in the table entry at the appropriate point. Note that as m rises, the onset of this effect is delayed.

The reason that the versions with no loop capping are given first is that, historically, this was the first method used, and it was not until later that the tighter bound was used, which, as can be seen, allows us to push the base x higher given the same computing resources.

 x 5, #1 5, #2 5, #3 5, #4 5, #5 6, #1 6, #2 6, #3 6, #4 6, #5 4 19 19 19 19 19 15 15 15 15 15 5 18 18 18 18 18 29 29 29 29 29 6 14 14 14 14 14 22 22 22 22 22 7 12 12 12 12 12 21 35 21 35 21 8 9 20 9 20 9 15 23 15 23 15 9 11 --------- 11 --------- 11 22 23 22 23 = 19 10 9 --------- 9 --------- 9 15 23 15 23 15 11 13 --------- 13 --------- 13 17 --------- 17 --------- 17 12 6 --------- 6 --------- 6 15 --------- 15 --------- 15 13 12 --------- 12 --------- 12 16 --------- 16 --------- 16 14 8 --------- 8 --------- 8 14 --------- 14 --------- 14 15 10 --------- 10 --------- 10 15 --------- 15 --------- 15 16 11 --------- 11 --------- = 9 13 --------- 13 --------- 13 17 8 --------- 8 --------- 8 12 --------- 12 --------- 12 18 10 --------- 10 --------- 10 11 --------- 11 --------- 11 19 10 --------- 10 --------- 10 11 --------- 11 --------- 11 20 9 --------- 9 --------- 9 13 --------- 13 --------- 13 21 10 --------- 10 --------- 10 14 --------- 14 --------- 14 22 10 --------- 10 --------- 10 13 --------- 13 --------- = 12 23 7 --------- 7 --------- 7 15 --------- \$ 13 --------- 13 24 6 --------- 6 --------- 6 13 --------- 13 --------- 13 25 10 --------- 10 --------- = 9 15 --------- 15 --------- = 12 26 7 --------- 7 --------- 7 12 --------- 12 --------- 12 27 9 --------- 9 --------- 9 13 --------- 13 --------- = 12 28 8 --------- 8 --------- 8 12 --------- 12 --------- 12 29 9 --------- 9 --------- 9 12 --------- 12 --------- 12 30 6 --------- 6 --------- 6 11 --------- 11 --------- 11 31 9 --------- 9 --------- 9 --------- 11 --------- 11 32 6 --------- 6 --------- 6 --------- 12 --------- = 11 33 8 --------- 8 --------- 8 --------- 11 --------- 11 34 7 --------- 7 --------- 7 --------- 11 --------- 11 35 --------- 7 --------- 7 --------- 13 --------- 13 36 --------- 6 --------- 6 --------- 11 --------- 11 37 --------- 8 --------- 8 --------- 11 --------- 11 38 --------- 7 --------- 7 --------- 12 --------- = 11 39 --------- 8 --------- 8 --------- 11 --------- = 10 40 --------- 7 --------- 7 --------- 12 --------- = 11

 x 7, #1 7, #2 7, #3 7, #4 7, #5 8, #1 8, #2 8, #3 8, #4 8, #5 4 66 66 66 66 66 121 121 121 121 121 5 39 39 39 39 39 85 85 85 85 = 80 6 36 36 36 36 = 28 55 55 55 55 55 7 26 26 26 26 26 40 65 40 65 40 8 21 21 21 21 21 47 47 47 47 = 44 9 25 28 25 28 = 20 34 44 34 44 34 10 23 39 23 39 = 18 41 45 41 45 = 40 11 22 22 22 22 22 44 51 44 51 = 40 12 24 -------- 24 -------- = 22 34 41 34 41 34 13 23 -------- 23 -------- = 22 38 63 38 63 38 14 25 -------- 25 -------- = 20 36 -------- 36 -------- 36 15 23 -------- \$ 21 -------- 21 37 -------- 37 -------- = 36 16 14 -------- 14 -------- 14 36 -------- 36 -------- = 34 17 19 -------- 19 -------- = 17 37 -------- 37 -------- = 17 18 14 -------- 14 -------- 14 36 -------- \$ 35 -------- = 34 19 14 -------- 14 -------- 14 36 -------- 36 -------- = 29 20 19 -------- 19 -------- = 17 36 -------- 36 -------- = 34 21 17 -------- 17 -------- = 16 36 -------- 36 -------- = 27 22 17 -------- 17 -------- 17 34 -------- 34 -------- = 33 23 14 -------- 14 -------- 14 34 -------- 34 -------- = 29 24 16 -------- 16 -------- 16 33 -------- 33 -------- 33 25 13 -------- 13 -------- 13 35 -------- 35 -------- = 32 26 16 -------- 15 -------- 15 33 -------- 33 -------- 27 13 -------- 13 -------- 13 34 -------- 34 -------- 28 12 -------- 12 -------- 12 -------- 34 -------- 29 15 -------- 15 -------- 15 -------- 19 -------- 30 13 -------- 13 -------- 13 -------- 34 -------- 31 15 -------- 15 -------- 15 -------- 27 -------- 32 14 -------- 14 -------- = 13 -------- 33 -------- 33 -------- 14 -------- 14 -------- 29 -------- 34 -------- 13 -------- 13 -------- 33 -------- 35 -------- 14 -------- 14 -------- --------

 x 9, #1 9, #2 9, #3 9, #4 9, #5 10,#1 10,#2 10, #3 10, #4 10, #5 4 146 146 146 146 146 199 199 199 199 199 5 32 32 32 32 32 188 188 188 188 188 6 102 102 102 102 102 144 144 144 144 144 7 67 67 67 67 67 122 122 122 122 122 8 72 72 72 72 = 63 133 133 133 133 = 89 9 46 46 46 46 46 67 78 67 78 = 56 10 44 73 44 73 = 32 111 * 56 111 * 56 56 11 53 64 53 64 = 37 44 66 44 66 44 12 50 59 50 59 = 42 45 68 45 68 = 34 13 35 46 35 46 = 33 46 79 46 79 46 14 42 55 \$ 41 55 = 34 50 68 50 68 = 39 15 29 -------- 29 -------- 29 23 68 23 68 23 16 29 -------- 29 -------- 29 46 -------- 46 -------- = 34 17 32 -------- \$ 29 -------- 29 36 -------- 36 -------- = 34 18 29 -------- 29 -------- = 27 36 -------- ^ 45 -------- = 34 19 26 -------- ^ 28 -------- 26 37 -------- \$ 35 -------- = 33 20 24 -------- 24 -------- 24 34 -------- 34 -------- 34 21 23 -------- 23 -------- = 16 23 -------- 23 -------- 23 22 26 -------- 26 -------- = 25 33 -------- 33 -------- 33 23 19 -------- 19 -------- 19 34 -------- 34 -------- = 32 24 19 -------- 19 -------- 19 34 -------- 34 -------- 34 25 23 -------- 23 -------- = 20 34 -------- 34 -------- = 26 26 19 -------- 19 -------- = 15 24 -------- 24 -------- 27 18 -------- 18 -------- 18 34 -------- 34 -------- 28 21 -------- 21 -------- 21 -------- 27 -------- 29 21 -------- ^ 24 -------- 21 -------- 26 -------- 30 17 -------- ^ 19 -------- 17 -------- 26 -------- 31 -------- 19 -------- 19 -------- -------- 32 -------- 21 -------- = 18 -------- -------- 33 -------- -------- 19 -------- -------- 34 -------- -------- 19 -------- -------- 35 -------- -------- 18 -------- -------- 36 -------- -------- 17 -------- -------- 37 -------- -------- 17 -------- -------- 38 -------- -------- 18 -------- -------- 39 -------- -------- 19 -------- -------- 40 -------- -------- 18 -------- --------

 x 11,#1 11,#2 11, #3 11, #4 11, #5 12,#1 12,#2 12, #3 12, #4 12, #5 4 277 277 277 277 277 911 911 911 911 911 5 850 850 850 850 = 137 820 820 820 820 = 365 6 291 291 291 291 = 145 547 547 547 547 = 456 7 51 166 51 166 51 196 196 196 196 196 8 88 88 88 88 88 404 404 404 404 = 157 9 105 * 92 105 * 92 = 70 274 * 157 274 * 157 = 118 10 103 103 103 103 = 85 79 157 79 157 = 66 11 105 150 105 150 = 75 92 105 92 105 = 79 12 64 64 64 64 = 61 66 131 66 131 66 13 55 66 55 66 = 52 78 104 78 104 78 14 65 84 \$ 38 84 38 81 119 81 119 = 66 15 53 92 53 \$ 90 = 46 66 93 66 ^ 107 66 16 42 76 \$ 40 76 40 66 81 66 81 = 54 17 46 85 ^ 52 85 46 79 108 ^ 92 108 = 53 18 45 -------- 45 -------- = 39 79 106 \$ 44 106 44 19 41 -------- \$ 38 -------- 38 54 -------- \$ 42 -------- 42 20 42 -------- 42 -------- 42 66 -------- 66 -------- = 46 21 44 -------- \$ 39 -------- = 39 57 -------- \$ 53 -------- = 42 22 35 -------- ^ 40 -------- 35 53 -------- 53 -------- = 44 23 41 -------- 41 -------- = 36 -------- 54 -------- = 40 24 38 -------- 38 -------- = 35 -------- 40 -------- 25 -------- 43 -------- = 31 -------- 40 -------- 26 -------- 33 -------- -------- 46 -------- 27 -------- 37 -------- -------- 43 -------- 28 -------- 31 -------- -------- -------- 29 -------- 31 -------- -------- -------- 30 -------- 31 -------- -------- --------

 x 13, #1 13, #2 13, #3 13, #4 13, #5 14, #1 14, #2 14, #3 14, #4 14, #5 4 2247 2247 2247 2247 = 1669 4559 4559 4559 4559 4559 5 1088 1088 1088 1088 = 1088 4130 4130 4130 4130 = 2644 6 1348 * 1055 1348 * 1055 = 894 3855 3855 3855 3855 = 1766 7 1046 1046 1046 1046 = 727 3597 3597 3597 3597 = 1270 8 999 999 999 999 = 605 3421 3421 3421 3421 = 769 9 976 976 976 976 = 554 3043 3043 3043 3043 = 587 10 950 951 950 951 = 479 2907 2921 2907 2921 = 490 11 879 930 879 930 = 428 2792 2879 2792 2879 = 404 12 882 888 882 888 = 397 2498 * 2334 2498 * 2334 = 313 13 820 828 820 828 = 363 2060 2268 2060 2268 = 267 14 823 * 776 823 * 776 = 322 2152 * 2037 2152 * 2037 = 225 15 791 823 791 823 = 306 1546 1669 1546 1669 16 766 * 763 766 * 763 = 289 919 1469 919 1469 = 883 17 734 754 734 754 1039 1137 1039 1137 18 697 750 697 750 547 962 547 962 19 723 726 723 726 577 599 577 599 20 749 749 505 505 21 -------- -------- 537 537 22 -------- -------- -------- -------- 23 -------- -------- -------- -------- 24 -------- -------- -------- -------- 25 -------- -------- -------- -------- 26 -------- -------- -------- -------- 27 -------- -------- -------- -------- 28 -------- -------- -------- -------- 29 -------- -------- -------- -------- 30 -------- -------- -------- --------

 x 15, #1 15, #2 15, #3 15, #4 15, #5 16, #1 16, #2 16, #3 16, #4 16, #5 4 4039 4039 4039 4039 4039 11136 11136 11136 11136 = 8246 5 4294 4294 4294 4294 = 1697 8110 8110 8110 8110 = 3605 6 3717 3717 3717 3717 = 791 3503 3503 3503 3503 = 851 7 3086 3086 3086 3086 = 731 1412 1412 1412 1412 = 443 8 2174 2174 2174 2174 = 343 1140 1140 1140 1140 = 528 9 532 532 532 532 = 272 579 579 579 579 = 341 10 585 585 585 585 = 210 834 834 834 834 = 324 11 318 318 318 318 = 159 851 851 851 851 = 239 12 276 300 276 300 = 140 290 307 290 307 = 222 13 169 * 153 169 * 153 = 109 324 494 324 494 324 14 202 202 202 202 290 290 290 *\$ 273 15 169 222 \$ 157 \$ 201 188 341 ^ 205 341 16 166 176 \$ 127 ^ 198 171 273 171 \$ 205 17 130 151 \$ 127 ^ 180 238 * 187 238 * 187 18 118 * 96 118 * 96 139 240 139 240 19 120 150 120 \$ 142 103 189 103 189 20 114 132 ^ 116 ^ 138 122 122 ^ 205 * 122 21 109 127 \$ 106 127 121 138 121 138 22 133 92 133 156 120 ^ 189 23 142 84 142 158 105 \$ 140 24 -------- 83 -------- 104 160 25 -------- -------- -------- -------- 26 -------- -------- -------- -------- 27 -------- -------- -------- -------- 28 -------- -------- -------- -------- 29 -------- -------- -------- -------- 30 -------- -------- -------- --------

 x 17, #1 17, #2 17, #3 17, #4 17, #5 18, #1 18, #2 18, #3 18, #4 18, #5 4 33366 33366 33366 33366 = 7976 9843 9843 9843 9843 9843 5 31716 31716 31716 31716 = 2602 10109 10109 10109 10109 10109 6 11910 11910 11910 11910 = 1586 11572 11572 11572 11572 = 2794 7 9600 9600 9600 9600 = 1192 8323 11515 8323.00 11515 = 1939 8 11037 11037 11037 11037 = 842 4884 6556 4884 6556 9 911 911 911 911 2585 2585 2585 2585 10 1217 1217 1217 1217 1977 1977 1977 1977 11 495 495 495 495 837 1825 837 1825 12 579 579 \$ 419 ^ 596 989 989 989 989 13 455 561 ^ 561 561 723 970 723 970 14 391 391 ^ 453 ^ 453 723 1027 723 1027 15 388 * 325 388 *^ 344 362 419 362 419 16 240 240 ^ 274 *\$ 188 362 362 362 362 17 238 289 \$ 225 ^ 294 286 400 \$ 191 400 18 236 264 \$ 210 *\$ 202 267 267 267 267 19 144 251 ^ 176 \$ 193 285 323 285 \$ 285 20 170 * 166 \$ 166 166 269 382 \$ 249 \$ 268 21 241 166 \$ 203 230 250 ^ 249 22 127 241 210 230 23 137 248 230 24 212 213 25 206 26 241 27 -------- -------- 28 -------- -------- -------- -------- 29 -------- -------- -------- -------- 30 -------- -------- -------- --------

 x 19, #1 19, #2 19, #3 19, #4 19, #5 20, #1 20, #2 20, #3 20, #4 20, #5 4 62437 62437 62437 62437 =34442 137776 137776 137776 137776 =72876 5 23066 23066 23066 23066 =17339 8350 8350 8350 8350 8350 6 22045 22045 22045 22045 32088 32088 32088 32088 7 2633 2633 2633 2633 14895 14895 14895 14895 8 4439 4439 4439 4439 20373 20373 20373 20373 9 2020 2020 2020 2020 10462 10462 10462 10462 10 2851 2851 2851 2851 7998 7998 7998 7998 11 1325 1325 1325 1325 1408 1408 1408 1408 12 1332 2067 1332 2067 1898 1898 1898 1898 13 1147 1147 1147 1147 1540 1540 1540 1540 14 420 420 420 420 1160 * 676 1160 * 676 15 593 601 ^ 646 ^ 835 811 811 811 811 16 417 466 417 466 1120 * 780 1120 * 780 17 347 389 ^ 581 *^ 426 742 743 ^ 746 * 743 18 383 544 \$ 341 \$ 400 455 * 366 ^ 558 ^ 558 19 318 * 292 \$ 269 ^ 437 498 498 ^ 523 ^ 642 20 299 299 \$ 268 ^ 302 256 415 256 ^ 494 21 281 298 *^ 290 370 377 * 370 22 267 * 263 370 310 \$ 311 23 279 292 24 273 349 25 26 27 28 29 -------- -------- 30 -------- -------- 31 -------- -------- -------- --------

 x 21, #1 21, #2 21, #3 21, #4 21, #5 22, #1 22, #2 22, #3 22, #4 22, #5 4 76052 76052 76052 76052 76052 40182 40182 40182 40182 40182 5 88266 88266 88266 88266 =22781 467637 467637 467637 467637 =45104 6 99923 *33791 99923 *33791 186807 186807 186807 186807 7 48097 48097 48097 48097 46116 46116 46116 46116 8 30631 30631 30631 30631 31902 31902 31902 31902 9 5630 5630 5630 5630 26957 26957 26957 26957 10 12838 * 8925 12838 * 8925 21690 *14169 21690 *14169 11 6083 13896 6083 13896 2738 2738 2738 2738 12 4688 4688 4688 4688 2439 2439 2439 2439 13 2196 4148 2196 4148 2991 2991 2991 2991 14 2763 2763 2763 2763 2462 * 1956 2462 * 1956 15 1528 1711 1528 1711 3635 * 875 3635 * 875 16 966 1356 966 1356 1151 1151 ^ 1243 ^ 1381 17 656 1021 656 1021 1082 1519 \$ 990 1519 18 677 677 677 677 1197 1197 ^ 1427 *^1404 19 665 499 665 645 1197 *^ 806 20 569 398 ^ 812 760 691 *\$ 576 21 363 528 461 645 22 406 530 530 23 24 25 26 27 28 29 30

The results given in the next table are the best currently known using loop iteration caps and no loop abort.

* indicates that the bound is also the actual length of an Euler representation

^ indicates that the result was obtained using an iteration cap larger than the suggested maximum

? indicates that the result is likely to be exact but has not been verified

All the results in this table were obtained after only a few minutes processing.

 x m = 13 m = 14 m = 15 m = 16 m = 17 m = 18 m = 19 m = 20 m = 21 m = 22 4 * 1669 * 4559 * 4039 * 8246 * 7976 * 9843 * 34442 * 72876 * 76052 * 40182 5 * 1088 * 2644 * 1697 * 3605 * 2602 * 10109 * 17339 * 8350 * 22781 * 45104 6 * 894 * 1766 * 791 * 851 * 1586 * 2794 ? 3326 ? 6535 ? 5249 ? 16216 7 ^ 806 ^ 1458 * 731 * 443 * 1192 * 1939 ? 2546 3048 4555 8557 8 ^ 841 ^ 2034 ^ 477 * 528 ? 842 ? 1179 ? 691 1904 3633 3405 9 ^ 860 ^ 1915 ^ 362 *^ 341 646 723 886 1453 3460 3773 10 ^ 1027 ^ 2099 299 * 324 440 438 916 958 1753 1703 11 1054 ^ 2890 * 159 341 486 438 746 924 1880 2347 12 1008 4910 154 * 222 484 704 773 1017 2006 2255

All the results in this table were obtained using the standard method with loop abort and iteration capping using only a few minutes execution time. Only results better than those obtained using the standard methods are given.

 x m = 13 m = 14 m = 15 m = 16 m = 17 m = 18 m = 19 m = 20 m = 21 m = 22 6 2905 9444 77511 7 3586 2509 8 3206 1886 6982 3659 * 4111 23783 9 884 389 10 878 519 732 716 1635 5201 11 876 * 2339 647 * 761 4421 12 852 897 13 868 1183 14 1725 239 * 400 * 2018 15 484 576 16 393 17 153 * 298 653 * 599 18 326 * 323 * 625 944

As a demonstration of the effect of iteration capping, appendix B2 and appendix B3 give the bounds obtained using the extended method with loop abort for length of the Euler representation for a variety of cap values and powers.

Note that as the cap value rises, the trend is for the upper bound to gradually fall, bottom out, and then level out at the normal value. This is expected as the cap tends to reach an optimum level and then as it increases further its effect diminishes until it might as well not be in force.