# 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, 2013 at 7:00
• @marinus this is believed to be true ( but not proven yet). looking for some proof. Nov 7, 2013 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, 2013 at 10:04
• On a separate note, must the output be in application order or would composition order also be acceptable? Nov 7, 2013 at 10:05
• @PeterTaylor Either way is OK. Nov 7, 2013 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) Nov 8, 2013 at 1:11 • @Doorknob The challenge states that the "1 " should not be included in the output. Nov 8, 2013 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, 2013 at 10:42 • Yes it is. thanks Nov 7, 2013 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, 2013 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, 2013 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, 2013 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, 2013 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, 2013 at 5:46 • You can further save a bit if you replace all n by3**f. Nov 8, 2013 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, 2013 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, 2013 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, 2013 at 7:02 • You can drop the '1' (again!) Your original interpretation of output description was correct. Enjoy the Python lead, again! :-) Nov 8, 2013 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, 2013 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, 2013 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, 2013 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`.