Generate any number in the fewest step using multiply by 2 or divide by 3?

Here is a BFS dynamic programming solution.

#! /usr/bin/env python
wanted = 7
found = {1: None}
added = [1]
while True:
    new_added = []
    for x in added:
        if 2*x not in found:
            found[2*x] = [x, 2]
            new_added.append(2*x)
        if x/3 not in found:
            found[x/3] = [x, 3]
            new_added.append(x/3)
    if wanted in found:
        break
    # This magic line copies new_added over the added array.
    added[:] = new_added

answer = []
path = [wanted]
while path[-1] != 1:
    node = found[path[-1]]
    path.append(node[0])
    answer.append(node[1])

print([x for x in reversed(answer)])
print([x for x in reversed(path)])

Here is an explanation.

BFS means Breadth-First Search. In this case we are searching in parallel through all paths of lengths 1, 2, 3, etc until we are done.

Dynamic Programming refers to any of a variety of methods to store a record of work done so that we can either avoid work, or refer back to already done work.

In this case found is a record of all numbers that we have found a path to with the integer you get there from, and what operation to use. added is the record of all integers that we found on the last pass. new_added is all of the integers that we found on this pass.

So we start with a record saying that we know how to get to 1. Then in each pass we take all of the just added records and see what new ones we get to by multiplying by 2 or dividing by 3.

We stop once we found our target. And then it is a question of finding the path back through found to get back to 1. This gives us our answer but in reverse order - the end of the path is at the start of our list. So reverse it and we have our answer.

Which I displayed both as a record of all of the numbers we visit and as a record of the operations.

--- EDIT: DOES NOT FIND THE SHORTEST SOLUTION ---

After describing the following algorithm, I was told that it does not find the shortest solution.

My idea is to start from our number N, repetitively multiply by 3 (considering the uncertainty range that integer division by 3 introduces for the product), and check if a power of two lies witin the current uncertainty range.

E.g. for N=7:

• Range0 = 7...7, no power of 2 in range
• Range1 = 21...23, no power of 2 in range
• Range2 = 63...71, a power of 2, being 2^6 = 64, lies within the range, so the solution is 2^6 / 3^2 = 7.

I'm not sure that every natural number N can be reached that way. So the algorithm might not terminate.

And I feel the intermediate numbers can get quite large even for small N values, so a BigInteger implementation will probably be necessary.

If N = 2^a / 3^b, then the algorithm will run in O(a+b).

Java program with 64-bit integers:

package test;

public class TwoThreePower {

    static void printPowers(int n) {
        int exp3 = 0;
        long rangeMin = n;
        long rangeMax = n;
        int exp2 = 0;
        long power2 = 1;
        while(true) {
            if (power2 < rangeMin) {
                power2 = power2 * 2;
                exp2 = exp2 + 1;
            } else if (power2 <= rangeMax) {
                System.out.println(String.format("%d is 2^%d / 3^%d", n, exp2, exp3));
                return;
            } else {
                rangeMin = rangeMin * 3;
                rangeMax = rangeMax * 3 + 2;
                exp3 = exp3 + 1;
            }
        }
    }

    public static void main(String[] args) {
        for (int i=1; i<100; i++) {
            printPowers(i);
        }
    }
}

This already fails at n=40, so I created (less readable) BigInteger version:

package test;

import java.math.BigInteger;

public class BigTwoThreePower {

    public static final BigInteger TWO = BigInteger.valueOf(2);
    public static final BigInteger THREE = BigInteger.valueOf(3);

    static void printPowers(int n) {
        int exp3 = 0;
        BigInteger rangeMin = BigInteger.valueOf(n);
        BigInteger rangeMax = rangeMin;
        int exp2 = 0;
        BigInteger power2 = BigInteger.ONE;
        while(true) {
            if (power2.compareTo(rangeMin) < 0) {
                power2 = power2.multiply(TWO);
                exp2 = exp2 + 1;
            } else if (power2.compareTo(rangeMax) <= 0) {
                System.out.println(String.format("%d is 2^%d / 3^%d", n, exp2, exp3));
                return;
            } else {
                rangeMin = rangeMin.multiply(THREE);
                rangeMax = rangeMax.multiply(THREE).add(TWO);
                exp3 = exp3 + 1;
            }
        }
    }

    public static void main(String[] args) {
        for (int i=1; i<100; i++) {
            printPowers(i);
        }
    }
}

And here are the results for N=1 to 99:

1 is 2^0 / 3^0
2 is 2^1 / 3^0
3 is 2^5 / 3^2
4 is 2^2 / 3^0
5 is 2^4 / 3^1
6 is 2^9 / 3^4
7 is 2^6 / 3^2
8 is 2^3 / 3^0
9 is 2^8 / 3^3
10 is 2^5 / 3^1
11 is 2^13 / 3^6
12 is 2^10 / 3^4
13 is 2^18 / 3^9
14 is 2^7 / 3^2
15 is 2^23 / 3^12
16 is 2^4 / 3^0
17 is 2^20 / 3^10
18 is 2^9 / 3^3
19 is 2^17 / 3^8
20 is 2^44 / 3^25
21 is 2^6 / 3^1
22 is 2^14 / 3^6
23 is 2^22 / 3^11
24 is 2^30 / 3^16
25 is 2^11 / 3^4
26 is 2^19 / 3^9
27 is 2^46 / 3^26
28 is 2^8 / 3^2
29 is 2^16 / 3^7
30 is 2^62 / 3^36
31 is 2^24 / 3^12
32 is 2^5 / 3^0
33 is 2^13 / 3^5
34 is 2^59 / 3^34
35 is 2^21 / 3^10
36 is 2^48 / 3^27
37 is 2^10 / 3^3
38 is 2^56 / 3^32
39 is 2^18 / 3^8
40 is 2^64 / 3^37
41 is 2^45 / 3^25
42 is 2^7 / 3^1
43 is 2^53 / 3^30
44 is 2^15 / 3^6
45 is 2^80 / 3^47
46 is 2^42 / 3^23
47 is 2^23 / 3^11
48 is 2^69 / 3^40
49 is 2^31 / 3^16
50 is 2^12 / 3^4
51 is 2^58 / 3^33
52 is 2^39 / 3^21
53 is 2^20 / 3^9
54 is 2^66 / 3^38
55 is 2^47 / 3^26
56 is 2^9 / 3^2
57 is 2^74 / 3^43
58 is 2^55 / 3^31
59 is 2^17 / 3^7
60 is 2^82 / 3^48
61 is 2^63 / 3^36
62 is 2^44 / 3^24
63 is 2^25 / 3^12
64 is 2^6 / 3^0
65 is 2^52 / 3^29
66 is 2^33 / 3^17
67 is 2^14 / 3^5
68 is 2^79 / 3^46
69 is 2^60 / 3^34
70 is 2^41 / 3^22
71 is 2^22 / 3^10
72 is 2^68 / 3^39
73 is 2^49 / 3^27
74 is 2^30 / 3^15
75 is 2^11 / 3^3
76 is 2^76 / 3^44
77 is 2^57 / 3^32
78 is 2^38 / 3^20
79 is 2^19 / 3^8
80 is 2^84 / 3^49
81 is 2^65 / 3^37
82 is 2^130 / 3^78
83 is 2^46 / 3^25
84 is 2^27 / 3^13
85 is 2^8 / 3^1
86 is 2^73 / 3^42
87 is 2^54 / 3^30
88 is 2^35 / 3^18
89 is 2^16 / 3^6
90 is 2^81 / 3^47
91 is 2^146 / 3^88
92 is 2^62 / 3^35
93 is 2^43 / 3^23
94 is 2^24 / 3^11
95 is 2^89 / 3^52
96 is 2^154 / 3^93
97 is 2^70 / 3^40
98 is 2^51 / 3^28
99 is 2^32 / 3^16