概要
たまたま知ったレカマン数列(Recaman's Sequence)に関するメモ。漸化式や特徴を確認し、数列の動きを描写してみる。
レカマン数列とは
レカマン数列$a_{n}$は、下記の漸化式で表される。
$ a_n = \begin{cases} 0 & (n = 0) \\ a_{n-1} - n & (a_{n-1} - n \gt 0 \ \text{and is not already in the sequence}) \\ a_{n-1} + n & (\text{otherwise}) \end{cases} $
初項は$0$で、$a_{n}$は$a_{n-1}$に依存して決まる。 $a_{n-1} - n$の値が0より大きく、これまで数列中に現れていない場合、その値が$a_{n}$となる。 そうでなければ、$a_{n-1} + n$の値が$a_{n}$となる(この場合、$a_{n-1} + n$の値が既に数列中に現れていることもある)。
特徴としては以下の通りである。
3つ目の特徴の例としては、$a_{20}$と$a_{24}$の値が$42$となることが挙げられる。また、$852655$が現れる項が確認されていないようである(4つ目の特徴)。
描写
参考に載せたYouTubeの動画にて、レカマン数列の動きが確認できる。それにならい、pythonでレカマン数列が描く模様を出力してみる。
from matplotlib import pyplot as plt from matplotlib import patches as pat rec = [] rec_MAX = 100 for i in range(rec_MAX): if i == 0: rec.append(0) elif rec[i - 1] - i > 0 and (rec[i - 1] - i) not in rec: rec.append(rec[i - 1] - i) else: rec.append(rec[i - 1] + i) x_MAX = 120 y_MAX = 60 fig, ax = plt.subplots(figsize=(10, 10)) ax.set_xlim([0, x_MAX]) ax.set_ylim([-y_MAX, y_MAX]) for i in range(rec_MAX - 1): if i % 2 == 0: patch = pat.Wedge(center = ((rec[i + 1] + rec[i]) / 2, 0), r = abs((rec[i + 1] - rec[i])) / 2, theta1 = 180, theta2 = 360, width = 0.01, color = 'k') ax.add_patch(patch) else: patch = pat.Wedge(center = ((rec[i + 1] + rec[i]) / 2, 0), r = abs((rec[i + 1] - rec[i])) / 2, theta1 = 0, theta2 = 180, width = 0.01, color = 'k') ax.add_patch(patch) plt.savefig('result.png')
上記pythonスクリプトの前半でレカマン数列($a_{0}$から$a_{99}$まで)を生成し、後半で模様を描いている。偶数番目の項から奇数番目の項への移動は下半分の弧(扇形で代用)で描き、奇数番目の項から偶数番目の項への移動は上半分の弧で描いている($a_{0}$は偶数番目の項として扱った)。 実行すると、同ディレクトリ内にresult.pngが生成される。
感想
$852655$が何だか不思議な数字に思えてきました。また、漸化式の単純さに反して、もっと認知されていても不思議ではない数列だと感じました(数学の世界では有名なんでしょうか?)。レカマン数列を用いたステガノグラフィがあるらしいので、それに関する論文(理解できるようなもの)があれば読んでみたいと思います。