黄金進法のソースを表示

'''黄金進法'''（おうごんしんぽう、golden ratio base, phinary）は、[[黄金比]]（[[φ]] = <math display=inline>\frac{1+\sqrt{5}}{2}</math> &asymp; 1.61803399）を[[底]]とした[[広義の記数法]]である。全ての非負[[実数]]はφを底とした0, 1列によって表され、このうち "11" の連続を除いたものを「標準形」と呼ぶ。"11" を含むφ進表記は、φ<sup>{{mvar|n}}</sup> + φ<sup>{{math|''n''−1}}</sup> = φ<sup>{{math|''n''+1}}</sup> という関係を用いて標準形に書き直すことができる。例えば 11<sub>φ</sub> = 100<sub>φ</sub> である。

黄金進法は[[無理数]]を底とした記数法であるが、全ての非負[[整数]]は一通りの（有限）φ進表現を持つ。また、[[有理数]]は循環小数として表すことができる。これらの表現は[[10進法]]でいうところの 1 = [[0.999...]] のような場合を除いて一意的である。

== 例 ==
{| class="wikitable"
|-
! 10進
! φの累乗の和
! φ進
|-
| 1
| φ<sup>0</sup>
| align=right | {{mono|1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}}
|-
| 2
| φ<sup>1</sup> + φ<sup>−2</sup>
| align=right | {{mono|10.01&nbsp;&nbsp;}}
|-
| 3
| φ<sup>2</sup> + φ<sup>−2</sup>
| align=right | {{mono|100.01&nbsp;&nbsp;}}
|-
| 4
| φ<sup>2</sup> + φ<sup>0</sup> + φ<sup>−2</sup>
| align=right | {{mono|101.01&nbsp;&nbsp;}}
|-
| 5
| φ<sup>3</sup> + φ<sup>−1</sup> + φ<sup>−4</sup>
| align=right | {{mono|1000.1001}}
|-
| 6
| φ<sup>3</sup> + φ<sup>1</sup> + φ<sup>−4</sup>
| align=right | {{mono|1010.0001}}
|-
| 7
| φ<sup>4</sup> + φ<sup>−4</sup>
| align=right | {{mono|10000.0001}}
|-
| 8
| φ<sup>4</sup> + φ<sup>0</sup> + φ<sup>−4</sup>
| align=right | {{mono|10001.0001}}
|-
| 9
| φ<sup>4</sup> + φ<sup>1</sup> + φ<sup>−2</sup> + φ<sup>−4</sup>
| align=right | {{mono|10010.0101}}
|-
| 10
| φ<sup>4</sup> + φ<sup>2</sup> + φ<sup>−2</sup> + φ<sup>−4</sup>
| align=right | {{mono|10100.0101}}
|}

== 黄金進数の標準形 ==
以下、下線はその桁が負であることを意味するものとする。例えば、211.0<u>1</u><sub>φ</sub> は、2φ<sup>2</sup> + φ<sup>1</sup> + 1 − φ<sup>−2</sup> の意である。この表現は、"2" や "<u>1</u>"（"0"、"1"以外の数）、"11" を含むため、標準形ではない。後述する四則の計算の際に、このような表現を標準形に直す必要が出てくる。

「標準化」には、以下の置換を用いる。
* 011<sub>φ</sub> = 100<sub>φ</sub> （φ + 1 = φ<sup>2</sup> の意）
* 0200<sub>φ</sub> = 1001<sub>φ</sub> （2φ<sup>2</sup> = φ<sup>3</sup> + 1 の意）
* 0<u>1</u>0<sub>φ</sub> = <u>1</u>01<sub>φ</sub> （−φ = −φ<sup>2</sup> + 1 の意）
置換はどの順序で行っても結果は同じである。以下に示す例では、右が適用した置換で、左がその結果である。

   211.0<u>1</u><sub>φ</sub>
   300.0<u>1</u><sub>φ</sub>     011<sub>φ</sub> → 100<sub>φ</sub>
  1101.0<u>1</u><sub>φ</sub>     0200<sub>φ</sub> → 1001<sub>φ</sub>
 10001.0<u>1</u><sub>φ</sub>     011<sub>φ</sub> → 100<sub>φ</sub>（再）
 10001.<u>1</u>01<sub>φ</sub>    0<u>1</u>0<sub>φ</sub> → <u>1</u>01<sub>φ</sub>
 10000.011<sub>φ</sub>    0<u>1</u>0<sub>φ</sub> → <u>1</u>01<sub>φ</sub>（再）
 10000.1<sub>φ</sub>      011<sub>φ</sub> → 100<sub>φ</sub>（再）

この方法で、任意の[[正の数と負の数|正]]の非標準形φ進数は一意に標準化できる。上記のルールでできる限りの置換を行った結果、先頭の桁が <u>1</u> であれば、その表現は負の数である。[[プラス記号とマイナス記号|マイナスの符号]]を付して、1 と <u>1</u> を互いに入れ替えることにより、符号付きの標準形を得ることができる。例えば、
:<u>1</u>01<sub>φ</sub> = −10<u>1</u><sub>φ</sub> = −1<u>1</u>0.1<sub>φ</sub> = −1.1<sub>φ</sub> = −10<sub>φ</sub>
などと計算される。

== 整数の黄金進数表現 ==
通常の意味での整数を、黄金進数で表すと有限小数となる。例として、整数 5 をφ進法で表す手続きを見よう。

5 以下で最も大きなφの冪は φ<sup>3</sup> = 1 + 2φ &asymp; 4.236 である。5 との差を取ると、5 - (1 + 2φ) = 4 - 2φ &asymp; 0.763 である。これ以下で最も大きなφの冪はφ<sup>－1</sup> = -1 + 1φ &asymp; 0.618 である。差を取ると、4 - 2φ - (-1 + 1φ) = 5 - 3φ &asymp; 0.145 である。これ以下で最も大きなφの冪は φ<sup>－4</sup> = 5 - 3φ &asymp; 0.145 である。差を取ると 0 である。したがって、
:5 = φ<sup>3</sup> + φ<sup>－1</sup> + φ<sup>－4</sup>
であり、φ進法で表すと 1000.1001<sub>φ</sub> である。

ここで暗に用いている事実は、φの冪は全てある整数 ''a'', ''b'' を用いて ''a'' + ''b'' φの形で書ける、ということである。これを確かめるには、φ<sup>2</sup> = φ + 1 と φ<sup>－1</sup> = -1 + φ に注意すればよい。そして、このような形の数同士の大小を調べることは易しい。実際、''a'' + ''b''φ &gt; ''c'' + ''d''φ は 2(''a'' － ''c'') － (''d'' － ''b'') &gt; (''d'' － ''b'') × √5 と同値であり、この大小関係は一方のみが正であれば自明であるし、そうでなければ両辺を平方することにより確かめられる。

黄金進法により有限小数となるのは、通常の意味での整数のみならず、[[環 (数学)|環]]
{{Indent|<math>\mathbb{Z}[\varphi]:= \{ a+b\varphi \mid a,b \in \mathbb{Z} \}</math>}}
の[[元 (数学)|元]]であり、またそれに限ることが容易に分かる。

=== 非一意性 ===
[[N進数]]のときと同じように、黄金進数にも複数の表現がある。10進法における [[0.999...]]=1 と同様に、φ進法では 0.1010101…<sub>φ</sub> が 1 と等しいことが、以下の各方法で確かめられる。
*非標準形に変換する: 1  = 0.11<sub>φ</sub> = 0.1011<sub>φ</sub> = 0.101011<sub>φ</sub> = … = 0.10101010…<sub>φ</sub>
*[[等比級数]]: 1.0101010…<sub>φ</sub> は以下に等しい
*:<math>\sum_{k=0}^\infty \varphi^{-2k}=\frac{1}{1-\varphi^{-2}} = \varphi</math>
*"シフト"して差分を取る: φ<sup>2</sup> x - x = 10.101010…<sub>φ</sub> - 0.101010…<sub>φ</sub> = 10<sub>φ</sub> = φ このとき x = φ/(φ<sup>2</sup>&nbsp;－&nbsp;1) = 1
この非一意性は記数法の特徴であり、1.0000 も 0.101010… も標準形である。一般に、φ進数における最後の 1 を 01 の繰り返しに置換することによって、別の標準形を作ることができる。

== 有理数の黄金進数表現 ==
非負の[[有理数]]は黄金進数表現として循環小数で表すことができる。実は、循環小数で表すことができるのは、通常の意味での有理数のみならず、'''Z'''[φ] の[[商体]]
{{Indent|<math>\mathbb{Q}(\varphi)=\mathbb{Q}(\sqrt{5}):= \{ a+b\sqrt{5} \mid a,b \in \mathbb{Q} \}</math>}}
の元であり、またそれに限る。いくつか例を挙げる。
*1/2 = 0.010 010 010 010…<sub>φ</sub>
*1/3 = 0.00101000 00101000 00101000…<sub>φ</sub> 
*√5 = 10.1<sub>φ</sub>
*2+(1/13)√5 = 10.010 1000100010101000100010000000 1000100010101000100010000000 1000100010101000100010000000…<sub>φ</sub>
'''Q'''(φ) の元の黄金進数表現が有限小数となることの証明は、通常の十進法の場合と同様である。実際、割り算を[[筆算]]で行った場合の余りの可能性は有限個しかないため、繰り返しのパターンが現れる。例えば、1/2 = 1/10.01<sub>φ</sub> = 100<sub>φ</sub>/1001<sub>φ</sub> の筆算は次のようになる。

               0.0 1 0 0 1 ...
         ------------------------
 1 0 0 1 ) 1 0 0.0 0 0 0 0 0 0 0
             1 0 0 1
             -------
                 1 0 0 0 0
                   1 0 0 1
                   -------
                       ...

ここに、引き算が少々難しいが、10000<sub>φ</sub> = 1100<sub>φ</sub> = 1011<sub>φ</sub> より 10000<sub>φ</sub> - 1001<sub>φ</sub> = 10<sub>φ</sub> であることを用いている。

逆に、黄金進数表現で循環小数であるものが '''Q'''(φ) の元に限ることを見るには、循環小数の意味するところが、公比がφの冪である[[等比級数]]であることに注意すればよい。

== 無理数の黄金進数表現 ==
通常の意味での無理数であっても、'''Q'''(φ) の元であれば黄金進数表現において有限小数となる。
* [[黄金比|φ]] = (1+√5)/2 = 10<sub>φ</sub>
* [[5の平方根|√5]] = 10.1<sub>φ</sub>
一方、'''Q'''[φ] の元でない実数は循環しない無限小数となる。
* [[Pi|π]] = 100.01001 01010 01000 10101 01000 00101…<sub>φ</sub>（{{OEIS|A102243}}）
* ''[[ネイピア数|e]]'' = 100.00001 00001 00100 00000 01000…<sub>φ</sub>（{{OEIS2C|A105165}}）
* [[2の平方根|√2]] = 1.01000 00101 00101 00100 00000 10100 00000 00101…<sub>φ</sub>

== 四則計算 ==
10進法の通常の四則と同様にして、φ進法においても四則が行える。加法、減法、乗法については、以下のように大きく2つの方法がある。

=== 計算して標準化 ===
2つのφ進数の[[加法]]として、各々の桁を（繰り上がり等を気にせず）そのまま足してから標準形に直す方法が考えられる。[[減法]]も同様に（上の桁から借りてくることを気にせず、必要なら <u>1</u> の記号を用いることにより）そのまま引いてから標準化すればよい。[[乗法]]も同様である。以下に計算の例を挙げる。
* 2 + 3 = 10.01<sub>φ</sub> + 100.01<sub>φ</sub> = 110.02<sub>φ</sub> = 110.1001<sub>φ</sub> = 1000.1001<sub>φ</sub>
* 7 - 2 = 10000.0001<sub>φ</sub> - 10.01<sub>φ</sub> = 100<u>1</u>0.0<u>1</u>01<sub>φ</sub> = 11<u>1</u>0.0<u>1</u>01<sub>φ</sub> = 1001.0<u>1</u>01<sub>φ</sub> = 1000.1001<sub>φ</sub>
* 2 × 3 =  10.01<sub>φ</sub> × 100.01<sub>φ</sub> = 1000.1<sub>φ</sub> + 1.0001<sub>φ</sub> = 1001.1001<sub>φ</sub> = 1010.0001<sub>φ</sub>

=== 0と1以外の数字を避ける ===
さらに「自然な」方法として、1 + 1 の加法または 0 - 1 の減法を避ける方法がある。これはφ進数を非標準形に置換することによって実現できる。例えば、次のようにする。
* 2 + 3 = 10.01<sub>φ</sub> + 100.01<sub>φ</sub> =  10.01<sub>φ</sub> + 100.0011<sub>φ</sub> = 110.0111<sub>φ</sub> = 1000.1001<sub>φ</sub>
* 7 - 2 = 10000.0001<sub>φ</sub> - 10.01<sub>φ</sub> = 1100.0001<sub>φ</sub> - 10.01<sub>φ</sub> = 1011.0001<sub>φ</sub> - 10.01<sub>φ</sub> = 1010.1101<sub>φ</sub> - 10.01<sub>φ</sub> = 1000.1001<sub>φ</sub>

=== 除法 ===
すでに見たように、除法は筆算によって行うことができる。商が '''Z'''[φ] の元ならば筆算が有限回で終了して有限小数となり、'''Q'''(φ) の元ならば繰り返しが生じて循環小数を得る。

== フィボナッチ符号との関係 ==
{{仮リンク|フィボナッチ符号|en|Fibonacci coding}}は[[フィボナッチ数]]の重みを持つ0,1列である。φ進法と同じように、標準形は F<sub>''k''+1</sub> = F<sub>''k''</sub> + F<sub>''k''-1</sub>が適用され、"11" を持たない。例えば、30 は
:30 = 1×21 + 0×13 + 1×8 + 0×5 + 0×3 + 0×2 + 1×1 + 0×1 = 10100010<sub>fib</sub>
と表現される。

== 参考文献 ==
* {{cite book|和書
| author = H. ヴァルサー 著
| others = 蟹江幸博 訳
| title = 黄金分割
| year = 2002
| month = Sep.
| publisher = 日本評論社
| isbn = 4-535-78347-0
| pages=131-134
}}
*{{citation|last=Bergman|first=George|title=A Number System with an Irrational Base|journal=Mathematics Magazine|volume=31|number=2|pages=98–110|year=1957}}
*{{citation|last=Plojhar|first=Jozef|title=the Good~natured Rabbit~breeder|journal=Manifold|volume=11|year=1971|pages=26–30}}

== 外部リンク ==
* [http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/phigits.html Using Powers of Phi to represent Integers (Base Phi)]
{{貴金属比}}

{{DEFAULTSORT:おうこんしんほう}}

[[Category:位取り記数法]]
[[Category:数の表現]]
[[Category:数学に関する記事]]
[[Category:広義の記数法]]