"Prime fingerprint game" and coupon collector's problem

I find it easiest to explain the motivation as a "game" or task: you are given an arbitrary (but guaranteded to be valid) subsequence of the characteristic function of primes, so just '1's and '0's, one after another, and your task is to identify the numbers they represent. To simplify, let's say the sequence always starts with a '1', and you have identify the prime this first '1' represents (and consequently also all other digits). As soon as you know the answer you press a big red buzzer button and the game is over. But wrong answers have severe consequences, so you shouldn't guess, but be absolutely sure. What can you do?

As far as I can tell the only strategy is to look for complete residue systems modulo p for some prime number p. As soon as we find such a complete system, we know for sure that one of the p involved '1's has to represent this prime p, and now "only" have to find out which one, e.g. by comparing the subsequence with the characteristic function table in that range.

Trivial examples:

• 1 1 [BUZZ]
  We found a complete system mod 2, and can then show that the first '1' has to represent the 2.

• 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 [BUZZ]
  We found a complete system mod 5, and can then show that the first '1' has to represent the 5.

I want to know how the lengths of required subsequences grow when p increases. For this I define a function $ F: \mathbb{P} \rightarrow \mathbb{N} $ that for a given prime p returns the total number of primes needed to complete a residue system modulo p, starting at $p_{1} = 2$. In other words, $F(p) = n$ means that $ p_{n} $ is the smallest prime such that for every k in $\{0, 1, ..., p-1\}$ the set $\{p_{1}, ..., p_{n}\}$ contains at least one prime that is congruent k mod p.

This function allows to specify my question:

What can be said about the (asymptotic) growth rate of F(p)?

Below a plot of F(p) (in red) for the first 500 primes. The discrete values of F (dots) are connected by lines only for visual comprehensibility.

What I tried so far:

If for two primes p, q and 0 < k < p the fact that $ q \equiv k\ (mod\ p) $ would be an independant random event with uniform propability $\frac{1}{p - 1}$, we would expect F(p) to grow like the expectation of the Coupon collector's problem without group drawings, which has the general solution $ n \cdot H_{n} $, where $H_{n}$ is the nth Harmonic number. In this case it would rather be $ (p - 1) \cdot H_{p - 1} $, but such distinctions are irrelevant for understanding the asymptotic growth rate.

But of course the above assumption is wrong, in particular the term "independant". In the limited sample set of the above plot it looks like F(p) might instead grow like: $$ F(p) \sim C\ \cdot p\ \cdot H_{p} $$ with C being a constant near 0.7 (light blue) - possibly log(2) -, but this is pure speculation.

For example, consecutive primes come in groups or "packets" (of varying sizes) of distinct residues mod p: for any odd prime p and any $ n \geq 0 $ all odd primes $ q_{i} $ in the range:

$$ n \cdot p < q_{i} < (n + 2) \cdot p$$

must have a different residue mod p. Taking the varying packet sizes - the actual prime distribution - into account when calculating the expectation is hardly possible, but for packets of fixed size s I found the following formula for calculating the expectation of needed packets in german math book Norbert Henze: Stochastik für Einsteiger:

$$ E(X_{n}) = \sum_{r = 1}^{n - s} (-1)^{r - 1} \binom{n}{r} \frac{q_{r}^{a - 1} \cdot (q_{r} - a \cdot (q_{r} - 1))}{1 - q_{r}} $$

with:

$$ a := \left\lceil \frac{n}{s} \right\rceil, q_{r} := \frac{\binom{n - r}{s}}{\binom{n}{s}}$$

I thought that this can be used to at least calculate a lower bound - not for individual values, but for the growth rate of F(p). If we pretend that we deal with packets of fixed size s and use the largest actual packet size - the number of primes between 0 and $2 \cdot p$, i.e. $\pi(2 \cdot p)$ - as this fixed packet size, we should get such a lower bound, since larger packets mean lower expectation and we replaced all actual packet sizes with the largest packet size.

In the above plot this lower bound is represented as G(p) (green), where G(p) is calculated like this:

$$ G(p) = li(2 \cdot p \cdot E(X_{p})), s = round(li(2 \cdot p)) $$

Explanation:

• $ \pi(2 \cdot p) $ is replaced by $ round(li(2 \cdot p)) $, which should be no problem.
• $ E(X_{p}) $ is used to calculate the number of needed packets of size $ round(li(2 \cdot p)) $.
• Multiplying $ E(X_{p}) $ by $ round(li(2 \cdot p)) $ would now overshoot - since there were actually less primes in each packet above $ 2 \cdot p $ - and the result would be unclear. Instead we feed $ 2 \cdot p \cdot E(X_{p}) $ into li again to calculate the lower bound. That is, we use $ E(X_{p}) $ only for the number of packets, but then calculate the actual number of primes between 0 and $ 2 \cdot p \cdot E(X_{p}) $.

G(p) indeed seems to be a lower bound for the growth rate of F(p), but a rather bad one, I'm sure that there are better ways to approach this.

Thanks in advance.