Version:

recursion =>tree ( decision tree) with edges weighted by probabilities.

Consider terminal nodes 1,...,n, which contain primes. Prob p(i) for each terminal is prob of path from tree root to node = product of probs on edges. Let g(i) number of gcd calculations for each terminal. Mean = sum of p(i)*g(i).

Let we have 8=2^3- root. From it going out 4 edges: r1=2*(2*k+1) with p1=0.25,

and going to v=2-terminal and v=4-recursion, r2=4*(2*k+1) with p1=0.125 also in v=2

and v=4 and r3=(2*k+1) with p3=0.5 - loop in v=8, r4= 8*k with p4=1/8- loop to 8. Loops correspond to infinite geometric progression.

we have F(8)=(1/2 +1/8)(F(8)+1)+(1/4+1/8)(F(4)+1)+(1/4+1/8)*(F(2)+1)

where F(2)=0. By the way: 1/8+1/2+1/4+1/8=1 - this must be for earch inner node.

*Edited by author 23.10.2011 06:03*

*Edited by author 23.10.2011 06:12*

Thank you, svr, you really helped me.

But let me fix you:

F(8) = (1/2+1/8)*(F(8)+1) + 1/4*(F(2)+F(4)+1) + 1/8*(F(4)+F(2)+1)

got AC using this approach

*Edited by author 30.10.2011 05:23*