|
|
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.
|
|
4
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
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...
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)
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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nice,nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|