12
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ "first digit" meaning the ones digit, or "first digit" meaning most significant digit? $\endgroup$ – Hugh Dec 12 '18 at 2:46
  • 1
    $\begingroup$ @Hugh - most significant. $\endgroup$ – deep thought Dec 12 '18 at 2:51
  • $\begingroup$ I wonder if the fact that the prime factorization of 1536 is $2^9 \times 3$. That puts a lower bound of at least 10 operations, but it must be more since just trying possibilities shows that there must be some multiplications in there. $\endgroup$ – Hugh Dec 12 '18 at 3:03
48
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I agree that this deserves to be the accepted answer. Jo's answer does deserve an upvote as well for being first and correct though. $\endgroup$ – Imus Dec 12 '18 at 13:16
  • 1
    $\begingroup$ @Chris - I meant minimal, as in minimal distance through the maze. I did not specify 'prove it' or anything like that in the question. Thus I must consider the other answer complete. I am unwilling to change the question after the fact. $\endgroup$ – deep thought Dec 12 '18 at 14:35
  • 1
    $\begingroup$ @Chris - I don't know enough about other stacks, but perhaps one difference is that, around here, there is often an "intended answer". And too often OP moves the goalposts to suit that answer :-) There is a "meta" question here, which I may post .... but later. $\endgroup$ – deep thought Dec 12 '18 at 15:05
  • 2
    $\begingroup$ Yeah. I quite agree that moving goalposts is bad but I don't think that's what I'm suggesting, I'm just suggesting an answer with workings is better than one without. I agree that it might be interesting meta conversation to be had to see if there is a consensus on things like whether questions should all be assumed to have implicit "And show your workings/thought process/etc." and so on. Though it may be there is already a meta question on this subject... $\endgroup$ – Chris Dec 12 '18 at 15:24
  • 1
    $\begingroup$ This grid explains why all solutions will have an even number of steps: just color the squares like a checkerboard. $\endgroup$ – mathmandan Dec 12 '18 at 18:44
19
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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)
$\endgroup$
  • $\begingroup$ Python has a function called divmod which returns the result of dividing and modulus. next, rem = divmod(crt, 2) for instance. This would save you the doubled division. $\endgroup$ – Sean Perry Dec 13 '18 at 0:27
  • $\begingroup$ It's obvious that there are no solutions with an odd number of steps. The starting number has $10$ prime factors, the target has none, and you get one factor more or fewer at each step. $\endgroup$ – David Dec 16 '18 at 23:41
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ If anyone can offer a way to bury this in a spoiler tag I would love to hear it. $\endgroup$ – Sean Perry Dec 13 '18 at 0:59

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.