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

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.

• How do you know this is true? Nov 7 '13 at 7:00
• @marinus this is believed to be true ( but not proven yet). looking for some proof. Nov 7 '13 at 9:54
• @marinus, you can prove that it's possible by descent (or equivalently by strong induction). Case-split on x mod 3: if x=3y construct y and then apply f; if x=3y+1 construct 2y+1 and apply f then g; if x=3y+2 then it gets complicated but essentially is recursive. Nov 7 '13 at 10:04
• On a separate note, must the output be in application order or would composition order also be acceptable? Nov 7 '13 at 10:05
• @PeterTaylor Either way is OK. Nov 7 '13 at 12:54

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. • Quoting user Darren Stone in a suggested edit on this post: "I am unable to leave a comment here so I will leave an edit. This output does not include the first two characters "1 " nor are those reflected in score. Should be an easy fix and still an incredibly short solution. Cheers!" (I rejected, but thought I should carry the message) – Doorknob Nov 8 '13 at 1:11 • @Doorknob The challenge states that the "1 " should not be included in the output. Nov 8 '13 at 6:52 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. • (2*i+1)%3==0 is equivalent to i%3==1 Nov 7 '13 at 10:42 • Yes it is. thanks Nov 7 '13 at 10:43 • if(X){A}else{if(Y){B}else{C}} is longer than if(X){A}else if(Y){B}else{C}. Also you can replace your == conditions with shorter < conditions. Nov 7 '13 at 11:27 • @PeterTaylor true, my solution still is ugly. I don't know if the random part makes the code shorter, but it sures makes the output crappier. Nov 7 '13 at 12:32 • Your f/g strings begin with 'g' (which is supposed to stand for '/2'), so they will convert 1 to 0 instead of to 41. Changing the f's to g's and vice versa, also doesn't seem to give 41. Nov 7 '13 at 13:53 ## 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  • If you do m=f=0 you can make the outer loop while(n!=x)*(m!=x) and remove the breaks. Brings it to 95 chars of code. Nov 8 '13 at 3:49 • @Daniel: You, sir, are a gentleman and a scholar. Thanks! Your submission is still safely 10 chars ahead of me. :) Nov 8 '13 at 5:46 • You can further save a bit if you replace all n by3**f. Nov 8 '13 at 7:56 • For input = 1, your program generates an error ("name 'g' is not defined", due to not entering the outer while-loop). Nov 8 '13 at 15:19 • You could cut out another character by writing print'f'*f+'g'*g, which would give a score of 90-2+36 = 124. Nov 9 '13 at 0:44 ## 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'  • @Darren, I wasn't sure how to interpret the output description, but you're probably right. I added the '1'. Thanks! Nov 8 '13 at 7:02 • You can drop the '1' (again!) Your original interpretation of output description was correct. Enjoy the Python lead, again! :-) Nov 8 '13 at 16:47 • If you combined your 2nd, 3rd, and 4th lines into l,n,f=len(t),1,0, and removed the '1', from the print statement, your score would be 87-2+36 = 121. Nov 9 '13 at 0:37 • Thanks guys - I dropped the 1,. l,n,f=len(t),1,0 gives the same number of characters, right? (For each variable, an = and a newline is replaced with two ,s.) Nov 9 '13 at 4:07 • If each newline is one character (e.g. UNIX-style LF), then the one-line and three-line versions have the same length. If each newline is two characters (e.g. MS Windows-style CR+LF), then the one-line version is two characters shorter than the three-line version. The score of 121 assumes one-character newlines. Nov 9 '13 at 5:21 ## 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 ≤ 106, 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  # 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`.