秘密のルールを見つけ出せ！

これはcodecheckのチャレンジです。
初めての方はまずチュートリアルをご覧ください。

ある秘密の規則にそった数列を生成する関数が存在します。

この関数に1を渡すと、結果として「1」が返されます。 この関数に2を渡すと、結果として「11」が返されます。 以下、7までの入力に対する結果は以下の通りです。

1 -> 1
2 -> 11
3 -> 21
4 -> 1211
5 -> 111221
6 -> 312211
7 -> 13112221

ザ・ミッション

この数列の生成ルールを見つけ、その値を返す関数を実装してください。

実装の詳細

CLI

入力値を引数に取り、結果を標準出力に出力するCLIアプリケーションとして解答を実装してください。 CLIの実装方法については[指定言語].mdを参照ください。

入力ルール

$ ./secret_rule n

• このCLIアプリケーションは整数の引数 n が1つのみ渡されます。
• 不正な引数が渡されることはありません。
• 1 <= n <= 20

処理ルール

• 数列の生成ルールに従い、標準出力に整数を出力してください。
• 生成ルールについてはウェブ上で検索することを可とします。
• 外部ライブラリの利用は不可とします。

サンプル

$ ./secret_rule 2
11

なお、期待する入出力は test/ ディレクトリにいくつか定義されています。
実装する際の参考にしてください。

追加課題

追加課題として、入力値「10000」に対する結果の最初の500桁をlongOutput.txtの一行目に記述しなさい。 この課題は、素直な実装では膨大な桁数に膨れ上がり計算できないでしょう。 最適化する方法があるか考えてみてください。

※ この秘密のテストはチャレンジ提出時にのみ実行されWebEditor上では確認できません。

Answer.md

answer.mdを用意してあるので、その中に

• どのように実装したか、工夫した点は何か
• 発生した問題、難しかった箇所
• それをどのようにして対処したのか

等を書いてください。