Otros resultados

Similar problems

Langton's Ant on a torus

When Langton's Ant is ran on a finite grid with wrapping edges, there is a finite number of states the map can be in and thus, the ant must exhibit a periodic behaviour. The following table shows the iterations it takes for the map to reset back to zero for different map sizes. These periods do not take into account the final position of the ant. If the ant doesn't finish in the same position or orientation, the number in brackets will show how many times it has to repeat to go back to the initial position, and in the second row, the true period. For all maps the ant will start in the up direction, this is only important for rectangular maps.

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51	52	53	54	55	56	57	58	59	60	61	62	63	64
1	2	4	6	8	10	12	14	16	18	20	22	24	26	28	30	32	34	36	38	40	42	44	46	48	50	52	54	56	58	60	62	64	66	68	70	72	74	76	78	80	82	84	86	88	90	92	94	96	98	100	102	104	106	108	110	112	114	116	118	120	122	124	126	128
2	[2] 2 4	8	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	32	32	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16
3	[3] 2 6	8	[3] 22 66	72	[3] 318 954	196	208	3008	6064	304	[3] 23086 69258	246400	400	29404	[3] 455518 1366554	496	[3] 3154588 9463764	10930388	592	30519840	70930202	688	[3] 20542756 61628268	477526912	784	363496056	[3] 5627546592 16882639776	880	[3] 31672079480 95016238440	116172994252	1952	89001498224	801163066354	1072	[3] 56941161464 170823484392	10406505035992	1168	2161637491684	17435111778612	1264	101435064150558	50435525447888	1360	> 875830000000000		1456			1552			1648			1744			1840			1936			2032
4	[4] 2 8	8	[2] 28 56	96	624	696	[2] 1724 3448	2336	13360	2608	171296	78672	206504	1137192	71720	13988800	9123112	55697168	35079376	60632672	159287544	3246498160	3572855600	6820117568	80657175256	31571358000	172932373040	254446052624	155296650648	3302227741096	19822460137384
5	[5] 2 10	8	[5] 34 170	96	[5] 2342 11710	16804	[5] 68860 344300	606688	[5] 2997634 14988170	1544720	[5] 33555146 167775730	19029864	[5] 681073734 3405368670	1260184496	[5] 2974356306 14871781530	108815220032	[5] 18506568168 92532840840	56041736392	[5] 3755676047600 18778380238000	4402064805608	[5] 169106742579008 845533712895040	34997635256728
6	[6] 2 12	8	[3] 40 120	96	4184	4592	[3] 98912 296736	507056	1824688	2045304	[3] 8030504 24091512	367522560	1679162720	76802416	[3] 13951927360 41855782080	6041675312	681798670200	472419240200	[3] 1595162914368 4785488743104	9801649413424	[3] 66730681830448 200192045491344	96386522564864
7	[7] 2 14	8	[7] 46 322	96	17432	714592	[7] 9166514 64165598	34882576	299407462	58495320	17528302032	255750389816	[7] 527212155760 3690485090320	4490430260152	[7] 132715628795344 929009401567408	102906381886784
8	[8] 2 16	8	[4] 52 208	96	[2] 15800 31600	147424	10003800	11502464	[2] 817028832 1634057664	4622916480	[2] 28041851784 56083703568	283557331968	[2] 258300148016 516600296032	2023377365008	379480121316560	1168360867448448
9	[9] 2 18	8	[9] 58 522	96	[9] 174320 1568880	8066144	[9] 278711246 2508401214	3586271200	[9] 102117469222 919057222998	133648022836	[9] 5123840063762 46114560573858	117023480769872
10	[10] 2 20	8	[5] 64 320	96	[5] 1089044 5445220	10426496	[5] 421554140 2107770700	2084996112	[5] 74929451984 374647259920	150192928160	[5] 17234336729272 86171683646360	96092178610816
11	[11] 2 22	8	[11] 70 770	96	[11] 5706122 62767342	12407368	[11] 743930286 8183233146	14626950624	[11] 16137819532920 177516014862120	307998326029192	> 2679370000000000
12	[12] 2 24	8	[6] 76 456	96	[6] 36409444 218456664	89938544	[3] 1555327928 4665983784	85363123552	[6] 133014676711964 798088060271784	135516255977120
13	[13] 2 26	8	[13] 82 1066	96	[13] 67369382 875801966	1874869096	[13] 74076471182 962994125366	32955829457568
14	[14] 2 28	8	[7] 88 616	96	[7] 311304720 2179133040	3134995080	[7] 276129430192 1932906011344	45634795164688
15	[15] 2 30	8	[15] 94 1410	96	[15] 1078079138 16171187070	25770205108	[15] 72951945146078 1094279177191170
16	[16] 2 32	8	[8] 100 800	96	[8] 7937081572 63496652576	150244377600
17	[17] 2 34	8	[17] 106 1802	96	[17] 15055046252 255935786284	406904645548
18	[18] 2 36	8	[9] 112 1008	96	146191703400	872886860320
19	[19] 2 38	8	[19] 118 2242	96	[19] 554081969798 10527557426162	81026017704884
20	[20] 2 40	8	[10] 124 1240	96	[10] 562731443148 5627314431480
21	[21] 2 42	8	[21] 130 2730	96	[3] 18191910235790 54575730707370
22	[22] 2 44	8	[11] 136 1496	96	[11] 84898039066800 933878429734800
23	[23] 2 46	8	[23] 142 3266	96
24	[24] 2 48	8	[12] 148 1776	96
25	[25] 2 50	8	[25] 154 3850	96
26	[26] 2 52	8	[13] 160 2080	96
27	[27] 2 54	8	[27] 166 4482	96
28	[28] 2 56	8	[14] 172 2408	96
29	[29] 2 58	8	[29] 178 5162	96
30	[30] 2 60	8	[15] 184 2760	96
31	[31] 2 62	8	[31] 190 5890	96
32	[32] 2 64	8	[16] 196 3136	96
33	[33] 2 66	8	[33] 202 6666	96
34	[34] 2 68	8	[17] 208 3536	96
35	[35] 2 70	8	[35] 214 7490	96
36	[36] 2 72	8	[18] 220 3960	96
37	[37] 2 74	8	[37] 226 8362	96
38	[38] 2 76	8	[19] 232 4408	96
39	[39] 2 78	8	[39] 238 9282	96
40	[40] 2 80	8	[20] 244 4880	96
41	[41] 2 82	8	[41] 250 10250	96
42	[42] 2 84	8	[21] 256 5376	96
43	[43] 2 86	8	[43] 262 11266	96
44	[44] 2 88	8	[22] 268 5896	96
45	[45] 2 90	8	[45] 274 12330	96
46	[46] 2 92	8	[23] 280 6440	96
47	[47] 2 94	8	[47] 286 13442	96
48	[48] 2 96	8	[24] 292 7008	96
49	[49] 2 98	8	[49] 298 14602	96
50	[50] 2 100	8	[25] 304 7600	96
51	[51] 2 102	8	[51] 310 15810	96
52	[52] 2 104	8	[26] 316 8216	96
53	[53] 2 106	8	[53] 322 17066	96
54	[54] 2 108	8	[27] 328 8856	96
55	[55] 2 110	8	[55] 334 18370	96
56	[56] 2 112	8	[28] 340 9520	96
57	[57] 2 114	8	[57] 346 19722	96
58	[58] 2 116	8	[29] 352 10208	96
59	[59] 2 118	8	[59] 358 21122	96
60	[60] 2 120	8	[30] 364 10920	96
61	[61] 2 122	8	[61] 370 22570	96
62	[62] 2 124	8	[31] 376 11656	96
63	[63] 2 126	8	[63] 382 24066	96
64	[64] 2 128	8	[32] 388 12416	96

Last update: 2026-05-02 23:41:01

Some observations

The ant always ends up in the same column it starts in. For even widths, the ant always ends up in the initial position.
Following the last observation: the multiplicity in brackets is divisible by the height. And for even widths it is always one (if one considers a period as either a full map of ones or zeroes instead of only zeroes, then the even widths can have multiplicity greater than 1)^[1]
Widths 1, 2 and 4 and height 2 become constant.
Size 3xn (n>1) has period n*(3n+2) if n is even and 2n*(3n+2) if n is odd.
Size (3n+1)x3 (n>1) has period 96n+16.
Size nx1 has period 2n.
The other columns and rows grow exponentially (R²=0.99). However, along the columns, the jumps happen every other row and adjacent rows have similar periods.

Verify results

For small periods simply run the simulation. For larger periods I provide different checkpoints so that the computation can be performed in parallel. Keep in mind that some sizes may take days or weeks to finish.

Check the results and code here

References

More details on upper bounds and multiplicities: What is the period of Langton's ant on a torus? - Stackexchange
Period of Langton's ant on an n X n torus. - OEIS
Period of Langton's Ant on an n X 3 torus. - OEIS