appendb1

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

Additionally,

* 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.

URL : www.glasgowg43.freeserve.co.uk/appendb1.htm