[logo] Web連載「数学ガールの秘密ノート」
Share

第102回 シーズン11 エピソード2
冒険ビット(後編)

書籍『数学ガールの秘密ノート/ビットとバイナリー』

この記事は『数学ガールの秘密ノート/ビットとバイナリー』として書籍化されています。

無料でWeb立ち読み アマゾンで購入

$ \newcommand{\BIGUL}[1]{\underline{\Large#1}} \newcommand{\SUM}{\displaystyle\sum} \newcommand{\BAR}[1]{\bar{#1}} \newcommand{\TEXT}[1]{\textbf{#1}} \newcommand{\REMTEXT}[1]{\textbf{#1}} $

登場人物紹介

:数学が好きな高校生。

ユーリのいとこの中学生。のことを《お兄ちゃん》と呼ぶ。

$-2$ 進数

$2$ 進数の話をしているとき、 ユーリが言い出した《$-2$ 進数(マイナスにしんすう)》に話が発展して……(第101回参照)。

ユーリ「ぐちゃぐちゃじゃん!」

「いや、少し考えればわかるよ……こうかな」

$-2$ 進数で数を表したらどうなるか

$$ \begin{array}{rrl} \REMTEXT{$-2$進数} & \REMTEXT{$10$進数} & \REMTEXT{メモ} \\ \hline 0 & 0 & \\ 1 & 1 & \\ 110 & 2 & \REMTEXT{$(-2)^2 = 4$に、負数$(-2)^1 = -2$を加える} \\ 111 & 3 & \REMTEXT{$2$に$1$加える} \\ 100 & 4 & \REMTEXT{$(-2)^2 = 4$} \\ 101 & 5 & \REMTEXT{$4$に$1$加える} \\ 11010 & 6 & \REMTEXT{$(-2)^4 = 16$に、負数$(-2)^3 = -8$と$(-2)^1 = -2$を加える} \\ 11011 & 7 & \REMTEXT{$6$に$1$加える} \\ \vdots & \vdots & \vdots \\ \end{array} $$

ユーリ「あれ……お兄ちゃん! パターンが見える! ほらほら、縦読みすれば!」

「ほんとだ! よし、もっと先まで書いてみようか」

そのとき玄関のベルが鳴り、少ししてがやってきた。

「ミルカさんと、もう一人、お友達がいらしたわよ」

「ミルカさん!」

ユーリ「ミルカさま!」

ミルカ「今日はリサを連れてきた」

リサ「……」

リサミルカさんの親戚で、僕たちの後輩にあたる。 無造作に切った赤い髪。 彼女はいつも真っ赤なノートブック・コンピュータを持ち歩いている。

ミルカ「君の家に来たがったのはリサなんだが。来たくてしょうがないと」

「え?」

リサ「誇張」

登場人物紹介(追加)

ミルカさん:数学が好きな高校生。のクラスメート。長い黒髪の《饒舌才媛》。

リサ:自在にプログラミングを行う無口な女子。赤い髪の《コンピュータ少女》。

ミルカ「今日は何を?」

ユーリ「マイナス $2$ 進数です、ミルカさま」

ミルカ「ふうん……楽しそうだな」

リサ「$-2$ 進数?」

「いま、 $-2$ 進数と $10$ 進数の対応表を作ろうとしていたんだ」

リサ「手で?」

「『手で?』ってどういう意味?」

ミルカ「リサは、プログラムでできると言いたいんだよ」

「ああ、そうか。リサちゃんならコンピュータでできるんだ!」

リサ「《ちゃん》は不要」

「リサはプログラム得意だからなあ」

リサ「どこまで?」

ミルカ「切りの良いところまで」

リサ「それなら、 $256$ まで」

リサは軽く咳をしてから、コンピュータのキーボードを叩く。 ほどなくして一覧表を作り出した。

$-2$ 進数と $10$ 進数の対応表

ユーリ「ふへー……リサさんってすごいんですね」

リサ「《さん》も不要」

ユーリ「お兄ちゃん、 $-2$ 進数のパターンが見えるよ。縦読み縦読み!」

「うん。 $(-2)^0$ の位、つまり $1$ の位は縦読みで $0,1,0,1,0,1\ldots$ というパターン」

ユーリ「$(-2)^1$ の位は、 $1,1,0,0,1,1,0,0,\ldots$ だね!  $1,1$ と $0,0$ がかわりばんこ」

「それから $(-2)^2$ の位、つまり $4$ の位は $1,1,1,1$ と $0,0,0,0$ が交互に来る」

ユーリ「下から四桁目の $(-2)^3$ の位は、 $1$ が $8$ 個と、 $0$ が $8$ 個がかわりばんこ」

「$(-2)^4$ の位は、 $1$ が $16$ 個と、 $0$ が $16$ 個……もう一般化できるなあ」

《$-2$ 進数のパターン》

$(-2)^k$ の位を縦読みすると、 《$1$ が $2^k$ 個》と《$0$ が $2^k$ 個》が交互に現れる。

ただし、 $k = 0,1,2,\ldots$ とする。

桁の増加

ミルカ「桁の増加にもパターンが見える」

ユーリ「そーそー! ユーリ気付いてたよ! 桁が増えるときって、 必ず $2$ 桁ずつ増えるの。しかも、増える数字は必ず $11$ で。 そしてしばらく進むと、そこんとこが $10$ に変わる」

$$ \begin{array}{rrl} 0 & 0 & \\ 1 & 1 & \\ 110 & 2 & \REMTEXT{$11$が増えた} \\ 111 & 3 & \\ 100 & 4 & \REMTEXT{$10$に変わった} \\ 101 & 5 & \\ 11010 & 6 & \REMTEXT{$11$が増えた} \\ 11011 & 7 & \\ 11000 & 8 & \\ 11001 & 9 & \\ 11110 & 10 & \\ 11111 & 11 & \\ 11100 & 12 & \\ 11101 & 13 & \\ 10010 & 14 & \REMTEXT{$10$に変わった} \\ 10011 & 15 & \\ 10000 & 16 & \\ 10001 & 17 & \\ 10110 & 18 & \\ 10111 & 19 & \\ 10100 & 20 & \\ 10101 & 21 & \\ \vdots & \vdots & \\ \end{array} $$

「縦読みしたときに交互になるという意味では、 $2$ 進数のパターンと少し似ているところもあるけど、 $2$ 進数と $-2$ 進数ではまったく違うなあ」

ミルカ「まったく違うだろうか?」

「え?」

ミルカ「たとえば $0$ や $1$ を考えると、 $2$ 進法で表記しても $-2$ 進法で表記しても同じだ」

「そりゃそうだけど」

ユーリ「$4$ も! 両方 $100$ になる!」

ミルカ「では問題」

問題1

$n$ は $0$ 以上の整数とする。

$n$ を $2$ 進法で表記した場合と、 $-2$ 進法で表記した場合に、 同じ表記になるのはどんなときか。 $n$ についての条件を求めよ。

「……」

ユーリ「……」

「そうか……もしかすると、 $4$ の冪乗?」

リサ「できた」

ミルカ「プログラムで表を作っても、条件を求めたとはいえない」

リサ「なぜ」

ミルカ「たとえば、 『$n = 341$ のとき、 $2$ 進法と $-2$ 進法で表記が同じになるか?』 という問いに答えられないから」

リサ「表を $341$ までに」

ミルカ「ならば $n = 1501199875790165$ のときは? 切りがない」

「表を作り直さなくても、 $341$ や、その……すごく大きな数の表記を調べるだけでいいよね」

ミルカ「プログラムで確かめられたとしても、条件を求めるのは別の話」

「ところで、条件は見つかったよ。 《$n$ が $4$ の冪乗の和で表されること》が求める条件だ」

ミルカ「正解」

ユーリ「$4$ のべきじょうの……わ?」

「$4^0, 4^1, 4^2, 4^3, \ldots$ つまり $4^k$ の形で表される数を 何個か選ぶんだよ。そしてそれらを足し合わせる。 たとえば、 $4^0$ と $4^2$ を選んだとする。 そうすると、 $4^0 + 4^2 = 1 + 16 = 17$ だよね。 リサが作ってくれた表を見ると、確かに $17$ は同じ表記になっている」

リサ「$17$ 確認完了 $10001$」

ユーリ「でも、なんで? どっから $4$ が出てきたの?」

「$4 = (-2)^2$ だよ。ほら、 $-2$ 進数を一般的に書いた式があるよね。 あれでわかった」

ユーリ「へー」

「$2$ 進数と $-2$ 進数を一般的に書いてみるとこうなる」

$2$ 進数

$$ a_{n-1}2^{n-1} + \cdots + a_32^3 + a_22^2 + a_12^1 + a_02^0 $$

$-2$ 進数

$$ a_{n-1}(-2)^{n-1} + \cdots + a_3(-2)^3 + a_2(-2)^2 + a_1(-2)^1 + a_0(-2)^0 $$

ユーリ「ぜんぜん違うじゃん」

「いやいや、 $k$ が偶数のとき、 $(-2)^k$ は、 $2^k$ に等しいよね。 だから、並べて書いてみると……」

$$ \begin{array}{cccccccccccccc} \REMTEXT{$2$進数} & \cdots &+& a_32^3 &+& a_22^2 &+& a_12^1 &+& a_02^0 \\ \REMTEXT{$-2$進数} & \cdots &+& a_3(-2)^3 &+& a_22^2 &+& a_1(-2)^1 &+& a_02^0 \\ \end{array} $$

ユーリ「そっか!  $2$ の偶数乗っていうのは、 $4$ の冪乗?」

「そうそう。 $4$ の冪乗をいくつか集めて作った和というのは、 《$2^{\REMTEXT{偶数}}$の位》にしか$1$がない数になる。 そしてそういう数は $2$ 進法と $-2$ 進法で等しくなるんだね」

ミルカ「正解」

解答1

$n$ は $0$ 以上の整数とする。

$n$ を $2$ 進法で表記した場合と、 $-2$ 進法で表記した場合に、 同じ表記になる条件は、 $n$ が $4$ の冪乗の和で表されることである。

リサ「条件……」(咳)

ユーリ「$-2$ 進数の表を作るプログラムって、どんなの……どんなものですか、 リサさん?」

リサ「《さん》は不要」

リサはコンピュータのディスプレイを向ける。

無料で「試し読み」できるのはここまでです。 この続きをお読みになるには「読み放題プラン」へのご参加が必要です。

ひと月500円で「読み放題プラン」へご参加いただきますと、 434本すべての記事が読み放題になりますので、 ぜひ、ご参加ください。


参加済みの方/すぐに参加したい方はこちら

結城浩のメンバーシップで参加 結城浩のpixivFANBOXで参加

(2015年1月16日)

書籍『数学ガールの秘密ノート/ビットとバイナリー』

この記事は『数学ガールの秘密ノート/ビットとバイナリー』として書籍化されています。

書籍化にあたっては、加筆修正をたくさん行い、 練習問題や研究問題も追加しました。

どの巻からでも読み始められますので、 ぜひどうぞ!

無料でWeb立ち読み アマゾンで購入

[icon]

結城浩(ゆうき・ひろし) @hyuki


『数学ガール』作者。 結城メルマガWeb連載を毎週書いてます。 文章書きとプログラミングが好きなクリスチャン。2014年日本数学会出版賞受賞。

Twitter note 結城メルマガ Mastodon Bluesky Threads Home