Vrftsjtryk

You start with the number 1536. Your mission is to get to 1 in as few steps as possible. At each step, you may either multiply or divide the number you have, by either 2 or 3; but, only if the result is a whole number whose first digit is 1, 3, 4, or 9. That is all.

As Jo has already shown, this can be accomplished in

28 steps. This is minimal, and it can be proven.

To help visualize this problem, we can imagine:

A two-dimensional grid/chart where each point is a number of the form $3^x2^y$, with $(x,y)$ as the relevant co-ordinates. We want to find a path from $(1,9)$ to $(0,0)$ while making only one step up/down/left/right at a time, and ensuring that the numbers we step on have their most significant digit in the set {1,3,4,9}.

Here is what the chart looks like for the range $(0,0)$ to $(10,10)$. The dashes represent numbers that do not begin with {1,3,4,9}, and so are unusable in our path.
1024 3072 9216 ---- ---- ---- ---- ---- ---- ---- ---- .
---- 1536 4608 13824 41472 124416 373248 1119744 3359232 10077696 30233088 .
---- ---- ---- ---- ---- ---- 186624 ---- 1679616 ---- 15116544 .
128 384 1152 3456 10368 31104 93312 ---- ---- ---- ---- .
---- 192 ---- 1728 ---- 15552 46656 139968 419904 1259712 3779136 .
32 96 ---- ---- ---- ---- ---- ---- ---- ---- 1889568 .
16 48 144 432 1296 3888 11664 34992 104976 314928 944784 .
---- ---- ---- ---- ---- 1944 ---- 17496 ---- 157464 472392 .
4 12 36 108 324 972 ---- ---- ---- ---- ---- .
---- ---- 18 ---- 162 486 1458 4374 13122 39366 118098 .
1 3 9 ---- ---- ---- ---- ---- ---- 19683 ---- .

From here, we can see two different routes of 28 steps each: (1536->373248->93312->384->48->3888->972->36->9->1) and (1536->373248->46656->3779136->944784->3888->972->36->9->1).

Proving minimality:

Since a path of length 28 exists (we've found two), we can rule out anything that's too far away to be used in a shortest path.

Moving from (1,9) to (0,0) must take at least ten steps on its own, so we can move at most nine steps completely out of the way (and nine steps back) in a shortest route. That limits us to only considering x-coordinates up to 10; any further would require making at least ten '*3' steps, eleven '÷3' steps, and at least nine '÷2' steps, putting the route definitely longer than 28.

With our x-coordinate limited to [0,10], we now look at the bottlenecks.

It should be clear that any shortest route must start by going from 1536 to 93312 in seven steps, and must end by going from 3888 to 1 in nine steps. These are both forced by unique bottlenecks; there is only one way to step from $(x,7)$ to $(x,6)$ and only one way to step from $(x,3)$ to $(x,2)$ in this range.

This leaves at most twelve steps to go from 93312 to 3888. Either by observation or by pointing out that there are only two ways to go from $(x,6)$ to $(x,5)$, we can see that there are exactly two shortest routes from 93312 to 3888, and both require all twelve steps.

Therefore, the shortest route is 28 steps, and there are exactly two ways to do so, both of which are described in Jo's solution and below the chart.

Not sure if it is the quickest, but I found two ways to do it with 28 steps:

   1536

*3 4608

*3 13824

*3 41472

*3 124416

*3 373248

/2 186624

/2 93312

/2 46656

*3 139968

*3 419904

*3 1259712

*3 3779136

/2 1889568

/2 944784

/3 314928

/3 104976

/3 34992

/3 11664

/3 3888

/2 1944

/2 972

/3 324

/3 108

/3 36

/2 18

/2 9

/3 3

/3 1

and

   1536

*3 4608

*3 13824

*3 41472

*3 124416

*3 373248

/2 186624

/2 93312

/3 31104

/3 10368

/3 3456

/3 1152

/3 384

/2 192

/2 96

/2 48

*3 144

*3 432

*3 1296

*3 3888

/2 1944

/2 972

/3 324

/3 108

/3 36

/2 18

/2 9

/3 3

/3 1

Not sure if this is relevant to the topic, but I wrote a python program that recursively builds sequences for valid operations. I limited it to 32 steps, so it will output the 2 optimal 28-steps solutions and 26 more for 30 and 32 steps (there are no 29/31 steps solutions)

Operations: 0: *3, 1: *2, 2: /2, 3: /3

def get_next(sequence, prev_op):

    crt = sequence[-1]



    if crt == 1536:

        print((len(sequence) - 1), sequence)

        return



    if len(sequence) > 32: return



    if prev_op != 3 and str(crt * 3)[0] in '1349':

        get_next(sequence + [crt * 3], 0)

    if prev_op != 2 and str(crt * 2)[0] in '1349':

        get_next(sequence + [crt * 2], 1)

    if prev_op != 1 and crt % 2 == 0 and str(crt // 2)[0] in '1349':

        get_next(sequence + [crt // 2], 2)

    if prev_op != 0 and crt % 3 == 0 and str(crt // 3)[0] in '1349':

        get_next(sequence + [crt // 3], 3)



get_next([1], 2)

I like the Python solution from user54653. I wrote this brute force solution before I looked at theirs. Runs under py2 or py3. This solution is a little more glitzy. I track the operations made as well as the numeric sequence.

def find_sequence(target):

    queue = [1]

    seen = {1: [(1, '*1')]}  # prevent loops



    while queue:

        current = queue.pop(0)

        steps = seen[current]



        if current == target:

            return steps



        # notice the use of slice copying ([:]). Without this the same

        # list would be reused in multiple places leading to incorrect

        # results.



        for i in (2, 3):

            next, rem = divmod(current, i)

            if rem == 0 and next not in seen:

                if str(next)[0] in ['1', '3', '4', '9']:

                    queue.append(next)

                    seen.setdefault(next, steps[:]).append((next, '/{}'.format(i)))

        for i in (2, 3):

            next = current * i

            if next not in seen and str(next)[0] in ['1', '3', '4', '9']:

                queue.append(next)

                seen.setdefault(next, steps[:]).append((next, '*{}'.format(i)))



    return None  # failed to compute a result.





print(find_sequence(1536))