A number guessing game
It's not possible to solve the game in all cases with fewer than 7 guesses, because after 6 guesses you have at least 95 unguessed numbers and 6 bits of information and $2^6<94.$
But actually 7 is not achievable, since at most 26 primes can appear in any given block of 101. Thus the first guess, in the worst case, will have at least 74 remaining numbers, and so at least 8 guesses are required since $2^6<68$.
The goal at each step is to find numbers that split the remaining numbers into two sets of roughly equal size. Here are the beginnings of a strategy for 9. Ask about 3. If the number is 3 you're done; if n + 3 is prime it should not be hard to guess the number in 8 more tries.
Otherwise 74 numbers remain: 1, 5, 6, 7, 9, 11, 12, 13, 15, 17, 18, 19, 21, 22, 23, 24, 25, 27, 29, 30, 31, 32, 33, 35, 36, 37, 39, 41, 42, 43, 45, 46, 47, 48, 49, 51, 52, 53, 54, 55, 57, 59, 60, 61, 62, 63, 65, 66, 67, 69, 71, 72, 73, 74, 75, 77, 78, 79, 81, 82, 83, 84, 85, 87, 88, 89, 90, 91, 92, 93, 95, 96, 97, 99. Now ask about 10. If n+10 is prime it should be easy to find the number in 7 more tries.
Otherwise 50 numbers remain: 5, 6, 11, 12, 15, 17, 18, 22, 23, 24, 25, 29, 30, 32, 35, 36, 39, 41, 42, 45, 46, 47, 48, 52, 53, 54, 55, 59, 60, 62, 65, 66, 67, 71, 72, 74, 75, 77, 78, 81, 82, 83, 84, 85, 88, 89, 90, 92, 95, 96. Now ask about 12. If n is 12 you're done; if n+12 is prime you have 6 tries to find 16 numbers.
Now 33 numbers remain: 6, 15, 18, 22, 23, 24, 30, 32, 36, 39, 42, 45, 46, 48, 52, 53, 54, 60, 62, 65, 66, 72, 74, 75, 78, 81, 82, 83, 84, 88, 90, 92, 96. Now ask about 1. If n+1 is prime there are 15 possibilities and you have 5 tries.
Now you have just 18: 15, 23, 24, 32, 39, 45, 48, 53, 54, 62, 65, 74, 75, 81, 83, 84, 90, 92. This is a bit tricky, but guess 1139 (or 1148) to split the remainder into two sets of 9.
Either way you go at least one of the sets has 5 members (4 would be possible only if you picked one of the 18).
I have a pretty cool but probably impractical solution.
Consider this table of primes from $1$ to $110$:
$$ \begin{matrix} 2 & 3 & 5 & 7 & 11 \\ 13 & 17 & 19 & 23 & 29 \\ 31 & 37 & 41 & 43 & 47 \\ 53 & 59 & 61 & 67 & 71 \\ 73 & 79 & 83 & 89 & 97 \\ 101 & 103 & 107 & 109 \\ \end{matrix} $$
Notice the differences between all the primes. That table would look like this:
$$ \begin{matrix} 2 & 1 & 2 & 2 & 4 \\ 2 & 4 & 2 & 4 & 6 \\ 2 & 6 & 4 & 2 & 4 \\ 6 & 6 & 2 & 6 & 4 \\ 2 & 6 & 4 & 6 & 8 \\ 4 & 2 & 4 & 2 \\ \end{matrix} $$
Let's look at the combinations of 6 differences in order. They're ordered from left to right and up to down by value as if the sequences represented digits of a 6-digit number:
$$1,2,2,4,2,4 \ \ \ \ \ \ \ \ \ \ 2,1,2,2,4,2 \ \ \ \ \ \ \ \ \ \ 2,2,4,2,4,2$$ $$2,4,2,4,2,4 \ \ \ \ \ \ \ \ \ \ 2,4,2,4,6,2 \ \ \ \ \ \ \ \ \ \ 2,4,6,2,6,4$$ $$2,4,6,6,2,6 \ \ \ \ \ \ \ \ \ \ 2,6,4,2,4,6 \ \ \ \ \ \ \ \ \ \ 2,6,4,2,6,4$$ $$2,6,4,6,8,4 \ \ \ \ \ \ \ \ \ \ 4,2,4,2,4,6 \ \ \ \ \ \ \ \ \ \ 4,2,4,6,2,6$$ $$4,2,4,6,6,2 \ \ \ \ \ \ \ \ \ \ 4,2,6,4,6,8 \ \ \ \ \ \ \ \ \ \ 4,6,2,6,4,2$$ $$4,6,6,2,6,4 \ \ \ \ \ \ \ \ \ \ 4,6,8,4,2,4 \ \ \ \ \ \ \ \ \ \ 6,2,6,4,2,4$$ $$6,2,6,4,2,6 \ \ \ \ \ \ \ \ \ \ 6,4,2,4,6,6 \ \ \ \ \ \ \ \ \ \ 6,4,2,6,4,6$$ $$6,4,6,8,4,2 \ \ \ \ \ \ \ \ \ \ 6,6,2,6,4,2 \ \ \ \ \ \ \ \ \ \ 6,8,4,2,4,2$$
Notice that no two sequences are equal in the above list
Start out by iterating over values of $x$ in $[0,7]$ incrementally until you hit the first prime number. Let this value of $x$ be denoted as $k$.
The above step requires $8$ guesses in the worst case
You have to use new values for $x$ equal to $k + o$ where $o$ is an offset that starts at $1$ and changes based on what's prime and what's not.
If $k + 1$ is prime, you can stop. $n = 2$.
Else, try $k + 2$ and if that doesn't work, $k + 4$, then $k + 6$.
If for instance, $k + 4$ works, you would then try $k + 4 + 2$. If that's prime too, then continue with these combinations in the same manner:
$$4,2,4,2,4,6$$ $$4,2,4,6,2,6$$ $$4,2,4,6,6,2$$ $$4,2,6,4,6,8$$
Using the above method, you derive the value of the prime $n + k$. $k$ is known, so you can immediately deduce the value of $n$.
In fact, we can optimize that above table of differences to remove the unneeded trials and combine a few of them:
$$ \begin{matrix} 1 & 2,1 & 2,2 \\ 2,4,2,4,2 & 2,4,2,4,6 & 2,4,6,2 \\ 2,4,6,6 & 2,6,4,2,4 & 2,6,4,2,6 \\ 2,6,4,6 & 4,2,4,2 & 4,2,4,6,2 \\ 4,2,4,6,6 & 4,2,6 & 4,6,2 \\ 4,6,6 & 4,6,8 & 6,2,6,4,2,4 \\ 6,2,6,4,2,6 & 6,4,2,4 & 6,4,2,6 \\ 6,4,6 & 6,6 & 6,8 \\ \end{matrix} $$
The magic numbers to add to $k$ when guessing would be:
$$ \begin{matrix} 1 & 2,3 & 2,4 \\ 2,6,8,12,14 & 2,6,8,12,18 & 2,6,12,14 \\ 2,6,12,18 & 2,8,12,14,18 & 2,8,12,14,20 \\ 2,8,12,18 & 4,6,10,12 & 4,6,10,16,18 \\ 4,6,10,16,22 & 4,6,12 & 4,10,12 \\ 4,10,16 & 4,10,18 & 6,8,14,18,20,24 \\ 6,8,14,18,20,26 & 6,10,12,16 & 6,10,12,18 \\ 6,10,16 & 6,12 & 6,14 \\ \end{matrix} $$
It's imperative that the trials are done in order from left to right and top to bottom in this table, else, you will get false information. An example of one optimization is to avoid guessing when the only possible combination to continue with is 1 because we know that $n + k$ is prime.
An example:
- You tested $k + 4$, $k + 10$, and you're testing for $k + 12$
- You're now testing for $k + 16$
- You're now testing for $k + 18$
That last step is redundant. If $k + 16$ is composite, you can skip the $k + 18$ step because you know it will be prime.
I hope this is clear enough.
To get a somewhat efficient algorithm, we can first compute for several choices of $x$ what the answers of Alice would be, for each choice of $n$ between $1$ and $100$.
As noted by Charles, no matter what $x$ is, for at most $26$ of the $100$ possible choices of $n$ will the answer be "Yes, $n + x$ is prime." This maximum information rate is achieved only by choosing $x = 1$, so we will want to ask this question as our first question. There are five choices of $x$ for which there are $25$ numbers where the answer is "Yes", which are $2, 3, 4, 9, 10$. For simplicity, let us assume that we first query the first $4$ numbers with such a high "information rate": $$x \in \{1, 2, 3, 4\}.$$ Now, for each choice of $n$, we can compute what the answers would have been. For the numbers $n = 1, 2, 3, 4$ we would get a match and be done, while for the other $96$ numbers there are only $7$ possible sequences of answers. Along with the choices of $n$ that lead to these answers, these sequences are: $$\begin{align} NNNN &: \{23, 24, 31, 32, 47, 48, 53, 54, 61, 62, 73, 74, 83, 84, 89, 90, 91, 92\} \\ NNNY &: \{7, 13, 19, 25, 33, 37, 43, 49, 55, 63, 67, 75, 79, 85, 93, 97\} \\ NNYN &: \{8, 14, 20, 26, 34, 38, 44, 50, 56, 64, 68, 76, 80, 86, 94, 98\} \\ NYNN &: \{5, 11, 17, 21, 29, 35, 41, 45, 51, 59, 65, 71, 77, 81, 87, 95\} \\ YNNN &: \{6, 12, 18, 22, 30, 36, 42, 46, 52, 60, 66, 72, 78, 82, 88, 96\} \\ NYNY &: \{9, 15, 27, 39, 57, 69, 99\} \\ YNYN &: \{10, 16, 28, 40, 58, 70, 100\} \end{align}$$ So with $4$ questions, we narrow down the search space to at most $18$ numbers. For each group, we may be able to choose the follow-up questions such that in total, we may need only about $10$ questions or so, but this will be very complicated. Of course, we could query each of the at most $18$ numbers in each of the groups, for a total of at most $4 + 18 = 22$ questions, but that would obviously not be optimal.
A somewhat simpler strategy would be to ask more questions in the initial stage, such as first querying $$x \in \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}.$$ In this case, there are $48$ possible strings of answers (and $10$ exact matches), and each group contains $3$ or fewer values of $n$ that lead to these answers. So once we know the answers to these $10$ queries, we are able to narrow down the search space to at most $3$ numbers, and with at most $2$ questions we may then be able to determine the correct value of $n$. So this would lead to a worst-case complexity of $10 + 2 = 12$ questions.