How many days are needed to find the robot?

Question

There is a row of $n$ opaque boxes numbered from $1$ to $n$.

A robot is programmed with an ordered pair of numbers $(x,y)$, each being integers between $1$ and $n$, inclusive.

$x$ is the box the robot will be in on the first day, and $y$ is the "speed" of the robot: each night the robot adds $y$ to its current box number and moves to that new box. If the sum exceeds $n$, then the robot subtracts $n$ to determine its new box.

You may open one box per day. How many days are needed to guarantee finding the robot? More specifically, is there a formula (explicit or recursive) based on $n$?

I've made only a little progress working by hand.

Number of boxes, $n$	Days to find the robot
$1$	$1$
$2$	$3$
$3$	$4$
$4$	$5$

For $n=3$ my solution is $1,1,3,2$. For $n=4$ my solution is $1,4,3,4,2$. For $n=5$ the best I can do is $9$ days, but I'm not confident about that being optimal.

These came from using a greedy algorithm like approach: I listed out all the possible sequences of the robot's positions and on each day looked for which box I could open that would eliminate most of the remaining sequences.

I tried searching $1,3,4,5,9$ in OEIS and it came back with these so-called Stone Skipping Numbers. I don't fully understand what the comments mean, but it seems to not be analogous to my box problem.

EDIT/UPDATE:

For $n=6$ boxes, I found a solution of $9$ days, which is: $1,2,6,5,4,4,3,4,2$.

I also know that if $n$ is a prime number, then the robot can be found in at most $2n-1$ days by the following process: Open box #$1$ on each of the first $n$ days. This will capture all robots except the ones that are stationary in the other boxes. Then open boxes $2$ through $n$ on days $n+1$ through $2n-1$.

Answer 1

Your solution for n=3 is wrong. This table shows, which robot you will find on which day.

day	box	(1,1)	(1,2)	(1,3)	(2,1)	(2,2)	(2,3)	(3,1)	(3,2)	(3,3)
1	1	x	x	x
2	1			x		x		x
3	3	x				x				x
4	2				x	x	x

There is no day on which you find robot (3,2). There is no solution with 4 days. The shortest solution is 5 days long. There are many 5-day-solutions, here is one of them:

day	box	(1,1)	(1,2)	(1,3)	(2,1)	(2,2)	(2,3)	(3,1)	(3,2)	(3,3)
1	1	x	x	x
2	2	x					x		x
3	3	x				x				x
4	3							x	x	x
5	3		x		x					x

Your solution for n=4 is also wrong:

day	box	(1,1)	(1,2)	(1,3)	(1,4)	(2,1)	(2,2)	(2,3)	(2,4)	(3,1)	(3,2)	(3,3)	(3,4)	(4,1)	(4,2)	(4,3)	(4,4)
1	1	x	x	x	x
2	4			x			x			x							x
3	3	x		x							x		x
4	4	x					x					x					x
5	2					x	x	x	x

There are even 3 robots you don't find: (4,1), (4,2) and (4,3)

Here is a solution with 7 days:

day	box	(1,1)	(1,2)	(1,3)	(1,4)	(2,1)	(2,2)	(2,3)	(2,4)	(3,1)	(3,2)	(3,3)	(3,4)	(4,1)	(4,2)	(4,3)	(4,4)
1	1	x	x	x	x
2	2	x							x			x			x
3	3	x		x							x		x
4	4	x					x					x					x
5	4													x	x	x	x
6	4			x			x			x							x
7	4					x		x							x		x

I did not find any shorter solution for n=4.

My best solution for n=5 needs also 9 days, but again your solution for n=6 is wrong. The table would be too big (it would have 38 columns), so I don't show it here, but your solution doesn't find the robot (6,5). So you need one more day to find this robot, which means, that you need 10 days for n=6. (I found a lot of other solutions with 10 days, but no solution with less than 10 days.)

My best solution for n=8 needs 15 days: 1, 8, 2, 7, 3, 6, 4, 5, 5, 4, 6, 3, 7, 2, 8. For n=9 I found a solution with 17 days: 1, 2, 3, 9, 6, 5, 8, 1, 1, 7, 5, 9, 3, 9, 4, 5, 7 and for n=10 with 19 days: 1, 10, 2, 9, 6, 3, 7, 4, 3, 2, 9, 5, 8, 2, 4, 2, 9, 9, 8

So, for now we have:

n	days
1	1
2	3
3	5
4	7
5	9
6	10
7	13
8	15
9	17
10	19
11	21

You already found an upper boundary for n=prime, and I think for prime numbers this is even the best solution. So, it looks, as if the formula was just $2n-1$, except for n=6.

This is not a full solution, but I hope it helps you a little bit.

Answer 2

Here's a proof that the optimal answer for $n = p$ prime is $2p - 1$.

If we open box $a_i$ on day $i$, then to find the robot in $t$ days we need $$\prod_{i = 1}^t (x + iy - a_i) = 0$$ for all $(x, y) \in \mathbb{F}_p^2$. So the polynomial on LHS must be identically zero on $\mathbb{F}_p^2$, which is equivalent to the fact that the polynomial is zero in the ring $\mathbb{F}_p[x, y] / (x^p - x, y^p - y)$.

It is clearly impossible that $t < p$. Now suppose $p \leq t < 2p - 1$. We consider the coefficient of the monomial $x^{t - p + 1} y^{p - 1}$ in the standard basis $\{x^i y^j: (i, j) \in [0, p - 1]^2\}$ of $\mathbb{F}_p[x, y] / (x^p - x, y^p - y)$. By degree counting(the crucial observation is that $t - p + 1 \leq p - 1$, so only monomials with degree $t$ or higher would contribute to the coefficient of this monomial), the coefficient of $x^{t - p + 1} y^{p - 1}$ is equal to its coefficient in $$\prod_{i = 1}^t (x + iy) = (x^{p - 1} - y^{p - 1})x\prod_{i = 1}^{t - p} (x + iy)$$ which is the nonzero $-1$, contradiction. So we must have $t \geq 2p - 1$.