Ruby
どう書く
yhpg

# 問題名間違えてた…

2進変換さえできれば、あとはやるだけな気がします.

…と思ったけど、他の方の答案見ていて、メインループ内にwhileを書くのはまずいと思いましたので、直しました。記念でPythonも。

#!/usr/bin/env ruby
#http://nabetani.sakura.ne.jp/hena/orde16nontri/
#http://qiita.com/Nabetani/items/3525da55601bdf55316e

W=3
def q(n)
    s=''.dup
    n.times{|i|s<<((i%W==W-1)?'1':'0')}
    s
end

while gets
    s='0'+($_.to_i+1).to_s(2)
    if idx=s.index('0'+'1'*W)
        s=s[0...idx]+'1'+q(s.size-(idx+1))
    end
    if idx=s.index('0'*W)
        s=s[0..idx+1]+'1'+q(s.size-(idx+3))
    end
    p s.to_i(2)
    STDOUT.flush
end
#!/usr/bin/env python
#http://nabetani.sakura.ne.jp/hena/orde16nontri/
#http://qiita.com/Nabetani/items/3525da55601bdf55316e

import sys
if sys.version_info[0]>=3: raw_input=input

W=3
q=lambda n:''.join('1' if i%W==W-1 else '0' for i in range(n))

try:
    while True:
        s='0'+bin(int(raw_input())+1)[2:]
        try:
            idx=s.index('0'+'1'*W)
            s=s[0:idx]+'1'+q(len(s)-(idx+1))
        except ValueError:
            pass
        try:
            idx=s.index('0'*W)
            s=s[0:idx+W-1]+'1'+q(len(s)-(idx+W))
        except ValueError:
            pass
        print(int(s,2))
        sys.stdout.flush()
except EOFError:
    pass

以下は古い答案。

#!/usr/bin/env ruby
#http://nabetani.sakura.ne.jp/hena/orde16nontri/
#http://qiita.com/Nabetani/items/3525da55601bdf55316e

while gets
    s=($_.to_i+1).to_s(2)
    while idx=s.index('111')
        while idx>=0
            break if s[idx]=='0'
            idx-=1
        end
        if idx==-1
            s='1'+'0'*s.size
        else
            s[idx]='1'
            (idx+1...s.size).each{|i|s[i]='0'}
        end
    end
    while idx=s.index('000')
        s[idx+2]='1'
        (idx+3...s.size).each{|i|s[i]='0'}
    end
    p s.to_i(2)
    STDOUT.flush
end