A329230 The number of steps it takes to reach all n positions around a circle during the grasshopper procedure.

1, 2, 3, 4, 10, 9, 7, 8, 23, 17, 16, 21, 20, 27, 29, 16, 58, 25, 28, 30, 40, 43, 88, 50, 40, 55, 87, 50, 62, 59, 70, 32, 81, 72, 67, 91, 84, 73, 71, 125, 107, 113, 69, 88, 148, 116, 135, 113, 158, 95, 137, 114, 182, 123, 174, 166, 112, 146, 215, 173, 126, 171

Offset: 1

Author

Peter Kagey, Nov 08 2019

Keywords

• nonn
• walk

Comments

The grasshopper procedure: n positions are evenly spaced around a circle, a grasshopper hops randomly to any position, after the k-th hop, the grasshopper looks clockwise and counterclockwise k positions. If one of the positions has been visited less often then the other, it hops there; if both positions have been visited an equal number of times, it hops k steps in the clockwise position. (See Mathematics Stack Exchange link for more details.)

In the Mathematics Stack Exchange link, the author conjectures that a(n) = n if and only if n = 3, n = 7, or n = 2^k for some nonnegative k.

Examples

			For n = 5 the a(5) = 10 steps are:
  [0,0,0,0,0] (randomly step to first position)
  [1,0,0,0,0] (length 1 clockwise (right) step)
  [1,1,0,0,0] (length 2 clockwise (right) step)
  [1,1,0,1,0] (length 3 clockwise (right) step)
  [1,2,0,1,0] (length 4 counterclockwise (left) step)
  [1,2,1,1,0] (length 5 clockwise (right) step)
  [1,2,2,1,0] (length 6 clockwise (right) step)
  [1,2,2,2,0] (length 7 clockwise (right) step)
  [2,2,2,2,0] (length 8 clockwise (right) step)
  [2,2,2,3,0] (length 9 counterclockwise (left) step)
  [2,2,2,3,1]
For example, the length 4 counterclockwise step occurs because stepping clockwise would result in landing in a position which has been visited once, and stepping counterclockwise would result in landing in a position which has not been visited before.
		

Links

• Peter Kagey, Table of n, a(n) for n = 1..5000
• Mathematics Stack Exchange User Vepir, Grasshopper jumping on circles.

Crossrefs

Cf. A329231, A329232, A329233.