続・フィボナッチとはじめてのPython
この問題をPythonでやってみます。
つぎのような操作を考える。
xが奇数のとき1加える、f(x) = x + 1
xが偶数のとき2で割る、f(x) = x / 2
任意の自然数xからはじめてfの操作を繰り返すと必ず1になるのはなぜか？x=5のとき、5→6→3→4→2→1であり、5回で1になる。
n回で1になる数を書き出せ。いくつあるか？
必ず1になる証明は、中学くらいの数学でやったことがあるのではないかと思います。奇数のときf(x) = 3x + 1だと、コラッツの問題といって未解決の難問なのですが。
ひとまず1になる証明です。xが奇数のとき1加えると偶数になるので、次の操作で2で割ることになります。そこで、まとめて(x + 1) / 2という操作を考えます。元の数xを引くと(x + 1) / 2 - x = (1 - x) / 2。xが3以上の奇数であれば負の値となるため、操作によって必ず小さくなることがわかります。xが2以上の偶数のときx / 2 < xですので、操作によって必ず小さくなることがわかります。2以上の自然数が必ず小さくなる操作を繰り返せば最後は1になります。
n回で1になる数を書き出します。
1から逆にたどって作れそうなので、呼ぶと1回分遡った数字のリストを返すstepという関数を作り、n回呼びます。code#5
def step(current):
result = []
for i in current:
if i % 2 == 0:
if i - 1 > 1:
result += [i-1]
result += [i*2]
return result
while True:
print("input:", end="")
num = int(input())
result = [1]
for i in range(num):
result = step(result)
print(result)
print(len(result))5、6、7を入力した結果がこちらで、n回で1になる数字が作れてます。そして個数がフィボナッチ数っぽいです。
input:5
[5, 12, 14, 15, 32]
5
input:6
[10, 11, 24, 13, 28, 30, 31, 64]
8
input:7
[9, 20, 22, 23, 48, 26, 27, 56, 29, 60, 62, 63, 128]
13
このコードで全ての自然数を覆い尽くせると言われると一見不思議ですが、5から8までの数字を2倍した数字とそこから1引いた数字が9から16までの数字になるので納得できます。
この問題を眺めていたらある規則に気づきました。ここからはその話をして、それに基づいたコードを書きます。
このようなことを考えました。「この問題は2つの操作の組み合わせで任意の自然数を表現できると主張しているようだ。2進数の考え方と同じなのでなにか関係があるのではないか？」
結果として関係を見つけました。
x-1を2進数表記し、下の桁から順に0を(x + 1) / 2、1をx / 2と読み替えたものが、自然数xに対する操作の手順を示している。
たとえば例示されていたx=5の場合、x-1=4の2進数表記は100なので、
0 → (5 + 1) / 2 = 3
0 → (3 + 1) / 2 = 2
1 → 2 / 2 = 1
確かに成り立っています。
x=41であれば40を2進数表記して101000が操作手順です。大きな数でも必ず成り立っているのです。
なぜでしょうか？証明してみます。
x-1を2進数表記した最下位の桁がxに対する次の操作を示しているということなので、xに対して1回操作することと、x-1の最下位の桁を消すことが、対応していることを説明できればいいですね。x-1の最下位の桁が0のとき、最下位の桁を消すのは、x-1を2で割ること、すなわち(x - 1) / 2に相当します。これは(x - 1) / 2 = (x + 1) / 2 -1と変形できるので、操作後に1引いた値になっていることがわかります。x-1の最下位の桁が1のとき、最下位の桁を消すのは、1引いて2で割ること、すなわち(x - 1 - 1) / 2に相当します。これは(x - 1 - 1) / 2 = x / 2 - 1と変形できますので、やはり操作後に1引いた値になっていることがわかります。これで証明できました。
改めて問題で与えられた操作fに分解すると、2進数表記の0は2回分、1は1回分に相当しますので、操作回数がnになる自然数xの数はn-1を1と2の和で表現する方法の数に一致します。なぜなら操作手順はx-1の2進数表記1***(ただし***は0か1を0個以上並べたもの)と対応しているからです。全操作数がnになる自然数xの数をB(n)とすると、前回の記事の結果を組み合わせることにより、B(n) = I(n-1) = F(n)で、フィボナッチ数と一致することがわかります。
せっかくなので、この考察を使ってn回の操作で1になる自然数を列挙してみます。まずn-1を1と2の和で表しながらx-1の2進数表記binnumを生成します。そしてint(binnum, 2)で10進数に変換してから1を加えてxを求めています。Pythonの3項演算子は特徴的だなと思いました。code#6
def func(num_left, binnum_temp, result_temp):
if num_left == 0 and binnum_temp:
result_temp += [binnum_temp]
else:
for i in [1,2]:
if num_left >= i:
binnum = binnum_temp + ("1" if i == 1 else "0")
func(num_left - i, binnum, result_temp)
while True:
print("input:", end="")
num = int(input())
result = []
func(num-1, "1", result)
result2 = []
for binnum in result:
x = int(binnum, 2) + 1
result2 += [x]
print(result)
print(result2)
print(len(result))5、6を入力してみた結果です。5回、6回の操作で1になる数字が作れていますね。
input:5
['11111', '1110', '1101', '1011', '100']
[32, 15, 14, 12, 5]
5
input:6
['111111', '11110', '11101', '11011', '1100', '10111', '1010', '1001']
[64, 31, 30, 28, 13, 24, 11, 10]
8
2つの記事にわたってPythonを使いましたが、ブロックを閉じなくていい書き方が気持ちいいと思いました。実用していきたいです。
.