Playing leapfrog with primes

Question

In connection with how primes jump (How do these primes jump?), I consider the following game.

Let $R$ be a finite set of positive integers. For this question, I content myself with $R$ being the $k$ smallest primes. I pick an order to "play" elements of $R$, and start with an empty track (number line). For each element $p$ of $R$, I pick an integer $m_p $ from $ [1,p]$ and do the following to play $p$: If slot $m_p$ is occupied on the track, increment $m_p$ by $p$ and try again, until one finds an unoccupied slot and then place $p$ on (occupy) location $m_p$. Play all $p$ in order. When I am done, there will be a $p$ with largest value of $m_p$, which I call $m$.

Over all orderings of $R$ and combinations of starting offsets $m_p$, what is the largest value of $m$ one can obtain?

Because 2+3=5, $m$ is 10 for the set $ \{2,3,5\}$. As we add larger primes, to $R$, $m$ becomes 16,25,35,48,59,73 (unverified). However, it is not clear how $m$ increases as one adds another prime. Does $m$ grow proportional to the $k$th prime for $R$ the set of the $k$ smallest primes? Or does it grow strictly faster?

If there are references to this game for this or for other sets $R$, I would appreciate knowing them. Note that we are filling the track with (occupied slots forming) short arithmetic progressions in order to get a large value for $m$. If there are nice ways to bound $m$ as a function of $k$, I would like seeing those too.
(I suspect an upper bound of $O(\sqrt{k}p_k)$ is provable.)

Gerhard "Trying To Jump For Results" Paseman, 2016.12.13.

Answer 1

I collect some information here as small progress on the problem.

Note that for any multiset $R$ and any ordering, one can pick $m_p$ for each member $p$ of $R$ so that one can achieve the minimum value of $n$, the count of members of $R$, while the example above with the first four primes shows that one cannot always achieve $s(R)$, the sum of the members of $R$, even when one can choose the order of play. When $n \gt 1$ one has $m$ at least as big as the sum of the largest two members of $R$, and one is challenged to make further progress for general $R$, especially when the three largest members are distinct and much larger than the sum of the remaining members.

I found a good algorithm whose runtime in practice is pretty good. While playing the primes in increasing order is good, it is not always optimal. Also, in order to find good starting offsets, it helps to "run the race in reverse".

The old algorithm did a breadth first search with pruning, but essentially looked through a prohibitively large subset of starting orders and offsets. After 11 primes, the system ran out of memory in spite of additional pruning of the search space, which seemed to be smaller than the number of orders, but was still too large.

So I decided to run the race backwards. I let the largest prime $p_k$ jump backwards $k$ times. I then picked the second largest prime, placed it on the space behind the farthest space achieved by the largest prime, and let it jump back about half as many times. This is because the spaces occupied by these prime leaps must total $k$, and the last two are occupied by the two largest primes.

I continue in this fashion, having the $j$th largest prime occupy the $j$th furthest space, computing the previous spaces it needs to get there, trimming the set of all spaces down to $k$ many, and continue in this fashion until I run out of primes. I now get an objective value for the length of the jumps and (in principle, but not in practice) their starting offsets.

This objective value may not be an optimal value for $m$, but it is a good aid in limiting the search space. I now repeat the process, except I try those combinations of primes which exhibit promise in beating the objective value. The number of combinations tested is quite variable but seems to be a conjectured $O(\sqrt{k}!)$ easily beating out the large fraction involving the product of the primes times $k!$.

By running it backwards for the first $k$ primes, I achieve objective (followed by optimal and rough estimate of cases beating the objective) values for m: 2,5,10, 15 (16,2), 25, 35, 48, 58 (59,5), 72 (73,15), 91 (92,23), 101 (105,705), 129 (130,8), 141 (146,966), 160 (169,10204), 187 (189,122).

An example race run in reverse (so everybody starts at 189) for the 15 primes less than 50 is

0,47,88,94,129,131,141,160,168,170,174,179,183,186,188,189.

Note that this race involves 47 followed by 41, not 43.

There is a geometric interpretation of the space of positions which suggests the bound in the post involving $\sqrt{k}p_k$ as a rough size for the objective and optimal bound. When I have some solid looking theory behind it I will post it here.

EDIT 2017.01.06 I post some fluid heuristics in hopes someone will freeze it into solid theory.

Let us look at what it takes to have the largest prime $p$ make $l$ leaps to land somewhere near and at most $lp$ away from the starting line. This requires $l$ primes, one being $p$ and the rest being distinct primes to leap over or upon to reach the farthest spot. Suppose now that $q$ is the second farthest prime and is less than $p$. It will need at least $l-1$ primes: itself and the remaining distinct primes to reach its final spot. It may need more, but if $q \geq l-1$ then every supporting prime it needs will be in a different location than those needed for $p$. (Every $p$ consecutive members of an integer arithmetic progression with common difference $q$ coprime to $p$ has exactly one member in common with a similar one with difference $p$.)

If we continue this with the next furthest prime $r$ we find we need at least $l-2$ primes, at most 2 of which are shared by the primes supporting $p$ or $q$, again assuming that $r\geq l-2$. With these largeness assumptions, the $j$th furthest prime which is bigger than $l-j-1$ will require an additional $l-(2j-2)$ supporting primes different from the ones needed from the earlier primes. This is $\Omega(l^2)$ distinct supporting primes bigger than $l$ to get $p$ to a position close to $lp$.

On the other hand, if one of the small $O(\sqrt{k})$ primes is used too near $lp$, then $lp$ is too close to $k\sqrt{k}$ to be a candidate for a maximal team leap.

So far the data roughly correspond to the conjecture for the first $k$ primes. With $k$ going from 16 to 20, we have 206 (214), 223 (243), 245 (256), 277 (291), 298 (313) for the trial (record) jumps. End EDIT 2017.01.06

Gerhard "Invert Your Perspective For Progress!" Paseman, 2017.01.03.

Answer 2

This probably will not shed any light, but ...

First, fix the "order of play" to just be the natural order of the primes. For $n=10$, $R= ( 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 )$. For each $p \in R$, choose your starting $m_p$ randomly from $[1,p]$. Then proceed to find an empty slot for $p$ at positions $$m_p, \; m_p+p,\; m_p+2p, \; m_p+3p,\; \ldots$$ as you describe. The maximum filled slot $m$ appears to have a natural distribution:

---

         
          ^{Distribution of the maximum $m$ achieved over $10^5$ trials, $n=10$.}

---

(The largest $m$ seen in this sampling was $m=78$.) I plotted the negative binomial / Pascal distribution for $n=10$ on top of the histogram. It is a reasonable fit for probability $p \approx 0.33$. If the distribution is indeed Pascal, it suggests a regularity underlies the somewhat chaotic jumping of the primes.