一進法
一進法（いっしんほう）とは数の表現方法の1つで、1を底とする非標準的な記数法である。その名に反し、N 進法で N を 1 にしたものとは異なるが、後述のように両者に関係はある。
Contents
概要
一進法とは、任意の記号を N 回繰り返すことで数 N を表すもので、自然数を表現するもっとも単純な記数法である。例えば記号として 1 を利用した場合、十進法の 1, 2, 3, 4, 5 は一進法で以下のようになる：
- 1, 11, 111, 1111, 11111.
一進法には 0 を表す記号がなく、0 は空文字列（すなわち、なにも書かない）によって表す。しかし、なにも書かないと読者にわからなくなってしまうので、便宜上はεで空文字列を表すこともある。
N 進数との関係
N 進数表記
- [math]a_{n-1}\ldots a_0[/math]
は自然数
- [math]\sum_{i=0}^{n-1}a_iN^i[/math]
を表している。ここで、形式的に
- [math]N=1,\; a_{n-1}=\cdots=a_0=1[/math]
とすると、表記
- [math]1\cdots 1[/math] （1 を N 個並べたもの）
が
- [math]\sum_{i=0}^{n-1}1\cdot 1^i=n[/math]
を表すことになり、一進数表記と一致する。これが「一進数」と呼ばれる由縁である。
日常生活における具体的
例えば記号として |（タリーマーク、tally mark）を使うと、6は |||||| として表される。このやり方を画線法という。また、指を折って数を数えるやり方は一進法であるといえる。一進法はスポーツの試合で得点を数えるなど進行中の結果を集計するのに便利である。これは書き足していくだけのインクリメンタルな記数法である、つまり中間結果を消したり、捨てたりする必要がないからである。漢数字の 一・二・三 や、ローマ数字の I・II・III なども一進法的な由来であろうことが想像される。
| を使うのは欧米ではもっとも一般的な方法である。単位となるマークは読みやすいように5つごとのグループにまとめられることが多い。これは、十進法で100,000,000のような大きな数を読みやすくするために（スペースやコンマなどの）区切り記号を使うのに似ている。グループの中の1番目または5番目のマークは簡単に識別できるよう、他のマークに対して斜めに書かれることがある。5を表すマークは five-bar gate とも呼ばれる。グループを2つまとめて円で囲む（10を表す）こともある。
日本や中国では五画の漢字である正を書いて数を数える方法があるが、これも5つごとのグループでまとめる一進法である。
アルゼンチンやブラジルでは、 Truco (en) というゲームを遊ぶときなどに一進法が広く用いられる。
標準的な位取り記数法と比較して、大きな数の計算には一進法は不便なので使われない。また、固定的な文書で使われることもほとんどない。
計算理論などにおける一進法
一進法には、計算理論において計算量を「人工的に」減らすため、などといった応用がある。例として、自然数の素因数分解問題は入力が二進法で与えられる場合には、入力長 n の多項式時間では実行不可能だと考えられている（素因数分解仮定）。しかし、入力が一進法で与えられるならば、入力長の多項式時間で実行するのは容易である（エラトステネスの篩で十分）。二進法での入力長 n は入力の数 N の対数 log N に比例するが、一進法での入力長は入力の数 N それ自身に比例するからである。
他にもコンピュータ科学などには多くの応用がある。たとえば、チューリングマシンの初歩的な例題などでは、テープ上に数字を並べてそれを位取り記数法で扱うのは相当に煩雑であるが、一進法であれば「右に進んでいって1があれば0に書き換えて、今度は左に進む」といったような手順で簡単に扱うことができる。
関連項目
以下、英語版の記事