Thought Process

This was a super fun problem!

My idea was very simple, create a tree where the leaves are the primes in binary form where left is the 0 bit and right is the 1 bit. This means our nodes are the primes with the same prefix sequence up till that node. 

For example in the N = 10 case we have the tree:

        ______
      /                      \
    [2]                [3, 5, 7]
  /     \              /                \
[]     [2]    [5]              [3, 7]
                  /     \            /        \
                []     [5]      []        [7]

Now our Strategy is simple: Pick 0, 1 depending on if the left or right subtree root node has more elements (That is, you are more likely to get a point), if your guess is correct continue down that subtree, otherwise switch subtree.

I detail the E(10) case:

1. We don't know anything [3, 5, 7] > [2] so we guess "1"

   1. If p = 2, then we don't get a point, so we go to the left subtree

      1. Now [2] > [] so we guess "1" and we get a point and we are done

   2. If p = 3, 5, 7 we get a point, continue down the right subtree

      1. [3, 7] > [5] therefore we guess "1"

         1. If p = 3, we get a point and we are done

         2. If p = 5, we don't get a point, go down left subtree

            1. Now [5] > [], therefore we guess "1" and we get a point and we are done

         3. if p = 7, we get a point, go down right subtree

            1. Now [7] > [], therefore we guess "1" and we get a point and we are done

Following this strategy if p = 2, 3, 5, 7 we get 1, 2, 2, 3 points respectively for an average of (1 + 2 + 2 + 3)/4 = 2 as desired.

It's a fun problem in itself to create the tree and visualize the problem as it helped me realize my earlier
(non-sensical when I look back at them) strategies were wrong. 

After I did this I just generated all primes, created the tree and then played the game for each prime. This method took me around 283 seconds but I quickly realized this can be done much faster, skipping the entire tree generation by using recursion. 

I give a brief outline of the idea as if you actually finish the problem it should be simpel to figure out!

1. Go through the list of primes in binary form (For example p = 2 becomes 01), and create 2 sublists p0, and p1 which contain all primes with the bit 0 and 1 at the front but we remove their first bit to be processed in the next stage of recursion.

   1. Following the above strategy we will guess the bigger sublist and get those number of points. Hence we get the max(size of p0, size of p1) and then we continue the recursion process on p0 and p1