# 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:

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!

# Interactive Code

Input an integer (yourinput)

Code will output E(yourinput)