この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。(このテンプレートの使い方)
出典検索?: "一進法"
一進法(いっしんほう)とは数の表現方法の1つで、1を底とする非標準的な記数法である。その名に反し、N 進法で N を 1 にしたものとは異なるが、後述のように両者に関係はある。 一進法とは、任意の記号を N 回繰り返すことで数 N を表すもので、自然数を表現するもっとも単純な記数法である。例えば記号として 1 を利用した場合、十進法の 1, 2, 3, 4, 5, 6 は一進法で以下のようになる:1, 11, 111, 1111, 11111, 111111 一進法には 0 を表す記号がなく、0 は空文字列(何も書かない)によって表す。しかし、何も書かないと読者に判らなくなるので、便宜上はεで空文字列を表すこともある。 N 進数表記 a n − 1 … a 0 {\displaystyle a_{n-1}\ldots a_{0}} は自然数 ∑ i = 0 n − 1 a i N i {\displaystyle \sum _{i=0}^{n-1}a_{i}N^{i}} を表している。ここで、形式的に N = 1 , a n − 1 = ⋯ = a 0 = 1 {\displaystyle N=1,\;a_{n-1}=\cdots =a_{0}=1} とすると、表記 1 ⋯ 1 {\displaystyle 1\cdots 1} (1 を N 個並べたもの) が ∑ i = 0 n − 1 1 ⋅ 1 i = n {\displaystyle \sum _{i=0}^{n-1}1\cdot 1^{i}=n} を表すことになり、一進数表記と一致する。これが「一進数」と呼ばれる由縁である。 例えば、記号として縦棒である |(タリーマーク、tally mark)を使うと、6は |||||。、9は ||||||||。、十進法の12は |||||||||||。として表現される。この記数法を画線法という。指を折って数える方法も一進法であるといえる。一進法は、スポーツの試合で得点を数えるなど進行中の結果を集計するのに便利である。これは書き足していくだけの漸増的な記数法で、中間結果を消したり、捨てたりする必要がないからである。漢数字の 一・二・三 や、ローマ数字の I・II・III なども一進法的な由来であろうことが想像される。5つ区切りのタリーマーク 。を使うのは、欧米では最も一般的な方法である。単位となるマークは、読みやすいように奇数(三つか五つ)ごとのグループに統められることが多い。偶数では、四つか六つごとのグループに統められる場合もある。これは、十進法など様々なN進法で「100,000,000」として表現される大きな数を読みやすくするために、スペースや区切り記号(コンマなど)を使うのに似ている。グループの中の最初、第三(三つ区切りの場合)、第五(五つ区切りの場合)のマークは、容易に識別できるように、他のマークに対して斜めに書かれたり、横線を入れたりすることがある。 5で区切る場合には、5を表すマークは 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)、六つ区切りの場合には六の冪数で統めて円で囲んだりする(62=36、63=216)こともある。正の字 「H」が四つに達したら新しい記号を出す(十二進法)、「正」が四つに達したら新しい記号を出す(二十進法)といった標準的なN進法と比較して、大きな数の計算には一進法は不便なので使われない。また、固定的な文書で使われることもほとんどない。 一進法には、計算理論において計算量を「人工的に」減らすため、などといった応用がある。例として、自然数の素因数分解問題は入力が二進法で与えられる場合には、入力長 n の多項式時間では実行不可能だと考えられている(素因数分解仮定)。しかし、入力が一進法で与えられるならば、入力長の多項式時間で実行するのは容易である(エラトステネスの篩で十分)。二進法での入力長 n は入力の数 N の対数 log N に比例するが、一進法での入力長は入力の数 N それ自身に比例するからである。 他にもコンピュータ科学などには多くの応用がある。たとえば、チューリングマシンの初歩的な例題などでは、テープ上に数字を並べてそれを位取り記数法で扱うのは相当に煩雑であるが、一進法であれば「右に進んでいって1があれば0に書き換えて、今度は左に進む」といったような手順で簡単に扱うことができる。
概要
N 進数との関係
具体的な用例
計算理論などにおける一進法
関連項目.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:#f9f9f9;display:flow-root}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}ウィキメディア・コモンズには、一進法に関連するカテゴリがあります。
画線法
ペアノの公理
モスクワ数学パピルス
外部リンク
オンライン整数列大辞典の数列 A000042
.mw-parser-output .asbox{position:relative;overflow:hidden}.mw-parser-output .asbox table{background:transparent}.mw-parser-output .asbox p{margin:0}.mw-parser-output .asbox p+p{margin-top:0.25em}.mw-parser-output .asbox{font-size:90%}.mw-parser-output .asbox-note{font-size:90%}.mw-parser-output .asbox .navbar{position:absolute;top:-0.90em;right:1em;display:none}
.mw-parser-output .hlist ul,.mw-parser-output .hlist ol{padding-left:0}.mw-parser-output .hlist li,.mw-parser-output .hlist dd,.mw-parser-output .hlist dt{margin-right:0;display:inline-block;white-space:nowrap}.mw-parser-output .hlist dt:after,.mw-parser-output .hlist dd:after,.mw-parser-output .hlist li:after{white-space:normal}.mw-parser-output .hlist li:after,.mw-parser-output .hlist dd:after{content:" ・\a0 ";font-weight:bold}.mw-parser-output .hlist dt:after{content:": "}.mw-parser-output .hlist-pipe dd:after,.mw-parser-output .hlist-pipe li:after{content:" |\a0 ";font-weight:normal}.mw-parser-output .hlist-hyphen dd:after,.mw-parser-output .hlist-hyphen li:after{content:" -\a0 ";font-weight:normal}.mw-parser-output .hlist-comma dd:after,.mw-parser-output .hlist-comma li:after{content:"、";font-weight:normal}.mw-parser-output .hlist-slash dd:after,.mw-parser-output .hlist-slash li:after{content:" /\a0 ";font-weight:normal}.mw-parser-output .hlist dd:last-child:after,.mw-parser-output .hlist dt:last-child:after,.mw-parser-output .hlist li:last-child:after{content:none}.mw-parser-output .hlist dd dd:first-child:before,.mw-parser-output .hlist dd dt:first-child:before,.mw-parser-output .hlist dd li:first-child:before,.mw-parser-output .hlist dt dd:first-child:before,.mw-parser-output .hlist dt dt:first-child:before,.mw-parser-output .hlist dt li:first-child:before,.mw-parser-output .hlist li dd:first-child:before,.mw-parser-output .hlist li dt:first-child:before,.mw-parser-output .hlist li li:first-child:before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child:after,.mw-parser-output .hlist dd dt:last-child:after,.mw-parser-output .hlist dd li:last-child:after,.mw-parser-output .hlist dt dd:last-child:after,.mw-parser-output .hlist dt dt:last-child:after,.mw-parser-output .hlist dt li:last-child:after,.mw-parser-output .hlist li dd:last-child:after,.mw-parser-output .hlist li dt:last-child:after,.mw-parser-output .hlist li li:last-child:after{content:")\a0 ";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li:before{content:" "counter(listitem)" ";white-space:nowrap}.mw-parser-output .hlist dd ol>li:first-child:before,.mw-parser-output .hlist dt ol>li:first-child:before,.mw-parser-output .hlist li ol>li:first-child:before{content:" ("counter(listitem)" "}.mw-parser-output .navbar{display:inline;font-size:75%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}.mw-parser-output .infobox .navbar{font-size:88%}.mw-parser-output .navbox .navbar{display:block;font-size:88%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}