31
$\begingroup$

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)$:

enter image description here

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

enter image description here

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.

$\endgroup$
6
  • $\begingroup$ I'll just say, it is a joy to read these updates :) $\endgroup$
    – Milten
    Nov 3, 2019 at 19:10
  • $\begingroup$ triangle numbers mod n $\endgroup$
    – user645636
    Nov 3, 2019 at 19:18
  • 1
    $\begingroup$ 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.) $\endgroup$ Nov 11, 2019 at 22:54
  • 1
    $\begingroup$ I've added a few related OEIS sequences: A329230, A329231, A329232, and A329233. $\endgroup$ Nov 12, 2019 at 4:57
  • 1
    $\begingroup$ @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$. $\endgroup$
    – Vepir
    Nov 12, 2019 at 6:05

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.