login
Number of non-intersecting polygons that it is possible for an accelerating ant to produce with n steps (rotations & reflections not included). On step 1 the ant moves forward 1 unit, then turns left or right and proceeds 2 units, then turns left or right until at the end of its n-th step it arrives back at its starting place.
4

%I #54 Jan 02 2019 03:46:19

%S 0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,3,0,0,0,0,0,0,25,67,0,0,0,0,0,0,515,

%T 1259,0,0,0,0,0,0,15072,41381,0,0,0,0,0,0,588066,1651922,0,0,0,0,0,0,

%U 25263990,73095122,0,0,0,0,0,0,1194909691,3492674650,0,0,0,0,0,0

%N Number of non-intersecting polygons that it is possible for an accelerating ant to produce with n steps (rotations & reflections not included). On step 1 the ant moves forward 1 unit, then turns left or right and proceeds 2 units, then turns left or right until at the end of its n-th step it arrives back at its starting place.

%C This walk by an accelerating ant can only arrive back at the starting point after n steps where n is 0 or -1 mod(8).

%D Dudeney, A. K. "An Odd Journey Along Even Roads Leads to Home in Golygon City." Sci. Amer. 263, 118-121, 1990.

%H Bert Dobbelaere, <a href="/A101856/a101856.cpp.txt">C++ program</a>

%H L. C. F. Sallows, <a href="http://leesallows.com/files/New%20Pathways.pdf">New Pathways in Serial Isogons</a>, Math. Intell. 14, 55-67, 1992.

%H Lee Sallows, Martin Gardner, Richard K. Guy and Donald Knuth, <a href="http://www.jstor.org/stable/2690648">Serial Isogons of 90 Degrees</a>, Math Mag. 64, 315-324, 1991.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Golygon.html">Golygon</a>

%e For example: a(7) = 1 because of the following solution:

%e 655555...

%e 6....4...

%e 6....4...

%e 6....4...

%e 6....4333

%e 6.......2

%e 777777712

%e where the ant starts at the "1" and moves right 1 space, up 2 spaces and so on...

%e From _Seiichi Manyama_, Sep 23 2017: (Start)

%e a(8) = 1 because of the following solution:

%e (0, 0) -> (1, 0) -> (1, 2) -> (-2, 2) -> (-2, -2) -> (-7, -2) -> (-7, -8) -> (0, -8) -> (0, 0).

%e .....4333

%e .....4..2

%e .....4.12

%e .....4.8.

%e 655555.8.

%e 6......8.

%e 6......8.

%e 6......8.

%e 6......8.

%e 6......8.

%e 77777778.

%e a(15) = 1 because of the following solution:

%e (0, 0) -> (1, 0) -> (1, 2) -> (4, 2) -> (4, -2) -> (-1, -2) -> (-1, -8) -> (-8, -8) -> (-8, -16) -> (-17, -16) -> (-17, -26) -> (-28, -26) -> (-28, -14) -> (-15, -14) -> (-15, 0) -> (0, 0).

%e a(16) = 3 because of the following solutions:

%e (0, 0) -> (1, 0) -> (1, 2) -> (4, 2) -> (4, 6) -> (-1, 6) -> (-1, 12) -> (-8, 12) -> (-8, 20) -> (-17, 20) -> (-17, 10) -> (-28, 10) -> (-28, -2) -> (-15, -2) -> (-15, -16) -> (0, -16) -> (0, 0),

%e (0, 0) -> (1, 0) -> (1, 2) -> (4, 2) -> (4, 6) -> (-1, 6) -> (-1, 0) -> (-8, 0) -> (-8, -8) -> (-17, -8) -> (-17, -18) -> (-28, -18) -> (-28, -30) -> (-15, -30) -> (-15, -16) -> (0, -16) -> (0, 0),

%e (0, 0) -> (1, 0) -> (1, 2) -> (4, 2) -> (4, -2) -> (-1, -2) -> (-1, -8) -> (-8, -8) -> (-8, 0) -> (-17, 0) -> (-17, -10) -> (-28, -10) -> (-28, 2) -> (-15, 2) -> (-15, 16) -> (0, 16) -> (0, 0). (End)

%o (Ruby)

%o def A101856(n)

%o ary = [0, 0]

%o b_ary = [[[0, 0], [1, 0], [1, 1], [1, 2]]]

%o s = 4

%o (3..n).each{|i|

%o s += i

%o t = 0

%o f_ary, b_ary = b_ary, []

%o if i % 2 == 1

%o f_ary.each{|a|

%o b = a.clone

%o x, y = *b[-1]

%o b += (1..i).map{|j| [x + j, y]}

%o b_ary << b if b.uniq.size == s

%o t += 1 if b[-1] == [0, 0] && b.uniq.size == s - 1

%o c = a.clone

%o x, y = *c[-1]

%o c += (1..i).map{|j| [x - j, y]}

%o b_ary << c if c.uniq.size == s

%o t += 1 if c[-1] == [0, 0] && c.uniq.size == s - 1

%o }

%o else

%o f_ary.each{|a|

%o b = a.clone

%o x, y = *b[-1]

%o b += (1..i).map{|j| [x, y + j]}

%o b_ary << b if b.uniq.size == s

%o t += 1 if b[-1] == [0, 0] && b.uniq.size == s - 1

%o c = a.clone

%o x, y = *c[-1]

%o c += (1..i).map{|j| [x, y - j]}

%o b_ary << c if c.uniq.size == s

%o t += 1 if c[-1] == [0, 0] && c.uniq.size == s - 1

%o }

%o end

%o ary << t

%o }

%o ary[0..n - 1]

%o end

%o p A101856(16) # _Seiichi Manyama_, Sep 24 2017

%Y Cf. A101857, A006718, A292793.

%K nice,nonn

%O 1,16

%A _Gordon Hamilton_, Jan 27 2005

%E a(31)-a(70) from _Bert Dobbelaere_, Jan 01 2019