階乗の約数の個数

2!，3!，4!，…，305! をそれぞれ素因数分解したときに，「2 が素因数として出てくる個数」と「2 ではない素数が素因数として出てくる個数の和」が一致するものがいくつあるか

たとえば，7! を考える場合，2, 3, 4, 5, 6, 7 それぞれの数について，2 とそれ以外の約数が何個ずつあるか数える。7! の約数はそれを全部合計すればよい。 8! の約数は，7! の約数に 8 の約数を加える。以下順に。

prime = c(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,
71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,
157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,
241,251,257,263,269,271,277,281,283,293)
twos = others = numeric(305)
for (i in 2:305) {
  n = i
  t = 0 # 約数 2 の個数
  repeat {
    if (n %% 2) break
    t = t+1
    n = n %/% 2
  }
  twos[i] = t
  for (j in prime) {
    if (n == 1) break
    o = 0 # 2 以外の約数の個数
    repeat {
      if (n %% j) break
      o = o+1
      n = n %/% j
      if (n == 1) break
    }
    others[i] = others[i]+o
  }
}
twos = cumsum(twos)[-1]
others = cumsum(others)[-1]
(2:305)[twos == others]

3!,  7!, 11!, 13!, 14!, 18!, 20! の 7 個（くそおもしろくもない。なんで 305 までにしたんだ？）

所要時間は 0.053 秒

gmp を使って手抜きをすれば，以下のように簡単に記述できる。所用時間も 0.259 秒となり，ほどほどだ。

library(gmp)
for (i in 2:305) {
  x = table(as.character(factorize(factorialZ(i))))
  if (sum(x)/2 == x["2"]) print(i)
}