This problem came up during the Google CTF 2017. For background information about the challenge you can search for `GoogleCTF A7 ~ Gee cue elle`.

Problem description:

 - A random number `N` between `0` and `39402006196394479212279040100143613805079739270465446667948293404245721771497210611414266254884915640806627990306815` (`~3.9*10^115` or `64^64`) is selected
 - You have to find the correct number `N`
 - You can take a guess `X`, and get a response whether the number `X` is greater or lower than `N`
 - The twist:
  - you can only perform 13 guesses in 30s without hitting a 90s timeout - `13/30`
  - if your guess was lower, then you get an error and you can only have 2 errors in 30s without a 90s timeout - `2/30`
  - you have only `2240s` time to find the correct value

I had a short discussion with the challenge creator about the solution and he solved it like the [broken egg](http://datagenetics.com/blog/july22012/index.html) problem. His algorithm basically runs in constant time. As max number is `64^64`, he divides the problem in 64 buildings with 64 floors. And a broken egg is an error. This means it takes overall pretty constant 1920s. I think the problem is not equivalent to the egg problem, but somehow the algorithm performs here really really well.

I chose a skewed binary search. Instead of splitting the search field into 50:50, I skew to one side `2/13=0.15` 15:85. This way the probability of hitting the punishing error condition is pretty unlikely. My intuition tells me, that this should be the most efficient algorithm, but apparently it's not.

1. I thought the `0.15` skew would be the best ratio, but after analysing the time it takes with different ratios, the most efficient value seems to be around `~0.22`. My calculation is obviously wrong, but what would have been the correct calculation to find `~0.22`?

[![average time in seconds for different skews][1]][1]


  [1]: https://i.sstatic.net/do9Mu.png

2. Why does the egg problem algorithm perform better (as in faster on average)?
3. What is the on average fastest algorithm here? And why is it not based on a skewed binary search?

Any thoughts and comments are welcome.