Convert 1 into any positive integer using only the operations *3 and /2

Question

Any positive integer can be obtained by starting with 1 and applying a sequence of operations, each of which is either "multiply by 3" or "divide by 2, discarding any remainder".

Examples (writing f for *3 and g for /2):

4 = 1 *3 *3 /2 = 1 ffg
6 = 1 ffggf = 1 fffgg
21 = 1 fffgfgfgggf

Write a program with the following behavior:

Input: any positive integer, via stdin or hard-coded. (If hard-coded, the input numeral will be excluded from the program length.)
Output: a string of f's and g's such that <input> = 1 <string> (as in the examples). Such a string in reverse order is also acceptable. NB: The output contains only f's and g's, or is empty.

The winner is the entry with the fewest bytes of program-plus-output when 41 is the input.

Answer 1

GolfScript, score 64 (43-2+23)

0{)1.$2base:s{{3*}{2/}if}/41=!}do;s{103^}%+

(41 is hardcoded, therefore -2 characters for the score). The output is

fffgffggffggffgggffgggg

which is 23 characters (without newline). By construction the code guarantees that it always returns (one of) the shortest representations.

Answer 2

We're getting dirty, friends!

JAVA 210 207 199 characters

public class C{public static void main(String[] a){int i=41;String s="";while(i>1){if(i%3<1){s+="f";i/=3;}else if(i%3<2){s+="g";i+=i+1;}else{s+="g";i+=i+(Math.random()+0.5);}}System.out.println(s);}}

non-golfed:

public class C {

    public static void main(String[] a) {

        int i = 41;
        String s = "";
        while (i > 1) {
            if (i % 3 == 0) {
                s += "f";
                i /= 3;
            } else {
                if (i % 3 == 1) {
                    s += "g";
                    i += i + 1;
                } else {
                    s += "g";
                    i += i + (Math.random() + 0.5);
                }
            }
        }
        System.out.println(s);
    }
}

output : depending on the faith of the old gods, the shortest i had was 30. Note that the output must be read from the right.

234

1 ggfgfgfgfggfggfgffgfggggfgffgfggfgfggggfgffgfggfgfggfgfggfgfgggggfffgfggfgfggfgfgggffgggggfffgfggggfgffgfggfgfggfgfggfgfggfgfggfgfggfgfggggfgffgfggfgfggfgfggfgfggfgfggfgfggggggggggggfgfgfggggfgfgfggfffgfgfggffgfgfggfgfggggffgfgfffff

108

1 gggffgfgfggggggfggggfgffggggfgfgfgfgfgffgggfgggggfggfffggfgfffffgggffggfgfgggffggfgfgggffggggggfgfgffgfgfff

edit 45

1 ggfgfgfgfgggfggfffgfggfgfgggggggffgffgfgfff

points : 318 199+30 = 229

edit1 (2*i+1)%3==0 --> (2*i) % 3 ==1

Nota Bene if you use Java 6 and not Java 7 while golfing, you can use

public class NoMain {
    static {
        //some code
        System.exit(1);
    }
}

39 characters structure instead of a standard structure which is 53 characters long.

Answer 3

Python, score 124 (90-2+36)

x=41;m=f=g=0
while(3**f!=x)*(m!=x):
 f+=1;m=3**f;g=0
 while m>x:m/=2;g+=1
print'f'*f+'g'*g

90 chars of code (newlines as 1 each) - 2 for hard-coded input numeral + 36 chars of output

Output:

ffffffffffffffffgggggggggggggggggggg

Answer 4

Python, score 121 (87 - 2 + 36)

t=bin(41)
l,n,f=len(t),1,0
while bin(n)[:l]!=t:f+=1;n*=3
print(len(bin(n))-l)*'g'+f*'f'

Answer 5

Perl, score 89 (63 - 2 + 28)

$_=41;$_=${$g=$_%3||$_==21?g:f}?$_*2+$_%3%2:$_/3while$_>print$g

Conjecture: If the naive approach described in my original solution below ever reaches a cycle, that cycle will be [21, 7, 15, 5, 10, 21, ...]. As there are no counter-examples for 1 ≤ n ≤ 10⁶, this seems likely to be true. To prove this, it would suffice to show that this is the only cycle which can exist, which I may or may not do at a later point in time.

The above solution avoids the cycle immediately, instead of guessing (wrongly), and avoiding it the second time through.

Output (28 bytes):

ggfgfgfgfggfggfgfgfggfgfgfff

---

Perl, score 100 (69 - 2 + 33)

$_=41;1while$_>print$s{$_=$$g?$_*2+$_%3%2:$_/3}=$g=$_%3||$s{$_/3}?g:f

Using a guess-and-check approach. The string is constructed using inverse operations (converting the value to 1, instead of the other way around), and the string becomes mirrored accordingly, which is allowed by the problem specification.

Whenever a non-multiple of three is encountered, it will be multiplied by two, adding one if the result would then be a multiple of three. When a multiple of three is encountered, it will be divided by three... unless this value has previously been encountered, indicating a cycle, hence guess-and-check.

Output (33 bytes):

ggfgfgfgfggfggfgffgfgggfggfgfgfff

Answer 6

J, score 103 (82-2+23)

*Note: I named my verbs f and g, not to be confused with output strings f and g.

Hard-coded:

f=:3 :'s=.1 for_a.y do.s=.((<.&-:)`(*&3)@.a)s end.'
'gf'{~#:(>:^:(41&~:@f@#:)^:_)1

General functions:

f=:3 :'s=.1 for_a.y do.s=.((<.&-:)`(*&3)@.a)s end.'
g=:3 :'''gf''{~#:(>:^:(y&~:@f@#:)^:_)1'

Did away with operating on blocks of binary numbers, which was the most important change as far as compacting g. Renamed variables and removed some whitespace for the heck of it, but everything's still functionally the same. (Usage: g 41)

J, score 197 (174+23)

f =: 3 : 0
acc =. 1
for_a. y do. acc =. ((*&3)`(<.&-:)@.a) acc end.
)

g =: 3 : 0
f2 =: f"1 f.
l =. 0$0
i =. 1
while. 0=$(l=.(#~(y&=@:f2))#:i.2^i) do. i=.>:i end.
'fg'{~{.l
)

Output: ffffffffggggggggfgffggg

f converts a list of booleans into number, using 0s as *3 and 1s as /2 (and floor). #:i.2^i creates a rank 2 array containing all the rank 1 boolean arrays of length i.