160304

Ruby

Ramanujan prime(3)

pi(n) - pi(floor(n / 2)) には面白い性質がある。

2! = 2 のunitary prime divisor は2 の1個。

3! = 2 × 3 のunitary prime divisor は2, 3 の2個。

4! = 2^3 × 3 のunitary prime divisor は3 の1個。

5! = 2^3 × 3 × 5 のunitary prime divisor は3, 5 の2個。

6! = 2^4 × 3^2 × 5 のunitary prime divisor は5 の1個。

…

となるが、一般に

n! のunitary prime divisor の個数はpi(n) - pi(floor(n / 2))

となる。

オンライン整数列大辞典の
A056171（http://oeis.org/A056171/list）
と比較し、答え合わせしてみる。

def A056171(n)
  a = Array.new(n + 1, 1)
  l = 0
  a[0] = l
  a[1] = l
  ary = [0, 0]
  i = 2

  while i * i <= n
    # 素数のとき
    if a[i] == 1
      l += 1
      j = i + i
      while j <= n
        a[j] = 0
        j += i
      end
    end
    a[i] = l
    ary << l - a[i / 2]
    i += 1
  end

  while i <= n
    # 素数のとき
    if a[i] == 1
      l += 1
    end
    a[i] = l
    ary << l - a[i / 2]
    i += 1
  end
  ary[1..-1]
end
ary = A056171(98)

# OEIS A056171のデータ
ary0 =
[0,1,2,1,2,1,2,2,2,1,2,2,3,2,2,2,3,3,4,4,4,3,4,4,
 4,3,3,3,4,4,5,5,5,4,4,4,5,4,4,4,5,5,6,6,6,5,6,6,6,
 6,6,6,7,7,7,7,7,6,7,7,8,7,7,7,7,7,8,8,8,8,9,9,10,
 9,9,9,9,9,10,10,10,9,10,10,10,9,9,9,10,10,10,10,
 10,9,9,9,10,10]
# 一致の確認
p ary == ary0