正木です。

[ruby-math:00962] の定理を一般化してみました。


【定理】 m, x, k を正の自然数で

        2|k|x

        k**2 / 2 <= a          (m == 2 の時)

        (m - 1) * k**2 <= a    (m > 2 の時)

    とするとき、

        N(x) = x + (a**m / x**(m - 1) - x) / m

    に対し次が成り立つ。

        -1 < x/k - a/k <= 1 ならば 0 <= N(x) - a < 1

【系】同じ前提条件で

        0 <= x/k - [[a**m/k**m]**(1/m)] <= 1 ならば 0 <= [N(x)] - [a] <= 1.


------
定理の証明

N(x) - a = (x - a)**2 / (m * x**(m - 1))
 * (0..m-2).collect{|k| (k + 1) * x**k * a**(m - k - 2)}.sum

<= (m - 1)/2 * (x - a)**2 * max(a, x)**(m - 2) / x**(m - 1)

となることを使って m > 2 の場合だけ証明します。

x > a の場合

0 <= N(x) - a <= (m - 1) * k**2 / (2 * x) <= a / (2 * x) < 1/2

x <= a の場合

(m -1) * k**2 <= x

(左辺と x は k の倍数で、 左辺 <= a < x + k )

より

0 <= N(x) - a < ((m - 1) * k**2 / x) * (a / x)**(m - 2) / 2

 <= (a / x)**(m - 2) / 2
                                # a - k < x

 <  (1 + k/(a - k))**(m - 2) / 2
                                # (m - 1) * k**2 <= a

 <= (1 + 1 / (k * (m - 1) - 1)))**(m - 2) / 2

 <= (1 + 1 / (2 * (m - 1) - 1)))**(m - 2) / 2

 <  (1 + 1 / (2 * (m - 2)))**(m - 2) / 2

 <  exp(1/2) / 2

 < 1

Q.E.D.

Integer#iroot の改良版です:

-----
class Integer
  def irootB(m)
    raise "argument is negative" if self < 0
    return 0 if self == 0
    n = (self >> m).irootB(m) << 1
    n1 = n | 1
    (n1 ** m > self)? n : n1
  end

# Log2Ceil=Function{"|m| n = m.ilog2;(m == 1<<n)? n : n + 1"}

  def iroot_ini(m)
    return irootB(m) if kind_of?(Fixnum)
    i = ilog2
    return 1 if i < m
#   n = Log2Ceil[m - 1]
    n = (m - 1).ilog2
    n += 1 if m - 1 > 1 << n
    j = (i.div(m) - n) >> 1
    return irootB(m) if j <= 0
    x = (self >> j * m).iroot_ini(m)
    y = (self >> j * (m - 1)).div(x ** (m - 1))
    x = x << j
    x + (y - x).div(m)
  end

  def iroot(m)
    raise "second argument is not positive" if m <= 0
    raise "argument is negative" if self < 0
    return irootB(m) if kind_of?(Fixnum)
    return self if m == 1
    return isqrt if m == 2
    return isqrt.iroot(m >> 1) if m & 1 == 0
    return 1 if ilog2 < m
    x = iroot_ini(m)
    if m == 3
      (x > div(x ** (m - 1))) ? (x - 1) : x
    else
      (x ** m > self) ? (x - 1) : x
    end
  end
end
-----