151108(5)

Ruby


Polite number(5)

f(10 ** i) を調べてみた。

require 'prime'

def power(a, n)
  return 1 if n == 0
  k = power(a, n >> 1)
  k *= k
  return k if n & 1 == 0
  return k * a
end

def f(n)
  return 0 if n == 1
  factor = Prime.prime_division(n)
  o_factor = factor.clone
  n1 = 1
  if o_factor[0][0] == 2
    n1 = power(2, o_factor[0][1])
    o_factor.shift
  end
  a0, a1 = 1, 1
  o_factor.each{|i|
    p, q = i[0], i[1]
    a0 *= q + 1
    a1 *= power(p, q + 1) / (p - 1)
  }
  ((2 * n1 + 1) * a1 - a0) / 2 - n
end

(0..25).each{|i| p f(10 ** i)}

出力結果
0
4
38
324
2884
26942
259746
2548792
25244072
251220570
2506103254
25030517060
250152586860
2500762937398
25003814693162
250019073478128
2500095367415248
25000476837125426
250002384185725470
2500011920928823996
25000059604644513236
250000298023223352654
2500001490116118336178
25000007450580594826664
250000037252902980424824
2500000186264514914707082

n = 10 ** i のとき
f(n) = (2^i + 1 / 2) (5^(i + 1) - 1) / (5 - 1) - (i + 1) / 2 - n
より、
f(n) ≒ 2^i 5^(i + 1) / 4 - n = n / 4
となっている。