紙は何回折れるか？

かなり有名な事実で，「ほぼ8回」というのが正解。

厚さ 0.1 mm，一辺 100 m の紙を，偶数回ごとに正方形になるように 8 回折れば，厚さは 0.1 / 1000 * 2^8  = 0.0256 m で，正方形の一辺の長さは 6.25 m。まだ十分に折れそうではあるが，10 回折ると，厚さは 0.1024 m，一辺の長さ3.125 m だが，折られた紙のそれまでの折り線付近が折りにくくなる。フットボール競技場大の紙を折るときは 11 回折れたという動画がある。

柔らかい紙を一方向に折っていくともう少し多く折れる。1200メートルのトイレットペーパーを半分ずつに折るのは 12回できたという写真がある（ワンカットの動画でないので正しさの証明はないが）。このとき，最終のトイレットペーパーの長さは 1200*0.5^12 =  0.2929688 で，まあ写真にあるように肘の長さ。

以上のように折るのは難しいが，半分ずつに切って，それを積み重ねるというのは思考実験としてはもう少し可能性が高い。

上のように，厚さ 0.1 mm，一辺 100 m の紙を，偶数回ごとに正方形になるように 8 回切って積み重ねる。もちろん，カッターなどを使って一回で切る。あるいはそれをシミュレートするように分割して切る。こうすれば 25 回切ると 0.1 / 1000 * 2^25 = 3355.443 m でほぼ富士山と同じ高さ。しかし，このときの一枚の紙切れは 1.22 cm × 2.44 cm だ。とても積み重ねることはできない。25 回目の紙を切る長さは延べ 409600 m。一枚一枚ハサミで切っていたら大変。全部で 1228600 m = 1228.6 km。札幌〜福岡の直線距離が約 1400 km。

高さはものすごい勢いで大きくなり，面積は逆にものすごい勢いで小さくなる。

一休さんかだれかが，殿様が褒美をやろうというのに答えて，「今日は碁盤の1マスに1粒のお米，明日は2倍の2粒，その次にはさらに2倍の4粒というようにして最後の一マスまでお願いします」というのも有名な話。一般的な碁盤のマス目は 18*18 = 324。324 番目のマス目には 2^(324-1) =1.70879e+97 個の米粒が載る（わけない）。碁盤全部では sum(2^(0:323)) = 3.417579e+97 粒。

これを逆方向に使ったのが，f(x) = 0 の解を求める二分法というアルゴリズム。-1000 から 1000 までの区間を半分にし，解のある方の区間を更に半分にしていく。30 回繰り返すと解の存在する区間幅は 2000*0.5^30 = 1.862645e-06 になる。

もし 2000 ページの辞書があって，調べたい単語が載っているページを探すとき，ほぼ半分ぐらいの所を開き，前のほうにあるか後ろのほうにあるかだけの情報で単語のある方の更に半分のページを開き...ということを繰り返すと 10 回目には 2ページが残る。 000*0.5^10 = 1.953125。11 回目で単語を含むページに達する。

この例は，単語がまさに辞書順に載っているからできることである。2000人の名前が名簿がコンピュータに記憶されているとき，でたらめに並んでいると，ある人を探すとき，最短では 1 回，最長では 2000 回，平均でも 1000 回の探索が必要だが，辞書順に並べ替えておくと最長でも 11 回で探し出せる。

 N.PRIME 個までの素数の配列 prime がある。整数 n が何番目の素数であるか探索するプログラムを書く。ただし，prime に含まれない数が与えられた場合は not found と表示する。

N.PRIME = 2000

素数配列を作成する

library(gmp)
prime = integer(N.PRIME)
a = 1
for (i in 1:N.PRIME) {
  prime[i] = a = as.integer(nextprime(a))
}

head(prime)
tail(prime)

線形探索（端から順番に探していく）

find1 = function(n) {
  found = 0
  for (i in 1:N.PRIME) {
    if (n == prime[i]) {
      found = i
      break
    }
  }
  if (found == 0) {
    print("not found")
  } else {
    print(sprintf("%d = prime[%d]", n, found))
  }
}

find1(1)
find1(2)
find1(7919)
find1(7909)
find1(17389)
find1(20000)

バイナリーサーチ（二分探索）

find2 = function(n) {
  found = 0
  begin = 1
  end = N.PRIME
  n.begin = prime[begin]
  n.end = prime[end]
  while (n.begin <= n && n.end >= n) {
    if (n.end == n) {
      found = end
      break
    }
    if (end == begin + 1 && prime[end] != n && prime[begin] != n) {
      break
    }
    middle = (begin + end) %/% 2
    n.middle = prime[middle]
    if (n.middle == n) {
      found = middle
      break
    } else if (n.middle > n) {
      end = middle
    } else {
      begin = middle
    }
  }
  if (found == 0) {
    print("not found")
  } else {
    print(sprintf("%d = prime[%d]", n, found))
  }
}

find2(1)
find2(2)
find2(7919)
find2(7909)
find2(17389)
find2(20000)

R の機能を最大限利用するプログラム

find3 = function(n) {
  pos = prime == n
  if (sum(pos) == 0) {
    print("not found")
  } else {
    found = (1:N.PRIME)[pos]
    print(sprintf("%d = prime[%d]", n, found))
  }
}

find3(1)
find3(2)
find3(7919)
find3(7909)
find3(17389)
find3(20000)