A101856 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.
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, 1259, 0, 0, 0, 0, 0, 0, 15072, 41381, 0, 0, 0, 0, 0, 0, 588066, 1651922, 0, 0, 0, 0, 0, 0, 25263990, 73095122, 0, 0, 0, 0, 0, 0, 1194909691, 3492674650, 0, 0, 0, 0, 0, 0
Offset: 1
Examples
For example: a(7) = 1 because of the following solution: 655555... 6....4... 6....4... 6....4... 6....4333 6.......2 777777712 where the ant starts at the "1" and moves right 1 space, up 2 spaces and so on... From _Seiichi Manyama_, Sep 23 2017: (Start) a(8) = 1 because of the following solution: (0, 0) -> (1, 0) -> (1, 2) -> (-2, 2) -> (-2, -2) -> (-7, -2) -> (-7, -8) -> (0, -8) -> (0, 0). .....4333 .....4..2 .....4.12 .....4.8. 655555.8. 6......8. 6......8. 6......8. 6......8. 6......8. 77777778. a(15) = 1 because of the following solution: (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). a(16) = 3 because of the following solutions: (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), (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), (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)
References
- Dudeney, A. K. "An Odd Journey Along Even Roads Leads to Home in Golygon City." Sci. Amer. 263, 118-121, 1990.
Links
- Bert Dobbelaere, C++ program
- L. C. F. Sallows, New Pathways in Serial Isogons, Math. Intell. 14, 55-67, 1992.
- Lee Sallows, Martin Gardner, Richard K. Guy and Donald Knuth, Serial Isogons of 90 Degrees, Math Mag. 64, 315-324, 1991.
- Eric Weisstein's World of Mathematics, Golygon
Programs
-
Ruby
def A101856(n) ary = [0, 0] b_ary = [[[0, 0], [1, 0], [1, 1], [1, 2]]] s = 4 (3..n).each{|i| s += i t = 0 f_ary, b_ary = b_ary, [] if i % 2 == 1 f_ary.each{|a| b = a.clone x, y = *b[-1] b += (1..i).map{|j| [x + j, y]} b_ary << b if b.uniq.size == s t += 1 if b[-1] == [0, 0] && b.uniq.size == s - 1 c = a.clone x, y = *c[-1] c += (1..i).map{|j| [x - j, y]} b_ary << c if c.uniq.size == s t += 1 if c[-1] == [0, 0] && c.uniq.size == s - 1 } else f_ary.each{|a| b = a.clone x, y = *b[-1] b += (1..i).map{|j| [x, y + j]} b_ary << b if b.uniq.size == s t += 1 if b[-1] == [0, 0] && b.uniq.size == s - 1 c = a.clone x, y = *c[-1] c += (1..i).map{|j| [x, y - j]} b_ary << c if c.uniq.size == s t += 1 if c[-1] == [0, 0] && c.uniq.size == s - 1 } end ary << t } ary[0..n - 1] end p A101856(16) # Seiichi Manyama, Sep 24 2017
Extensions
a(31)-a(70) from Bert Dobbelaere, Jan 01 2019
Comments