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,16

Comments

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

References

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

Links

Table of n, a(n) for n=1..70.

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

Example

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)

Prog

(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

Crossrefs

Cf. A101857, A006718, A292793.

Sequence in context: A181004 A051344 A236534 * A335520 A326291 A269250

Adjacent sequences: A101853 A101854 A101855 * A101857 A101858 A101859

Keyword

nice,nonn

Author

Gordon Hamilton, Jan 27 2005

Extensions

a(31)-a(70) from Bert Dobbelaere, Jan 01 2019

Status

approved