Project Euler 869 - Prime Guessing

Official link:

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)