Thought Process

First thing I did, which I always do for these types of problems, is to create a Monte-Carlo simulation to get an approximate answer. At first I couldn't tell much except for the fact that as n increases F(n) decreases slowly, of course given the nature of the problem I expect that it will converge to some value and hence I did a bunch of trials for a large amount of birds

1. F(1,000) ~ 0.3891118158078133 with 10,000 trials

2. F(10,000) ~ 0.38893046519289154 with 10,000 trials

3. F(100,000) ~ 0.3888896339813669 with 1,000 trials

4. F(1,000,000) ~ 0.3888891119536712 with 100 trials

The trial size goes down so the accuracy is affected but from this I conjectured that F(n) goes towards 0.38888.... which WolframAlpha told me is 7/18.

Given the relative simplicity of this fraction I again conjectured 2 things:

1. F(n) would always have a nice fraction

2. If the first point is true, that F(n) = (7n + a)/(18n + b)

To test this I used the fractions module limit_denominator() method which given a decimal, will approximate it as a fraction with a given denominator size.

Firstly, I got an approximate value for all values n = 4 to 7, using 10,000,000 trials, then again using 100,000,000 trials and tested the fraction I got when I limited the denominator to 100 and 1,000. I show my results below:

1. 4 birds:

   1. 10,000,000 trials:

      1. limit_denominator = 1,000: 443/927

      2. limit_denominator = 100: 43/90

   2. 100,000,000 trials:

      1. limit_denominator = 1,000: 333/697

      2. limit_denominator = 100: 43/90

2. 5 birds:

   1. 10,000,000 trials:

      1. limit_denominator = 1,000: 444/959

      2. limit_denominator = 100: 25/54

   2. 100,000,000 trials:

      1. limit_denominator = 1,000: 231/499

      2. limit_denominator = 100: 25/54

3. 6 birds:

   1. 10,000,000 trials:

      1. limit_denominator = 1,000: 181/400

      2. limit_denominator = 100: 19/42

   2. 100,000,000 trials:

      1. limit_denominator = 1,000: 375/829

      2. limit_denominator = 100: 19/42

4. 7 birds:

   1. 10,000,000 trials:

      1. limit_denominator = 1,000: 4/9

      2. limit_denominator = 100: 4/9

   2. 100,000,000 trials:

      1. limit_denominator = 1,000: 4/9

      2. limit_denominator = 100: 4/9

Using this it is clear that F(7) = 4/9, now using my conjectured point 2, and F(3) = 1/2, I can calculate a = 15, b = 18.

Then, to my amazement using F(n) = (7n + 15)/(18n + 18) I get F(5) = 25/54, F(6) = 19/42, exactly as I guessed!

Being pretty sure this was the correct closed form for F(n), I just ran my code for all primes less than a million and voila!