Given $x$, $y$, $k$, convert $x$ to $y$ by multiplication by $k$ or subtraction of $1$ in the fewest steps 
Problem Statement:
We are given three positive integers $x$, $y$, and $k$, and our aim is to convert $x$ to $y$ in the minimum number of steps using one of the following two operations at each step:

*

*Multiply $x$ by $k$

*Subtract $1$ from $x$

Let convert($x$,$y$,$k$) be the minimum number of steps to convert $x$ to $y$ using $k$. Then find the values for the following:


*

*convert(3,10,2)

*convert(4,92,3)

*convert(11,104250,2)

Note: Following are the official answers for the three parts mentioned above:

*

*3

*7

*24

My Approach: I think it is easier to go the other way round, i.e., to convert $y$ to $x$ using the opposite operations, which is to divide by $k$ or add $1$ at each step. I think this is easier because it restricts the possible cases as division is possible only when the number is a multiple of k. And while doing this we can avoid repeated calculations in case we encounter the same number some time later. For example, for convert(3,10,2), we have this,
I even coded a Breadth First Search solution for this problem (thought it is not so useful as the question was asked in a pen and paper based exam):

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll INF = 1e16;

int main() {    
    const int lim = 10000;
    int t;
    cin >> t;
    while(t--) {
        ll x, y, k;
        cin >> x >> y >> k;
        map<ll,bool> vis;
        map<ll,int> dist;
        queue<ll> q;
        q.push(y);
        vis[y] = true;
        bool found = false;
        while(!q.empty()) {
            int u = q.front();
            q.pop();
            if(u == x) {
                found = true;
                break;
            }
            if(dist[u] < lim) {
                if(u+1<INF && !vis[u+1]) {
                    vis[u+1] = true;
                    dist[u+1] = 1+dist[u];
                    q.push(u+1);
                }
                if(u%k == 0 && !vis[u/k]) {
                    vis[u/k] = true;
                    dist[u/k] = 1+dist[u];
                    q.push(u/k);
                }
            }
        }
        if(found) cout << dist[x] << "\n";
        else cout << "-1\n";
    }
                
    return 0;
}


So my question is:

Can we do something better than to look through each possibility? Any observations that can help? I am looking for an answer that can help compute the values without the help of a computer.

 A: (Fill in the gaps as needed. You should have everything that you need listed out here.)
Observations:

*

*Each valid sequence of steps can be written as $ k (k (k ( \ldots ( x - a_n) - a_{n-1} ) - \ldots - a_1) - a_0= y $. This takes $ n + \sum_{i=0}^n a_i$ steps. This is a bijection.

*Rewrite this as $k^n x - y = \sum a_i k^n$.

*In particular, if $ k^n x - y < 0$, then there is no solution using multiplication by $k$ exactly $n$ times. (This should be obvious from the start).

*For a fixed $N$ and $n$, the minimal $\sum_{i=0}^n a_i$ such that $ N=\sum_{i=0}^n a_i k^n$ happens when $ a_i < k$ for $ i < n$. There is a unique representation corresponding to the base $k$ representation of $N$. Note that $a_n$ is as large as it needs to be.

*Hence, given a fixed $n, x, y, k$, the calculation for the minimum is straight forward.

*We just need to test a several values of $n$, starting with $ \lceil \log_k \frac{y}{x} \rceil $, until $n >$ the minimum number of steps we're calculated so far. Note that the minimum doesn't always occur for the minimum $n$.

For example, in the first case,

*

*$ 3 \times 2^1 - 10 < 0$, so no solution here.

*$ 3 \times 2^2 - 10  = 2 = ( 1 \times 2^1) $ will take $ 2 + 1 = 3 $ steps.

*$ 3 \times 2^3 - 10  = 14 = ( 1 \times 2^3 + 1\times 2^2 + 1 \times 2 )$ will take $ 3 + 3 = 6 $ steps.

*We stop here since any larger $n$ is greater than the minimal steps calculated at this point.

And for the last case,

*

*Start with $\lceil \log_2 104250 / 11 \rceil = 14$.

*$11 \times 2^{14} - 104250 = 75974 = 410100011000110_2$, which takes $ 14 + 10 = 24$ steps.

*$ 11 \times 2^{15} - 104250 = 256198  = 7110100011000110_2$, which takes $ 15 + 14 = 29$ steps.

*Try $ n = 16, 17, \ldots, 24$ and see how many steps those take.

*Here is the process for $11\times 2^{14}$ to get to $104250$.


