一進法のソースを表示

{{出典の明記|date=2014年2月5日 (水) 00:07 (UTC)}}
'''一進法'''（いっしんほう）とは[[数]]の表現方法の1つで、[[1]]を底とする非標準的な記数法である。その名に反し、[[位取り記数法|''N'' 進法]]で ''N'' を 1 にしたものとは異なるが、後述のように両者に関係はある。単進法と呼ばれることもある
<ref>{{Cite journal|和書|author=和田健之介|date=1994-05|title=システムの進化と創造性|journal=現代思想|volume=22|number=6|publisher=青土社|pages=192-207|id={{NDLJP|6055574}}|ref=harv}}</ref>。

この記法で書かれた数値を一進数（または単進数）と呼ぶ。

== 概要 ==
一進法とは、任意の[[記号]]を ''N'' 回繰り返すことで数 ''N'' を表すもので、[[自然数]]を表現するもっとも単純な記数法である。例えば記号として 1 を利用した場合、十進法の 1, 2, 3, 4, 5, 6 は一進法で以下のようになる：
:1, 11, 111, 1111, 11111, 111111
一進法には '''[[0]]''' を表す記号がなく、0 は[[空文字列]]（何も書かない）によって表す。しかし、何も書かないと読者に判らなくなるので、便宜上はεで空文字列を表すこともある。
<!--
本論からずれている＆一進法では空文字列として0を表せるので例として不適切なのでコメントアウト
[[ローマ数字]]のような高度な数の数え方でも0にあたる文字はなく、代わりに[[ラテン語]]で「何もない」を意味する ''{{lang|la|nullae}}'' と書く。

言わずもがななのでコメントアウト
[[加算]]や[[減算]]は一進法では特に簡単であり、ほぼ記号列の連結だけで済む。[[乗算]]や[[除算]]はそれより面倒な手順となる。
-->

== ''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>
を表すことになり、一進数表記と一致する。これが「一進数」と呼ばれる由縁である。

== 具体的な用例 ==
例えば、記号として縦棒である '''|'''（タリーマーク、''{{lang|en|tally mark}}''）を使うと、[[6]]は '''||||||''' 、[[9]]は '''|||||||||''' 、十進法の[[12]]は '''||||||||||||''' として表現される。この記数法を[[画線法]]という。[[指]]を折って数える方法も一進法であるといえる。一進法は、[[スポーツ]]の試合で得点を数えるなど進行中の結果を集計するのに便利である。これは書き足していくだけの漸増的な記数法で、中間結果を消したり、捨てたりする必要がないからである。[[漢数字]]の 一・二・三 や、[[ローマ数字]]の I・II・III なども一進法的な由来であろうことが想像される。

[[File:Tally marks.png|right|150px|thumb|5つ区切りのタリーマーク]]
'''|''' を使うのは、[[欧米]]では最も一般的な方法である。[[単位]]となる[[マーク]]は、読みやすいように[[奇数]]（[[3|三]]つか[[5|五]]つ）ごとのグループに統められることが多い。[[偶数]]では、[[4|四]]つか[[6|六]]つごとのグループに統められる場合もある。これは、[[十進法]]など様々なN進法で「100,000,000」として表現される大きな数を読みやすくするために、[[スペース]]や区切り記号（[[コンマ]]など）を使うのに似ている。グループの中の最初、第三（三つ区切りの場合）、第五（五つ区切りの場合）のマークは、容易に識別できるように、他のマークに対して斜めに書かれたり、横線を入れたりすることがある。

5で区切る場合には、5を表すマークは ''{{lang|en|five-bar gate}}'' とも呼ばれ、「縦線4つに横線1つを入れる」方法で表現する。3で区切る場合には、3は「[[H]]」の横線を両脇に出張らせる方法で表現する。偶数も同じで、4で区切る場合には「♯」や「口」、6で区切る場合には「縦線4つに横線2つを入れる」や「⊠」(口の中に×) などの方法で表現する。

奇数（三つか五つ）区切りの場合には、グループを二つ統めて円で囲んだり（[[3]]×[[2]]＝[[6]]、5×2＝[[10]]）、四つ統めて円で囲んだり（3×[[4]]＝[[12]]、5×[[4]]＝[[20]]）することもある。同様に、四つ区切りの場合には、三つか五つで統めて円で囲んだり（4×3＝12、4×5＝20）、六つ区切りの場合には六の冪数で統めて円で囲んだりする（6{{sup|2}}＝[[36]]、6{{sup|3}}＝[[216]]）こともある。

[[File:Tally marks 3.svg|right|150px|thumb|正の字]]
[[日本]]や[[中国]]では五画の[[漢字]]である'''[[wikt:正|正]]'''を書いて数える方法があるが、これも5つごとのグループで統める一進法である。

[[File:Tally marks 2.svg|right|150px|thumb|アルゼンチンなどで使われる画線法]]
[[アルゼンチン]]や[[ブラジル]]では、 {{lang|pt|Truco}}{{enlink|Truco|en}}という[[ゲーム]]を遊ぶときなどに一進法が広く用いられる。

「H」が四つに達したら新しい記号を出す（[[十二進法]]）、「正」が四つに達したら新しい記号を出す（[[二十進法]]）といった標準的な[[位取り記数法|N進法]]と比較して、大きな数の[[計算]]には一進法は不便なので使われない。また、固定的な文書で使われることもほとんどない。

== 計算理論などにおける一進法 ==
一進法には、計算理論において[[計算複雑性理論|計算量]]を「人工的に」減らすため、などといった応用がある。例として、自然数の[[素因数分解]]問題は入力が二進法で与えられる場合には、入力長 ''n'' の[[多項式時間]]では実行不可能だと考えられている（素因数分解仮定）。しかし、入力が一進法で与えられるならば、入力長の多項式時間で実行するのは容易である（[[エラトステネスの篩]]で十分）。二進法での入力長 ''n'' は入力の数 ''N'' の[[対数]] log ''N'' に比例するが、一進法での入力長は入力の数 ''N'' それ自身に比例するからである。

他にも[[コンピュータ科学]]などには多くの応用がある。たとえば、[[チューリングマシン]]の初歩的な例題などでは、テープ上に数字を並べてそれを[[位取り記数法]]で扱うのは相当に煩雑であるが、一進法であれば「右に進んでいって1があれば0に書き換えて、今度は左に進む」といったような手順で簡単に扱うことができる。

== 出典 ==
{{Reflist}}

== 関連項目 ==
{{Commonscat|Unary numeral}}
* [[画線法]]
* [[ペアノの公理]]
* [[モスクワ数学パピルス]]

== 外部リンク ==
* {{OEIS|id=A000042}}

{{Num-stub}}
{{Math-stub}}
{{DEFAULTSORT:いつしんほう}}
[[Category:数の表現]]
[[Category:数学に関する記事]]
[[Category:1]]
[[Category:位取り記数法]]