p進法展開
日常生活で何気なく使っている数、例えば、246 などは、ある約束のもとに記述されてい
る。 246 は、「にーよんろく」とは呼ばず、正しくは、「にひゃくよんじゅうろく」である。もっと
も、国道246号線は、通称「にーよんろく」と呼ばれるが、これはあくまでも通称である。
したがって、同じ数字でも、書かれてある順番によって異なった意味合いをもつ。
整数で、一番右側の数は、一の位、その左は、十の位、またその左は、百の位、・・・ と
言われる。このことを明瞭に表すには、次のように書けばよい。
246(10)=2・102+4・10+6
このとき、「246」のような記数法を、位取り記数法、そして、その数を、右辺のように記
す方法を 十進法展開 というようだ。
(「じっしんほうてんかい」と読む!恥ずかしながら今まで「じゅっしんほうてんかい」とずっと読んでまし
た ... f(^^;) )
この位取り記数法は、インドでの「零(0)の発見」がなかったら、なかった記数法だと思う。
もしかしたら、今でも、T、V、X、L、C、D、M といったローマ数字を使っていたかもしれ
ない。(これは、非常に辛い記数法である。詳しくは、こちらを参照)
十進法の位取り記数法では、10になると位が1つ繰り上がるという性質をもつ。これが、
位が異なるごとに違う記号を用いたローマ数字との決定的な違いである。
十進法展開の考えは、p進法展開に一般化される。但し、p は、2以上の整数とする。
a0pn+a1pn-1+a2pn-2+・・・+an-1p+an (各akは、0≦ak<p なる整数)
で表された数を、p進法展開された数といい、各位の数を並べて、p進法の位取り記数法
が得られる。
a0a1a2・・・an-1an(p)
例 4進法で、123 は、十進法ではいくつか?
123(4)=1・42+2・4+3=16+8+3=27
例 十進法で、123 は、5進法でいくつか?
123(10)=5・24+3=5・(5・4+4)+3=4・52+4・5+3 より、123 を、5進法で表
すと、 443(5) となる。
十進法で表された数を、p進法に変換する場合、上記のように計算することはまずない。
通常次のような筆算で求められる。
上記では、整数の p 進法展開を計算したが、もちろん、小数の p 進法展開もありうる。
a1p-1+a2p-2+・・・+anp-n+・・・ (各akは、0≦ak<p なる整数)
例 4進法で、0.122 は、十進法ではいくつか?
0.122(4)=1・4-1+2・4-2+2・4-3=13/32
例 十進法で、0.122 は、5進法でいくつか?
0.122=a15-1+a25-2+a35-3+a45-4+a55-5+・・・ において、
0.122×5=0.61=a1+a25-1+a35-2+a45-3+a55-4+・・・ より、a1=0
0.61×5=3.05=a2+a35-1+a45-2+a55-3+・・・ より、a2=3
このとき、0.05=a35-1+a45-2+a55-3+・・・ となり、
0.05×5=0.25=a3+a45-1+a55-2+・・・ より、a3=0
0.25×5=1.25=a4+a55-1+・・・ より、a4=1
0.25×5=1.25 (これは上記値と同じで上の計算が以下繰り返される。)
・・・・・・・・・・・・・・・
したがって、 0.122 を、5進法で表すと、0.030111・・・ すなわち
となる。
この例からも分かるように、十進法の世界で有限小数であっても、p進数の世界では、循
環小数となる場合がある。
整数の場合と同様にして、小数の場合は、次のような筆算で求めるのが普通である。
(追記) 平成25年9月21日付け
放送大学文京校舎で、「代数曲線と幾何学」と題して、飯高先生のレクチャーがあるという
ことで参加してきた。飯高先生とは30年ほど前、仙台の東北大学で行われた代数幾何学シ
ンポジウムでお見かけして以来であったが、気さくなお人柄は相変わらずで楽しい時間を共
有することが出来た。講義の合間合間のエピソードがとても面白かった。
例えば、Wikipediaでは、Shafarevichが小平次元を名付けたことになっているが、それは誤
りで、本当は、小平先生から誘われて入った喫茶店で飯高先生が小平次元と命名したいと
申し出て、600円のケーキセットで了解してもらったとか...。飯高先生のお話を伺っている
と、代数幾何学の大御所である、小平邦彦、Shafarevich、Hartshorne、・・・の書籍から受け
る印象とはまた違って、とても人間味あふれる人柄がうかがい知れた。
その中で、雑談ではあったが、「1/5の7進法展開は如何?」ということが話題になった。
私は、頭の中で、上記のように、1/5=0.2を順次7倍して整数部分をつなげて、
0.12541254・・・・
を得たが、飯高先生は次のような別解を紹介された。
1は5で割れないから0がたち、0を補って10(7進数)とする。これは十進法で7で、5で割る
と1がたち2余る。
20(十進法で14)として5で割ると2がたち4余る。
40(十進法で28)として5で割ると5がたち3余る。
30(十進法で21)として5で割ると4がたち1余る。以下、繰り返しとなる。
従って、1/5の7進法展開は、 0.12541254・・・・
さらに、飯高先生は、次のような性質も面白いと紹介された。
1/5の7進法展開の循環節 1254 を2と5の間で2つの数12と54に分け足してみると、
12+54=66
となる。ここで、6は、6=7−1からくる。十進法展開で、1/7の循環節は、142857 であ
るが、これも、 142+857=999 (9=10−1) となり、同じ現象である。
(→ 参考:「循環小数の不思議」)
(コメント) 計算の簡明さから言うと、7を掛けた方が分かりやすいと思うが、飯高先生の方
法も有りかなと思う。
p進法展開は、整数に対して、その各位の数は一意に定まるが、小数の場合は、2通りに
表される場合がある。
たとえば、十進法展開で、有限小数の 0.5 という数は、
0.500000000・・・・・・ または 0.49999999・・・・・・
と2通りに表される。しかし、その値は、ともに等しい。
例 今、ある整数の3進法展開が2通りに表せたものとする。すなわち、
a・32+b・3+c = d・32+e・3+f (但し、a、b、c、d、e、f は0,1,2 の何れかの数)
このとき、c−f =9(d−a)+3(e−b) より、 c−f は3の倍数であるが、
−2<c−f <2 なので、c−f =0 となる。 よって、c=f
同様にして、b−e =3(d−a) より、b=e すなわち、d=a となる。
以上と同様にして、整数のp進法展開の方法は、一意的であることが分かる。
また、p進法の位取り記数法において、最小の n 桁の数は、100・・・0(p)=pn-1
0 が n-1 個
p進法の位取り記数法において、最大の n 桁の数は、qqq・・・q(p)=pn−1
q=p-1 が n 個
したがって、p進法の位取り記数法において、n 桁の数は、
pn-1(p−1) 個
ある。(ただし、0 は、この場合の計算からは除外されている。)
(参考文献:宮原 繁 著 整数 (科学新興社モノグラフ))
(追記) 平成20年9月7日付け
2進法で表された整数を小さい順に並べ、
1 、10 、11 、100 、101 、・・・・・・
としたとき、初めの方から数えて16番目の数は何かと問われれば、
から、直ちに、 10000 であることが分かる。即ち、単に、「16」という十進法の整数を
2進法の整数に直せばよい。
ところが、問題の出し方を変えると、俄然難しく感じられる。
0 、1 、2 の3個の数字のみをいくつか使って横に並べ整数を作る。ただし、先頭か
ら並ぶ「0」は無視して考えるものとする。
このとき、 1、2、・・・・ と並んでいる数列で、数字の「1」が使われているときは、その
整数は飛ばして数えるものとする。最初から数えて16番目の整数は何だろうか?
これは、0 と 2 のみを使って出来る整数を小さい順に並べて、
2 、20 、22 、200 、202 、220 、222 、 ・・・・・
としたとき、最初から数えて16番目の整数を問う問題である。
上記の数列は、0 と 1 のみを使って出来る2進法の整数列
1 、10 、11 、100 、101 、110 、111 、 ・・・・・
に対応し、十進法に直せば、
1 、2 、3 、4 、5 、6 、7 、 ・・・・・
ということである。
16 を2進法に直せば、 10000 であるので、求める整数は、 20000 となる。
最近、こんな話題が、平成20年8月24日、「熱血!平成教育学院」(フジテレビ系)で取
り上げられた。
1、2、・・・・ と並んでいる数列で、数字の「4」、「9」が使われているときは、
その整数は飛ばして数えるものとする。
最初から数えて400番目の整数は何だろうか?
この問題を考えるために、下表のような十進法の数字と8進法の数字の対応を考える。
|
400 を8進法で表せば、620 である。これを上表の対応する数字に置換すると、求める
整数は、720 となる。
(コメント) p 進数の意外というか、真の使い方を知って感動しました。2進法は、十進法の
数字の 2〜9 を「飛ばしたもの!」という発想がとても新鮮です。
(追記) 平成20年12月31日付け
0 と 1 のみを使って出来る2進法の整数列
1 、10 、11 、100 、101 、110 、111 、 ・・・
で、「1」の個数を漫然と眺めていると、数列
1 、1 、2 、1 、2 、2 、3 、1 、2 、2 、3 、2 、3 、3 、4 、1 、 ・・・
には、いろいろ興味ある法則が潜んでいそうである。
たとえば、
1 、1 、2 、1 、2 、2 、3 、1 、2 、2 、3 、2 、3 、3 、4 、1 、 ・・・
のように、「1」から次の「1」までの一区切りを考えると、その数列は、初項から一区切りの
最初の「1」に至る数列の各項に1を加えることによって構成されることが分かる。
すなわち、第 n 項を F(n) と表すと、次の性質が成り立つ。
(1) F(2k-1)=1 (k=1、2、3、・・・)
(2) F(2k-1+m)=F(m)+1 (m は、1≦m≦2k-1−1 を満たす自然数)
また、数列を奇数番目と偶数番目に分けて考えると、
n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | ・・・ |
奇数番 | 1 | 2 | 2 | 3 | 2 | 3 | 3 | 4 | ・・・ | ||||||||
偶数番 | 1 | 1 | 2 | 1 | 2 | 2 | 3 | 1 |
上記の表から、
F(3)=2 、 3=2×1+1 から、 F(1)=1 よって、 F(3)=F(1)+1
F(5)=2 、 5=2×2+1 から、 F(2)=1 よって、 F(5)=F(2)+1
F(7)=3 、 7=2×3+1 から、 F(3)=2 よって、 F(7)=F(3)+1
F(9)=2 、 9=2×4+1 から、 F(4)=1 よって、 F(9)=F(4)+1
・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
F(2)=1 、 2=2×1 から、 F(1)=1 よって、 F(2)=F(1)
F(4)=1 、 4=2×2 から、 F(2)=1 よって、 F(4)=F(2)
F(6)=2 、 6=2×3 から、 F(3)=2 よって、 F(6)=F(3)
F(8)=1 、 8=2×4 から、 F(4)=1 よって、 F(8)=F(4)
・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
上記の試算から、次の性質の成り立つことが推察される。
すなわち、自然数 n に対して、
(1) F(2n+1)=F(n)+1
(2) F(2n)=F(n)
この性質はまた次のようにも書き換えることが出来る。
自然数 n を 2 で割った商を Q 、余りを R (Rは、0 または 1 である!)とすると、
F(1)=1 、 F(n)=F(Q)+R
果たして、この性質は一般的に成立するのだろうか?大いに興味があるところである。
一般的に証明してみよう。
(証明) 自然数 n を2進法展開して、
n=a02p+a12p-1+a22p-2+・・・+ap-12+ap (各akは、0 または 1)
であるとする。
このとき、 F(n)=a0+a1+a2+・・・+ap-1+ap であるので、
2n+1=a02p+1+a12p+a22p-1+・・・+ap-122+ap2+1
の各位の1の個数 F(2n+1) は、
F(2n+1)=a0+a1+a2+・・・+ap-1+ap+1=F(n)+1
と書ける。同様にして、
2n+1=a02p+1+a12p+a22p-1+・・・+ap-122+ap2
の各位の1の個数 F(2n) は、
F(2n)=a0+a1+a2+・・・+ap-1+ap=F(n)
と書ける。 (証終)
逆に、F(1)=1 、F(n)=F(Q)+R で定められる数列 { F(n) }の一般項 F(n) は、
n を2進法展開したときの各位に現れる 1 の個数を表す
という特徴を有する。
実際に、n=a02p+a12p-1+a22p-2+・・・+ap-12+ap (各akは、0 または 1)
において、
F(n)=F(a02p-1+a12p-2+a22p-3+・・・+ap-1)+ap
=F(a02p-2+a12p-3+a22p-4+・・・+ap-2)+ap-1+ap
= ・・・・・・・・・・・・・・・・・・・・・・・・・
=a0+a1+a2+・・・+ap-1+ap
より明らかだろう。
読者のために、2009年新春のお年玉として次の練習問題を残しておこう。
問 題 2009以下の自然数 n に対して、F(n)の最大値を求めよ。
(答えは、もちろん 「10」 である。できたかな?)
(追記) 平成21年5月12日付け
p進法展開を利用した面白い計算を最近知ることができた。
問 題 517 を 19 で割った余りを求めよ。
この問題に対する通常の解法は次のようなものだろう。
mod 19 において、52=25≡6 、54≡36≡−2 、58≡4 、516≡16 より、
517=5・516≡5・16=80≡4
よって、517 を 19 で割った余りは、 4 である。
上記の解法を、2進法展開を利用して整理したものが次の解法である。
(解) 17 の 2 進法展開は、 17=24+1 なので、mod 19 において、
52=25≡6 、522=(52)2≡62≡−2 、523≡(−2)2≡4 、524≡42≡16
と計算しておくことにより、直ちに、517=524×51≡16×5=80≡4
よって、517 を 19 で割った余りは、4 である。 (終)
#もちろん、フェルマーの定理より、518≡1 (mod 19) なので、
518≡20 (mod 19) から、 517≡4 (mod 19)
とした方が計算は速いかな!
以下、工事中