counting back generations of a number
<p>I am trying to reverse engineer a set of numbers given to me (f,m) I need to go through and find how many generations it takes starting from 1,1 using the algorithm below for each generation:</p>

<pre><code>x = 1
y = 1
new_generation = y+x
x OR y = new_generation
</code></pre>

<p>IE, I do not know if X, or Y is changed, the other variable is left the same... A list of possible outputs would look like this for the ending values of 4 and 7:</p>

<pre><code>f = 4
m = 7
[1, 1]
[2, 1, 1, 2]
[3, 1, 2, 3, 3, 2, 1, 3]
[4, 1, 3, 4, 5, 3, 2, 5, 5, 2, 3, 5, 4, 3, 1, 4]
[5, 1, 4, 5, **7, 4**, 3, 7, 7, 5, 2, 7, 7, 2, 5, 7, 7, 3, **4, 7**, 5, 4, 1, 5]
</code></pre>

<p>Where every two sets of numbers (2,1) and (1,2) are a possible output. Note the ** denote the answer (in this case the order doesn't matter so long as both m and f have their value in the list).</p>

<p>Clearly there is exponential growth here, so I can't (or it less efficient) to make a list and then find the answer; instead I am using the following code to reverse this process...</p>

<pre><code>def answer(m,f):
    #the variables will be sent to me as a string, so here I convert them...
    m = (int(m))
    f = (int(f))
    global counter
    #While I have not reduced my given numbers to my starting numbers....
    while m != 1 or f != 1:
        counter +=1
        #If M is greater, I know the last generation added F to M, so remove it
        if m &gt; f:
            m = m-f
        #If F is greater, I know the last generation added M to M, so remove it
        elif f &gt; m:
            f = f-m
        else:
            #They can never be the same (one must always be bigger, so if they are the same and NOT 1, it can't be done in any generation)
            return "impossible"
    return str(counter)

print(answer("23333","30000000000"))
</code></pre>

<p>This returns the correct answer (for instance, 4,7 returns "4" which is correct) but it takes to long when I pass larger numbers (I must be able to handle 10^50, insane amount, I know!). 
<hr>
My thought was I should be able to apply some mathematical equation to the number to reduce it and them multiple the generations, but I'm having trouble finding a way to do this that also holds the integrity of the answer (for instance, if I divide the bigger by the smaller, on small numbers (7, 300000) I get a very close (but wrong) answer, however on closer numbers such as (23333, 300000) the answer is no where even close, which makes sense due to the differences in the generation path). Note I have also tried this in a recursive function (to find generations) and using the a non-reversed method (building the list and checking the answer; which was significantly slower for obvious reasons)</p>

<p><hr>
Here are some test cases with their answers:</p>

<blockquote>
<pre><code>f = "1"
m = "2"
Output: "1"

f = "4"
m = "7"
Output: "4"

f = "4"
m = "2"
Output: "impossible"
</code></pre>
</blockquote>

<p>Any help is much appreciated! P.S. I am running Python 2.7.6</p>

<p>[EDIT]
<hr>
The below code is working as desired.</p>

<pre><code>from fractions import gcd

def answer(m,f):
    #Convert strings to ints...
    m = (int(m))
    f = (int(f))

    #If they share a common denominator (GCD) return impossible
    if gcd(m,f) != 1:
        return "impossible"
    counter = 0
    #While there is still a remainder...
    while m != 0 and f != 0:
        if m &gt; f:
            counter += m // f
            #M now equals the remainder.
            m %= f
        elif f &gt; m:
            counter += f // m
            f %= m
    return str(counter - 1)
</code></pre>

<p>Try a form of recursion:</p>

<p>(Python 2.7.6)</p>

<pre><code>def back():
    global f,m,i
    if f&lt;m:
        s=m//f
        i+=s
        m-=s*f
    elif m&lt;f:
        s=f//m
        i+=s
        f-=s*m
    else:
        return False
    return True
while True:
    f=int(raw_input('f = '))
    m=int(raw_input('m = '))
    i=0
    while True:
        if f==m==1:
            print 'Output:',str(i)
            break
        else:
            if not back():
                print 'Output: impossible'
                break
    print
</code></pre>

<p>(Python 3.5.2)</p>

<pre><code>def back():
    global f,m,i
    if f&lt;m:
        s=m//f
        i+=s
        m-=s*f
    elif m&lt;f:
        s=f//m
        i+=s
        f-=s*m
    else:
        return False
    return True
while True:
    f=int(input('f = '))
    m=int(input('m = '))
    i=0
    while True:
        if f==m==1:
            print('Output:',str(i))
            break
        else:
            if not back():
                print('Output: impossible')
                break
    print()
</code></pre>

<p>Note: I am a Python 3.5 coder so I have tried to backdate my code, please let me know if there is something wrong with it.</p>

<p>The input format is also different: instead of <code>f = "some_int"</code> it is now <code>f = some_int</code>, and the output is formatted similarly.</p>

python loops recursion mathematical-optimization