<a href="http://blog.livedoor.jp/dankogai/archives/50509245.html">継子立て</a>

断り書き：話を順序立てて書くため、全面的に改稿しました。トラックバック先の文章とは異なっていますがご了承ください。


まずはポテトチップスを実際に食べてみよう。ただし、1枚から100枚まで順番に。

#!/usr/bin/ruby
1.upto 100 do |n|
    card = Array.new.fill(0, n){|i| i+1}
    while card.size > 1 do
        card.push card.shift
        card.shift
    end
    printf "%3i %3i\n", n, card.shift
end

出力は次のような感じ。

  1   1
  2   1
  3   3
  4   1
  5   3
  6   5
  7   7
  8   1
  9   3
 10   5
 11   7
 12   9
 13  11
 14  13
 15  15
 16   1
 17   3
 18   5
 19   7
 20   9
…

もちろん実際には100まで出てくるが、ここまでで十分、解の数列の特徴は掴める。

• 
• 
• 但し > となったらとする

というわけで、直接答えを表示するスクリプト。

#!/usr/bin/ruby
a = -1
1.upto 100 do |n|
    a += 2
    a = 1 if a > n
    printf "%3i %3i\n", n, a
end

1に戻るまでの数列の長さが、1,2,4,8,16,32…と、2のべき乗になっていることに注目して、if文を排除するように上のスクリプトを全面改定すると↓次のようになる。

#!/usr/bin/ruby
0.upto 6 do |i|
    j = 2 ** i
    0.upto(j - 1) do |k|
        printf "%3i %3i\n", j + k, k * 2 + 1
    end
end

これらのスクリプトはから順にしか解を求められないが、1,2,4,8,16,…という2のべき乗の和をとると、

になる、という関係を利用すれば、からを直接求めることが可能になる。

#!/usr/bin/ruby
n = ARGV.shift.to_i
puts (n - 2 ** (Math.log(n) / Math.log(2)).to_i) * 2 + 1

終了。