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