Minimum moves to reach k

This is an interesting problem in number theory, including linear Diophantine equations. Since there are solutions available on line, I gather that you want help in deriving the algorithm yourself.

Restate the problem: you start with two numbers characterized as 1*m+0*n, 0*m+1*n. Use the shorthand (1, 0) and (0, 1). You are looking for the shortest path to any solution to the linear Diophantine equation

a*m + b*n = k

where (a, b) is reached from starting values (1, 1) a.k.a. ( (1, 0), (0, 1) ).

So ... starting from (1, 1), how can you characterize the paths you reach from various permutations of the binary enhancement. At each step, you have two choices: a += b or b += a. Your existing algorithm already recognizes this binary search tree.

These graph transitions -- edges along a lattice -- can be characterized, in terms of which (a, b) pairs you can reach on a given step. Is that enough of a hint to move you along? That characterization is the key to converting this problem into something close to a direct computation.

Non-Recursive Algorithm based on Priority Queue (using Heap)

State: (sum_, m, n, path)
    sum_ is current sum (i.e. m + n)
    m and n are the first and second numbers
    path is the sequence of (m, n) pairs to get to the current sum

In each step there are two possible moves

1. Replace first number by the sum
2. Replace second number by the sum

Thus each state generates two new states. States are prioritized by:

1. moves: states with a lower number of have higher priority
2. sum: States with higher sums have higher priority

We use a Priority Queue (Heap in this case) to process states by priority.

Code

from heapq import heappush, heappop

def calc1(k):
  if k < 1:
    return None, None  # No solution

  m, n, moves = 1, 1, 0
  if m == k or n == k:
    return moves, [(m, n)]

  h = []  # Priority queue (heap)
  
  path = [(m, n)]
  sum_ = m + n
  # Python's heapq acts as a min queue.
  # We can order thing by max by using -value rather than value
  # Thus Tuple (moves+1, -sum_, ...) prioritizes by 1) min moves, and 2) max sum
  heappush(h, (moves+1, -sum_, sum_, n, path))
  heappush(h, (moves+1, -sum_, m, sum_, path))

  while h:
    # Get state with lowest sum
    moves, sum_, m, n, path = heappop(h)
    
    sum_ = - sum_

    if sum_ == k:
      return moves, path  # Found solution

    if sum_ < k:
      sum_ = m + n  # new sum
      # Replace first number with sum
      heappush(h, (moves+1, -sum_, sum_, n, path + [(sum_, n)]))
      # Replace second number with sum
      heappush(h, (moves+1, -sum_, m, sum_, path + [(m, sum_)]))
  
    # else:
    #  so just continues since sum_ > k

  # Exhausted all options, so no solution
  return None, None

Test

Test Code

for k in [5, 100, 1000]:
  moves, path = calc1(k)
  print(f'k: {k}, Moves: {moves}, Path: {path}')

Output

k: 5, Moves: 3, Path: [(1, 1), (2, 3), (2, 5)]
k: 100, Moves: 10, Path: [(1, 1), (2, 3), (5, 3), (8, 3), (8, 11),
                         (8, 19), (27, 19), (27, 46), (27, 73), (27, 100)]
k: 1000, Moves: 15, Path: [(1, 1), (2, 3), (5, 3), (8, 3), (8, 11),
                          (19, 11), (19, 30), (49, 30), (79, 30), (79, 109), 
                          (188, 109), (297, 109), (297, 406), (297, 703), (297, 1000)]

Performance Improvement

Following two adjustments to improve performance

1. Not including path just number of steps (providing 3X speedup for k = 10,000
2. Not using symmetric pairs (provided 2x additional with k = 10, 000

By symmetric pairs, mean pairs of m, n which are the same forward and backwards, such as (1, 2) and (2, 1).
We don't need to branch on both of these since they will provide the same solution step count.

Improved Code

from heapq import heappush, heappop

def calc(k):
  if k < 1:
    return None, None

  m, n, moves = 1, 1, 0
  if m == k or n == k:
    return moves

  h = []    # Priority queue (heap)
  
  sum_ = m + n
  heappush(h, (moves+1, -sum_, sum_, n))

  while h:
    moves, sum_, m, n = heappop(h)
    sum_ = - sum_

    if sum_ == k:
      return moves

    if sum_ < k:
      sum_ = m + n
      steps = [(sum_, n), (m, sum_)]
      heappush(h, (moves+1, -sum_, *steps[0]))
      if steps[0] != steps[-1]: # not same tuple in reverse (i.e. not symmetric)
        heappush(h, (moves+1, -sum_, *steps[1]))

Performance

Tested up to k = 100, 000 which took ~2 minutes.

Update

Converted solution by @גלעדברקן from JavaScript to Python to test

def g(m, n, memo):
  key = (m, n)
  
  if key in memo:
    return memo[key]
  
  if m == 1 or n == 1:
    memo[key] = max(m, n) - 1
    
  elif m == 0 or n == 0:
    memo[key] = float("inf")

  elif m > n:
    memo[key]  = (m // n) + g(m % n, n, memo)

  else:
    memo[key]  = (n // m) + g(m, n % m, memo)
    
  return memo[key] 

def f(k, memo={}):
  if k == 1:
    return 0

  return min(g(k, n, memo) for n in range((k // 2) + 1))

Performance of @גלעדברקן Code

Completed 100K in ~1 second 

This is 120X faster than my above heap based solution.

We can do much better than the queue even with brute force, trying each possible n when setting m to k. Here's JavaScript code, very close to Python syntax:

function g(m, n, memo){
  const key = m + ',' + n;
  
  if (memo[key])
    return memo[key];
  
  if (m == 1 || n == 1)
    return Math.max(m, n) - 1;
    
  if (m == 0 || n == 0)
    return Infinity;
  
  let answer;
  
  if (m > n)
    answer = Math.floor(m / n) + g(m % n, n, memo);
  else
    answer = Math.floor(n / m) + g(m, n % m, memo);
    
  memo[key] = answer;
  return answer;
}

function f(k, memo={}){
  if (k == 1)
    return 0;
  let best = Infinity;
  for (let n=1; n<=Math.floor(k/2); n++)
    best = Math.min(best, g(k, n, memo));
  return best;
}

var memo = {};
var ks = [1, 2, 5, 6, 10, 100, 1000, 100000];
  
for (let k of ks)
  console.log(`${ k }: ${ f(k, memo) }`);

By default, in Python, for a recursive function the recursion limit is set to 10^4. You can change it using sys module:

import sys 
sys.setrecursionlimit(10**6)