ちょっと変わったフィボナッチ数の作り方

15歳女子が「フィボナッチ数列は2進数でも美しいのか」を考察 算数・数学の自由研究作品コンクール「MATHコン」で日本数学検定協会賞を受賞 | プレスリリース | 公益財団法人 日本数学検定協会

フィボナッチと聞いて、昔編み出した少し変わったフィボナッチ数の作り方を思い出した。とは言っても、俺が思いつくレベルの話なのでとっくに誰かが考えているだろうけど。

以下のようなオブジェクトを定義する

  • あるオブジェクトについて
    • 2回だけクローンを作れる
    • 2回クローンを作ると死ぬ

このオブジェクトに1ターンに1つずつクローンを作らせていくと、各ターンに生きているオブジェクトの総数がなんとフィボナッチ数になるのです。

思い出しながら適当に書いたコードはこんな感じ。

require 'set'

class Cell
  def initialize(life)
    @count = life
    @life = life
  end
  def clone
    @count -= 1
    Cell.new(@life)
  end
  def alive?
    @count > 0
  end
end

s = Set.new
s << Cell.new(ARGV[0].to_i)

list = []

10.times do
  list << s.size
  s2 = Set.new
  s.each { |c|
    s2 << c.clone
    s2 << c if c.alive?
  }
  s = s2
end

puts list.join(" ")

見るからに効率が悪そうなコードなのだが、実際最悪なのでループは10回までにしておきます。100回とかやると死ぬ。で、実行するとこうなる

$ ruby nacci.rb 2
1 2 3 5 8 13 21 34 55 89

n=0とn=1の値がありませんが、n=2からのフィボナッチ数ですね。

これはフィボナッチ数は1つ前と2つ前の数字を足していくものなので、オブジェクトを2ターン生かしておけば2つ前の状態まで反映されるだろう、という考え方。なので生存期間を3ターンにするとトリボナッチ数になります。

$ ruby nacci.rb 3
1 2 4 7 13 24 44 81 149 274

同様に生存期間を4ターンにするとテトラナッチ数になります。

$ ruby nacci.rb 4
1 2 4 8 15 29 56 108 208 401

生存期間を無限大にすると2のn乘の数列になります。オブジェクトが不死の場合、倍々ゲームで増えるモデルなので当然そうなるんですが、フィボナッチ数列と2のn乘の数列ってどこかで繋がっているようですね。