Steven Byrne Steven Byrne - 1 month ago 6
Python Question

counting back generations of a number

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:

x = 1
y = 1
new_generation = y+x
x OR y = new_generation


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:

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]


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).

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...

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 > f:
m = m-f
#If F is greater, I know the last generation added M to M, so remove it
elif f > 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"))


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!).


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)



Here are some test cases with their answers:


f = "1"
m = "2"
Output: "1"

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

f = "4"
m = "2"
Output: "impossible"



Any help is much appreciated! P.S. I am running Python 2.7.6

Answer

You are on the right track with the top-down approach you posted. You can speed it up by a huge factor if you use integer division instead of repeated subtraction.

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))
    counter = 0
    #While I have not reduced my given numbers to my starting numbers....
    while m != 0 and f != 0:
        print(m, f, counter, sep="\t")
        #If M is greater, I know the last generation added F to M, so remove it
        if m > f:
            counter += m // f
            m %= f
        #If F is greater, I know the last generation added M to M, so remove it
        elif f > m:
            counter += f // m
            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 - 1)

Using the above, answer(23333, 30000000000) yields

23333   30000000000 0
23333   15244   1285732
8089    15244   1285733
8089    7155    1285734
934 7155    1285735
934 617 1285742
317 617 1285743
317 300 1285744
17  300 1285745
17  11  1285762
6   11  1285763
6   5   1285764
1   5   1285765
1285769

and answer(4, 7) yields

4   7   0
4   3   1
1   3   2
4