# Grasshopper jumping on circles

Can we characterize the grasshopper sequence?

Let $$n\in\mathbb N$$ be the number of stones $$s\in\{0,1,2\dots,n-1\}=S$$ on a circle that the grasshopper can jump on. Let $$v(s)$$ be the number of times the grasshopper visited the stone $$s$$. Initially, $$v(s)=0$$ for all $$s\in S$$.

The grasshopper takes a running start and starts jumping around, not planning to slow down. At the $$k$$th jump say he is on some stone $$s\in S$$. Say stone $$s_L$$ is $$k$$ steps anticlockwise, and stone $$s_R$$ is $$k$$ steps clockwise. He will jump on $$s_L$$ if $$v(s_L)\le v(s_R)$$, otherwise he will jump on $$s_R$$.

That is, if $$s$$ is the current stone, then he either moves to: $$s\to (s-k)\bmod n$$ $$s\to (s+k)\bmod n$$ Depending which of the two stones was visited least amount of times till this point.

Let $$a(n)$$ be the number of jumps the grasshopper makes before visiting all stones at least once, when jumping on $$n$$ stones placed on a circle.

For example, if $$n=5$$, he takes $$10$$ jumps to visit all stones, so $$a(5)=10$$. The jumps are: $$\begin{array}{cccc} k & (v(0), v(1), v(2), v(3), v(4)) & \text{jump} & {s}_{L}/{s}_{R} \\ - & (0, 0, 0, 0, 0) & \\ 0 & (1, 0, 0, 0, 0) & s \to 0 & \\ 1 & (1, 0, 0, 0, 1) & 0 \to 4 & L\\ 2 & (1, 0, 1, 0, 1) & 4 \to 2 & L\\ 3 & (1, 0, 1, 0, 2) & 2 \to 4 & L\\ 4 & (1, 0, 1, 1, 2) & 4 \to 3 & R\\ 5 & (1, 0, 1, 2, 2) & 3 \to 3 & L\\ 6 & (1, 0, 2, 2, 2) & 3 \to 2 & L\\ 7 & (2, 0, 2, 2, 2) & 2 \to 0 & L\\ 8 & (2, 0, 3, 2, 2) & 0 \to 2 & L\\ 9 & (2, 1, 3, 2, 2) & 2 \to 1 & R\\ \end{array}$$

WLOG grasshopper prefers anticlockwise $$s_L$$, and the zeroth jump sets $$s=0$$ as starting stone.

What can we say about $$a(n)$$?

One easy pattern I noticed, is that it appears to be:

$$a(n)=n \iff n\in\{2^m,m\in\mathbb N\}\cup\{1,3,7\}$$

Otherwise, it appears that $$a_n(n)\gg n$$ is much greater.

Here is the plot of around first $$15000$$ terms of $$a(n)$$:

The red line below is $$y=x$$ and intersects $$n=2^m$$'s since $$a(2^m)=2^m$$.

All the other terms are above the blue line which is $$y=x^{1.14}-4$$, an exponential lower bound that I guessed holds so far.

The green line intersects the origin $$(0,0)$$ and the term $$a(10496)=108893$$, which is the farthest term from the average so far. We have $$10496=2^8\cdot 41$$.

$$(Q_1)$$ Can we prove all terms $$a(n)$$ will be finite? For fixed $$n$$ the jumping must be periodic eventually, but will that period contain every $$s$$?

Or would this be too hard? - Since this looks like something similar to proving Recamán's sequence visits all numbers, which is a known unsolved problem.

For comparison, if we would always jump anticlockwise and only switch to clockwise if the $$v(s_R)=0$$, then the sequence would not terminate for all $$n$$ (would not be finite for all $$n$$).

Can we say anything else about the sequence $$a(n)$$?

$$(Q_2)$$ Can we find closed forms for patterns other than when $$n=2^m$$?

I'm not sure how to approach this.

Can we determine when the clockwise jumps $$R$$ occur?

Since the grasshopper prefers jumping on $$s_L$$, maybe finding when jumps on $$s_R$$ (the $$R$$ jumps) occur, can help characterize the sequence.

Hence, define $$R(r,n):=$$ "$$k$$th jump at which the grasshopper preformed the $$r$$th $$R$$ jump."

Recall that if $$n=2^m$$, we never preform the $$R$$ jump as first $$n$$ $$L$$ jumps visit all stones.

Hence assume $$n\ne 2^m$$. We wanted to first find a closed form for when first $$R$$ jump occurs.

The first $$R$$ jump.

That is, we look at $$R(1,n)$$ values, and it appears that it is $$\approx n/l$$, for some $$l\in\mathbb N$$.

• if $$n=p$$ is prime, then $$R(1,p)\approx n/2$$, to be precise: ($$\delta\in\mathbb N$$ depends on exact $$n$$)

$$R(1,p)=\frac12(n+1)+\delta$$

• if $$n=2p$$ where $$p$$ prime, then $$R(1,2p)\approx n/4$$, to be precise: ($$\delta\in\mathbb N$$ depends on exact $$n$$)

$$R(1,2p)=\frac14(n+2)+\delta$$

• if $$n=2^m q$$ where $$q$$ is odd, then $$R(1,2^m q)\approx n/q$$.

Depending on $$l$$ value, we get terms $$R(1,n)$$ accumulating around lines $$y=x/l$$.

Notice how odd $$l$$ are rarely populated, and how even $$l$$ are dense.

For example, as already mentioned, primes gather around $$l=2$$, and even semiprimes around $$l=4$$. For an odd $$l$$ example, it seems the numbers of form $$2^m\cdot 3$$ belong to $$l=3$$.

$$(Q_3)$$ Can we find a closed form for $$R(1,n):=$$ $$k$$-step at which we make the first $$R$$ jump?

That is, can we find the exact $$\delta$$ values, depending on $$n$$?

The first $$R$$ jump, when $$n$$ is prime.

In the case of primes $$n=p$$, I mentioned we have:

$$R(1,p)=\frac12(n+1)+\delta$$

It seems that the following patterns hold:

• If $$p$$ is of form $$4m+3$$, then $$\delta=0$$.
• If $$p$$ is of form $$8m+5$$, then $$\delta=1$$.
• If $$p$$ is of form $$56m+\{17,33,41\}$$, then $$\delta=4$$.
• If $$p$$ is of form $$1288m+X_4$$, then $$\delta=6$$, where $$X_4$$ contains:

{57, 65, 113, 137, 249, 281, 337, 401, 457, 505, 513, 569, 585, 617, 641, 681, 697, 753, 793, 849, 865, 953, 977, 1009, 1017, 1033, 1065, 1073, 1121, 1201, 1233, 1241, 1257}

• If $$p$$ is of form $$\dots$$

And so on.

Can we find a closed-form for these patterns (congruence classes) that determine $$\delta$$?

What is so special about $$p$$ modulo $$3,8,56,1288\dots$$?

The next one seems to be $$21896$$, and if that is true, then $$X_5$$ would contain:

{17921, 11265, 14337, 15873, 7169, 7177, 17929, 21001, 8201, 14345, 13841, 2577, 20497, 9241, 16921, 21529, 9753, 20505, 18425, 16417, 19489, 15905, 16937, 5161, 14897, 2097, 11825, 7729, 4153, 19513, 14393, 1593, 21057, 10313, 16969, 17481, 6729, 3665, 16977, 20049, 7249, 12881, 12889, 20057, 10329, 19545, 9305, 2657, 19553, 8289, 1129, 15465, 9321, 14953, 4601, 5233, 8817, 7281, 1145, 11897, 14457, 15481, 9857, 11393, 13441, 3201, 20609, 7809, 2697, 18057, 20105, 14473, 12433, 5777, 16017, 13969, 5273, 20633, 6297, 673, 8353, 9377, 18593, 1185, 4257, 12961, 19625, 1705, 7849, 177, 17585, 6329, 4281, 193, 9921, 13505, 14529, 5825, 21697, 6857, 1737, 8905, 2249, 16585, 8913, 17105, 8401, 4313, 11481, 15577, 4825, 19681, 11489, 15073, 5345, 1761, 737, 10977, 233, 21737, 7401, 3305, 12009, 17649, 15089, 14065, 16633, 13049, 21753, 20729, 19713, 5377, 5889, 6913, 20225, 1289, 12041, 12553, 1297, 15633, 19217, 9489, 18705, 20241, 785, 3865, 14617, 18201, 7961, 3361, 10529, 12065, 21281, 3873, 809, 17193, 10537, 20777, 6449, 20785, 9017, 13113, 20801, 15681, 6465, 2377, 4425, 18761, 5961, 11769, 8017, 9041, 19793, 11089, 11601, 7001, 8537, 4953, 18265, 11617, 13665, 21345, 11113, 9577, 2417, 13169, 16241, 6521, 10105, 4993, 13185, 16769, 15745, 5513, 11145, 5009, 3985, 21393, 2969, 8089, 921, 7065, 11673, 18841, 18337, 14249, 1961, 6057, 10665, 21417, 16297, 5545, 3497, 12721, 10161, 1457, 20913, 8633, 8121, 12217, 16825, 1465, 449, 5569, 15297, 15817, 7113, 11209, 21449, 4041, 14793, 10193, 17873, 4057, 473, 11225, 17369, 16377, 2017, 6113, 9185, 17889, 10721, 3049, 16361, 12777, 13801, 6633, 15849, 13297, 19441, 4593, 15345, 11761, 20465, 9209}


And in this case, the $$\delta=7$$ would occur.

The $$\delta$$ values whose congruence classes are unknown are: $$\delta\in\{8, 9, 13, 10, 14, 16, 15, 17,\dots\}$$

These congruence classes mentioned so far, that should determine $$\delta\in\{0,1,4,6,7\}$$ for all primes, are based on data on first $$2\cdot 10^4$$ primes, so far.

• I'll just say, it is a joy to read these updates :) Nov 3, 2019 at 19:10
• triangle numbers mod n
– user645636
Nov 3, 2019 at 19:18
• I'm also interested in the dynamics where the grasshopper tries to preserve direction. (i.e. instead of tiebreaking by using the clockwise direction, tiebreak by maintaining direction.) Nov 11, 2019 at 22:54
• I've added a few related OEIS sequences: A329230, A329231, A329232, and A329233. Nov 12, 2019 at 4:57
• @PeterKagey The variation where direction is preserved looks interesting. The $y=x$ line is now densely populated. That is, primes of form $n=p=4k+3$ now also have this property $a(n)=n$ as well as powers of two $n=2^m$. Nov 12, 2019 at 6:05