e-Gadget - プログラム関数電卓　Casio Python - Shell 画面とグラフィック画面の活用：コラッツ問題

Casio Python - Shell 画面とグラフィック画面の活用：コラッツ問題

Casio Python
Casioグラフ関数電卓の Python を使ってみる
　　　　　- Shell 画面とグラフィック画面の活用：コラッツ問題

初版：2020/12/12

▲ 前の記事 - 16. circle() 関数のFXモデルへの拡張 | ▼ 次の記事 -

17. Shell 画面とグラフィック画面の活用：コラッツ問題

<fx-CG50 OS3.40以降にに対応>

Casio Python は、入出力に極めて大きな制限があります。そこで今回は、Casio Python で shell 画面とグラフィック画面 (描画画面) をうまく活用して、出力方法を工夫してみます。そのための題材として、コラッツ問題を取り上げます。

17.1 コラッツ問題 (Collatz Problem) とは？

数学の未解決問題の1つにコラッツ問題 (コラッツ予想) があります。

▶ コラッツ問題

任意の正の整数 n に対して、関数 f(n) を以下のように定義する。
　 f(n) = 3n+1　　(n が奇数のとき)　　

　　　　　 n/2 　　 (n が偶数のとき)

この関数を使って、繰り返し演算を続けて、以下のように数列 a_i を作る。
　・a₀ = n

　・a_i = f(a_i-1)

どのような正の整数 n のときでも、数列は 1 に到達する。

要素が１になるまでの数列 a_i (i≧0) をコラッツ数列と言います。小学生レベルの四則演算で計算できる一見単純そうな問題です。コンピュータを使って実際に計算して要素が１に到達しない例がまだ見つかっていません。5x2⁶⁰ まで計算されているそうです。しかし、数学的にまだ証明されていません。

数学的に証明されていない限り、もっと大きな整数でコラッツ予想が成り立たなくなる例が見つかるかも知れません。

実際に計算してみます。

(1) n=6 のときのコラッツ数列 (i≧0)
a_i = 6, 3, 10, 5, 16, 8, 4, 2, 1
▶ 最初に a_i=1 になるとき i = 8

(2) n=25 のときのコラッツ数列 (i≧0)
a_i = 25, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
▶ 最初に a_i=1 になるとき i = 23

(3) n=27 のときのコラッツ数列 (i≧0)
a_i = 27, 82, 41, 124, 62, 31. 94, 47, 142, 71, 214, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 991, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1
▶ 最初に a_i=1 になるとき i = 111

n が 1 から 26 までは、手計算でも順調にできますが、n=27 になると途端に大変になり、9232 まで大きくなってしまうと、本当に 1 になるのか不安になりますが、結果として 1 に到達できました。

より詳しくは "コラッツ問題" や "コラッツ予想" で検索すれば、色々な情報が得られます。

管理人としては、Casio Python で、
　・計算しながら、数列の要素をグラフ表示させ、
　・最後は、コラッツ数列の全ての要素を出力させる
そのようなスクリプトを作りたくなりました。

計算中は、数列の i の値と a_i の値 (数列の要素の値) がどんどん変化している様子をリアルタイムで表示させながら、a_i の値の推移をグラフ表示させ、計算が終われば a_i の最大値も表示させます。最後に算出した全ての a_i (数列の全ての要素) を出力させます。

今回は、以下のような動作をする Casio Python スクリプト - Collatz.py を作ります。

▶ Collatz.py ⇒ ダウンロード

"""Sample script

　Collatz Problem Simulation ver1.0;
　- Graphical and numerical output of
　　Collatz sequence a0, a1, a2 ... an

　Collatz.py
　　for fx-CG50 OS3.40 or later
　　　by Krtyski/e-Gadget
"""

from u import *

#Input integer >1
print('\n\n\n== Collatz Problem ==\n\n')
n=int(input('Input number:'))

#Initialize variables
offset=150
scale=50
a=[0]; a[0]=n; i=0

#Draw initial screen
locate(0, 0, 'a :', size='l')
locate(3, 1, '0', size='s')
locate(3, 0, a[0], color='blue', size='l')
locate(0, 1, 'i :', size='l')
locate(0, 2, 'a :', size='l')
locate(3, 5, 'i', size='s')
locate(0, 3, 'a :', size='l')
locate(2, 7, 'max', size='s')
line(offset, 191, 383, 191)

#Calculate and draw element of sequence
while a[i]!=1:
　#Increment index
　i+=1

　#Erase previous numbers
　locate(3, 1, i-1, color=0, size='l')
　locate(3, 2, a[i-1], color=0, size='l')

　#Calculate next element of sequence
　if a[i-1]%2:
　　a.append(3*a[i-1]+1)
　else:
　　a.append(a[i-1]//2)

　#Draw updated numbers
　locate(3, 1, i, size='l')
　locate(3, 2, a[i], size='l')

　#Draw (update) graph of sequence
　if a[i]//scale<192:
　　line(offset+i-1, 191-a[i-1]//scale, offset+i, 191-a[i]//scale, (255, 0, 0))

#Draw finally maximum element
locate(3, 3, max(a), size='l')

#Output all elements of sequence
locate(0, 7, '[EXIT]', size='l')
for i in range(i+1):
　print('a' + str(i) + '=' + str(a[i]))

このスクリプトを見て、何をやっているのかスグに判る場合は、Collatz.py を実行して遊んでみて下さい。

これ以降は、Cllatz.py の解説を行い、少し遊んでみた結果を紹介します。

17.2 コラッツ数列の計算

今回は、コラッツ数列をリストで表現することにします。

つまり、
　数列：a_i = a₀, a₁, a₂, ... ,a_i-1, a_i
を
　リスト：a = [a₀, a₁, a₂, ... ,a_i-1, a_i]

とすると、i 番目の要素は a[i] で得られます。

スクリプトの冒頭で、リスト a の定義 (a=[0]) を行います。この定義では、要素が数値 0 が 1個しかないリストを定義しています。計算が終わらないと要素数が判らないので、次の要素を算出したときに、.append() 関数を使ってリストにその要素を追加し、i を1つづつ増やすようにします。

1つめの要素は、i=0 のときであり、その値は n なので、a[0]=n とします。
すると、リスト a[i] は以下のようにして求められます。

a=[0]; a[0]=n; i=0

while a[i]!=1:
　#Increment index
　i+=1

　#Calculate next element of sequence
　if a[i-1]%2:
　　a.append(3*a[i-1]+1)
　else:
　　a.append(a[i-1]//2)

これを解説します；

a[i] を求めるには、1つ前の a[i-1] を使って、

・a[i-1] が奇数のとき、
　言い換えると、a[i-1] を 2で割ったときの余りが 0 でない時、
　つまり a[i-1]%2 が 0 でない時
　　3 × a[i-1] +1 をリスト a の末尾に追加する、つまり
　　a.append(3*a[i-1]+1)

・そうでない時、つまり a[i-1] が偶数のとき
　　a[i-1] / 2 をリスト a の末尾に追加する、つまり
　　a.append(a[i-1]//2)
　　※ ここで、リストの要素を整数にしたいので、// 演算子 (割り算の商 = 整数部を得る)を使う

この処理を a[i] が 1 でない限り繰り返せば良いので、上記の処理を whilr a[i] != 1: のループの中に記述しています。

17.3 出力の工夫ポイント

17.3.1 input() での出力
最初に1以上の整数を入力させるには、Casio Python に備わっている唯一の入力関数 input() を使います。
input() を使うと、キー入力した文字列や数値は、全て文字列として返ります。今回は、入力した数値を数値変数 n に代入したいので、input() の戻り値を int() 関数で整数に変換します。

n=int(input())

入力時に表示する文字列は input() の ( ) 内に指定します。

n=int(input('Input number:'))

さて、今回は以下のような入力画面にしてみます。

チョット格好良いですね！
ちなみに、Collatz Problem は コラッツ問題 のことです。

このような配置にするには、改行を利用します。文字列の中に \n を入れたら、そこで改行します。

そこで、入力画面は以下のようにします。

print('\n\n\n== Collatz Problem ==\n\n')
n=int(input('Input number:'))

17.3.2 フォントサイズを変えて添え字の描画
コラッツ数列 a_i は、添え字を使っているので、出力画面でも添え字が表現できると格好イイですよね！
そこで、以下のような表示にしてみました。

ここでは、a0、ai、amax を表示しています。

実は最初は以下のような表示にしましたが、添え字の 0 と i 、特に i が見づらいので却下。上のように見やすさを優先しました。

グラフィック画面では、大、中、小の 3つのサイズのフォントが使えます。フォントピッチ (フォントの大きさ) を考えると、大フォントのピッタリ 1/2 が小フォントになっているので、大フォントの添え字に小フォントを使うとうまくいきそう。

ユーザー関数 locate() を作っているので、これを使います。スクリプトはチョット面倒に見えますが、コンセプトは簡単なので、地道に作ってゆきます。

▶ ユーザー関数 locate() の説明
　※ locate() を使うには、ユーザーモジュール u.py をインポートします。
　　 from u import *

結果は、以下のようになります。

locate(0, 0, 'a :', size='l')
locate(3, 1, '0', size='s')
locate(3, 0, a[0], color='blue', size='l')
locate(0, 1, 'i :', size='l')
locate(0, 2, 'a :', size='l')
locate(3, 5, 'i', size='s')
locate(0, 3, 'a :', size='l')
locate(2, 7, 'max', size='s')

ところで、コラッツ数列 a_i を、今回のスクリプトではリスト a で扱っていて、コラッツ数列の定義から、a₀ は n なので、
　a[0] = n
となります。

上の locate() が並んだスクリプトの、上から3番目に a[0] で出てきていますが、これは n に置き換えても同じです。そして、このときだけ青色で表示していることは、color='blue' がパラメータに入っていることで判ります (ユーザー関数 locate() の仕様)。

17.3.3 リアルタイムに変わる数値の表示
これを実現するには、グラフィック画面 (描画画面) に文字列を描画するしかありません。print() でshell 画面に出力するのでは、スクロールしてしまいます。

グラフィック画面で文字列を描画するには、casioplot モジュールに含まれる draw_string() 関数を使えば良いのですが、より使いやすくするために作ったユーザー関数 locate() を使います。

描画した文字列を新しい文字列で上書きするには、以下の手順が必要になります。
　(1) 色を指定して文字列を描画
　(2) 同じ位置に同じ文字列を白で再描画して、文字列を消去
　(3) 同じ位置に新たな文字列描画
手順 (2) が不可欠です。

※ locate() を使うには、ユーザーモジュール u.py をインポートします。
　 from u import *

コラッツ数列をリスト a として得るための while ループの中に、i の値と a[i] の値をリアルタイムで描画するコードを追加すると、以下のようになります。

#Calculate and draw element of sequence
while a[i]!=1:
　#Increment index
　i+=1

　#Erase previous numbers　◀ この2行↓を追加
　locate(3, 1, i-1, color=0, size='l')
　locate(3, 2, a[i-1], color=0, size='l')

　#Calculate next element of sequence
　if a[i-1]%2:
　　a.append(3*a[i-1]+1)
　else:
　　a.append(a[i-1]//2)

　#Draw updated numbers　◀ この2行↓を追加
　locate(3, 1, i, size='l')
　locate(3, 2, a[i], size='l')

17.3.4 グラフの描画
横軸に i の値、縦軸に a[i] の値をとって、ユーザー関数 line() を使ってグラフを描画します。

基本的には、点 (i-1, a[i-1]) と点 (i, a[i]) を結んだ線分を描画することになりますが、画面全体の左上が原点になる座標系から、所定の長方形のエリアの中に収まるように変換して描画する必要があります。

今回は、点 (x, y) について以下のように変換します。

▶ 横座標 (x座標) は、
　　左から 150 ドットの位置から右側を使うので、変数 offset = 150 として、
　　offset だけ右にずらすので、x を offset+x に変換します。

▶ 縦座標 (y 座標) は、
　　上下反転させ、変数 scale = 50 として 50分の1に圧縮して整数部を取得するので、
　　y を 191-y//scale に変換します。

ちなみに、// 演算は除算した時の商、つまり割り算結果の整数部を得るもので、これにより整数値が得られます。line() 関数に指定する座標パラメータは整数でなくてはならない(仕様です)ので、// 演算を用います。

以上から、
　点 (i-1, a[i-1]) は、点 (offset+i-1, 191-a[i-1]//scale) に
　点 (i, a[i]) は、点 (offset+i, 191-a[i]//scale) に
変換できます。

そして、今回はグラフを赤 (r, g,b) = (255, 0, 0) で描画することにしているので、line() 関数を使った線分描画は、以下のようになります。

　line(offset+i-1, 191-a[i-1]//scale, offset+i, 191-a[i]//scale, (255, 0, 0))

ところで、今回のグラフ描画エリアも画面に表示します。但し長方形のエリアではなく、エリアの下端のみを直線で示すことにします。そこで、line() 関数を使って、以下のようにします。
　line(offset, 191, 383, 191)

さて、今の line() 関数の仕様では、画面の外の座標を指定すると、エラーにならず見えない範囲に線分描画の動作を行うので、見えない線分描画に時間がかかってしまいます。そこで、今回指定したグラフ描画エリアの外の座標を設定する場合は描画をスキップするようにして、全体として高速化します。

具体的には、a[i]//scale の値がグラフ描画エリアの高さ(縦幅)に収まるときだけ、line() 関数で描画するようにしました。
　if a[i]//scale＜192:
　　line(offset+i-1, 191-a[i-1]//scale, offset+1, 191-a[i]//scale, (255, 0, 0))

▶ ユーザー関数 line() の説明
　 ※ line() を使うには、ユーザーモジュール u.py をインポートします。
　　 from u impot *

offset=150　　　　　　　　　　　　◀ この行を追加
scale=50　　　　　　　　　　　　　◀ この行を追加
a=[0]; a[0]=n; i=0

line(offset, 191, 383, 191)　◀ この行を追加

#Calculate and draw element of sequence
while a[i]!=1:
　#Increment index
　i+=1

　#Erase previous numbers
　locate(3, 1, i-1, color=0, size='l')
　locate(3, 2, a[i-1], color=0, size='l')

　#Calculate next element of sequence
　if a[i-1]%2:
　　a.append(3*a[i-1]+1)
　else:
　　a.append(a[i-1]//2)

　#Draw updated numbers
　locate(3, 1, i, size='l')
　locate(3, 2, a[i], size='l')

　#Draw (update) graph of sequence　◀ この2行↓を追加
　if a[i]//scale<192:
　　line(offset+i-1, 191-a[i-1]//scale, offset+i, 191-a[i]//scale, (255, 0, 0))

17.3.5 数列の値の最大値を求めて表示
冒頭で、整数 27 からコラッツ数列を求めたところ、最大 9232 とかなり大きな数になったのに、少し驚きました。そこで、求めた数列の最大の要素を表示したいと思いました。

そこで while ループ終了後に、a[i] の最大値を求めて表示します。
リスト a の要素から最大値を返す関数 max() を使えば、max(a) が最大値を返します。

ところで、max() 関数は、最大値が2つ以上有る時は、リストの中で一番左にあるものを返します。今回は最大値のみに感心があるので、max() 関数を使うだけで十分です。

この最大値を locate() 関数で、所定の位置に描画するには、以下のように記述します。
　locate(3, 3, max(a), size='l')

==========

#Initialize variables
offset=150
scale=50
a=[0]; a[0]=n; i=0

#Calculate and draw element of sequence
while a[i]!=1:
　#Increment index
　i+=1

　#Erase previous numbers
　locate(3, 1, i-1, color=0, size='l')
　locate(3, 2, a[i-1], color=0, size='l')

　#Calculate next element of sequence
　if a[i-1]%2:
　　a.append(3*a[i-1]+1)
　else:
　　a.append(a[i-1]//2)

　#Draw updated numbers
　locate(3, 1, i, size='l')
　locate(3, 2, a[i], size='l')

　#Draw (update) graph of sequence
　if a[i]//scale<192:
　　line(offset+i-1, 191-a[i-1]//scale, offset+i, 191-a[i]//scale, (255, 0, 0))

#Draw finally maximum element　◀ この1行を追加
locate(3, 3, max(a), size='l')

17.3.6 shell 画面でのスクロール出力
最後に、コラッツ数列の全要素を表示したいのですが、計算するまでは要素数が判らないので、グラフィック画面に出力するよりも、shell 画面でスクロールさせて出力するのが良いと思います。スクロールアップ/ダウンも自由にできるので、全要素を詳しく見るのに適しています。

冒頭の動画で判るように、グラフィック画面と shell 画面を、適材適所でうまく使い分けると良いと思います。

shell 画面でリスト a の要素 a[0] から a[i] までを表示するには、

　for i in range(i+1):
　　print(a[i])

とすればOKです。

ここでは、コラッツ数列の要素を表示するのが本来な目的なので、例えば i = 70 のときの a_i を表示する場合は、

　a70=991

と表示しようと思います。そこで、スクリプトは以下のようになります。

　for i in range(i+1):
　　print('a' + str(i) + '=' + str(a[i]))

グラフィック画面 (描画画面) が表示されているとき、shell 画面に切り替える方法が２つあります。
・[EXIT]キーを押す
・input() を実行する

今回は、[EXIT] キーを押せば良いので、グラフィック画面のまま維持しておき、[EXIT] キーを押してもらってから、shell 画面に切り替わるようにします。そこで、操作ガイドの意味で、グラフィック画面の左下に [EXIT] と表示しようと思います。
　locate(0, 7, '[EXIT]', size='l')

これに続いて、上記のリスト a の要素表示のスクリプトを追加すれば、うまくゆきます。

最後に Casio Python の制限について、付記しておきます。fx-CG50 の Pythonモードでは、print() 関数の出力は最大 200行に制限されています。コラッツ数列 (= リスト a) の要素数が 200 個を超えると、全ての要素が表示されません。

色々と整数を変えて遊んでいる限りは、今のところ 200 行を超えるケースがないので、なんとかなりそうです。以下の動画では、整数が20000以下のときは、要素数 200 を超える場合が結構少ないことが判ります。

もし 200 行を超えるものが沢山でてくるならば、チョット面倒ですが工夫次第でなんとかできると思います。

==========

全要素表示の部分を最後に追加し、今回検討したスクリプト全体を以下に示します。

from u import *

#Input integer >1
print('\n\n\n== Collatz Problem ==\n\n')
n=int(input('Input number:'))

#Initialize variables
offset=150
scale=50
a=[0]; a[0]=n; i=0

#Draw initial screen
locate(0, 0, 'a :', size='l')
locate(3, 1, '0', size='s')
locate(3, 0, a[0], color='blue', size='l')
locate(0, 1, 'i :', size='l')
locate(0, 2, 'a :', size='l')
locate(3, 5, 'i', size='s')
locate(0, 3, 'a :', size='l')
locate(2, 7, 'max', size='s')
line(offset, 191, 383, 191)

#Calculate and draw element of sequence
while a[i]!=1:
　#Increment index
　i+=1

　#Erase previous numbers
　locate(3, 1, i-1, color=0, size='l')
　locate(3, 2, a[i-1], color=0, size='l')

　#Calculate next element of sequence
　if a[i-1]%2:
　　a.append(3*a[i-1]+1)
　else:
　　a.append(a[i-1]//2)

　#Draw updated numbers
　locate(3, 1, i, size='l')
　locate(3, 2, a[i], size='l')

　#Draw (update) graph of sequence
　if a[i]//scale<192:
　　line(offset+i-1, 191-a[i-1]//scale, offset+i, 191-a[i]//scale, (255, 0, 0))

#Draw finally maximum element
locate(3, 3, max(a), size='l')

#Output all elements of sequence　◀ この3行↓を追加
locate(0, 7, '[EXIT]', size='l')
for i in range(i+1):
　print('a' + str(i) + '=' + str(a[i]))

17.4 コラッツ問題で遊んでみる

適当に入力する整数を選んで、コラッツ数列の要素数 i が大きい順に並べてみました。ここでは、170 ⇒ 160 ⇒ 151 を例に挙げています。当然これより大きな要素数になるケースは間違いなくあります。

グラフの縦軸は、縮尺率 scale = 50 にしているから、191 x 50 = 9550 が表示できる a_max の上限です。これを超える場合は表示されていません。上の3つの例では、いずれも a_max は 9550 以上になっています。

これに続く要素数は、例えば以下のように 146 ⇒ 144 ⇒ 136 になりました。

要素数 i に関わらず要素の最大値 a_max は 9232 になっています。最初に与える整数 a₀ (=リストa[0]) が 27 の時も a_max = 9232 で同じなので、数列要素の計算の終盤の計算パターンが同じになっているようですね。a_max が 9550 以下なので、グラフは描画エリア内に収まっています。

さらに、これに続く要素数は、例えば以下のように 132 ⇒ 127 ⇒ 125 なりました。

要素の最大値 a_max が 9232 になる計算パターンは、a₀ (=a[0]) が小さい時に多く見られるようです。

そして、a_max が 9232 になるとき、a₀ (=a[0]) の最小値は 27 なのは簡単に確認できます。その時の要素数 i は 111 です。