160402

Ruby


Alternating factorial(1)

昨日以下の問題を見かける。
http://integers.hatenablog.com/entry/2016/04/01/000130

その中の問２を解説してみる。

結論から言えば、実は、常にpn > n が成り立つわけでない。

https://en.wikipedia.org/wiki/Alternating_factorial
に載っているように、
3612702! - 3612701! + 3612700! - 3612699! + … ≡ 0 mod 3612703
より、n ≧ 3612702 のとき、
n! - (n - 1)! + (n - 2)! - … ≡ 0 mod 3612703
よって、3612703 ≧ pn となる。
したがって、n ≧ 3612703 のとき、
n ≧ pn となる。

念のため、
3612702! - 3612701! + 3612700! - 3612699! + … ≡ 0 mod 3612703
を確認しておく。

def af(n, mod)
  a = 0
  f = 1
  (1..n).each{|i|
    f *= i
    f %= mod
    a = f - a
    a %= mod
    p [i, a] if i <= 10 || i > 3612690
  }
end

mod = 3612703
af(3612750, mod)

出力結果
[1, 1]
[2, 1]
[3, 5]
[4, 19]
[5, 101]
[6, 619]
[7, 4421]
[8, 35899]
[9, 326981]
[10, 3301819]
[3612691, 2384440]
[3612692, 1884506]
[3612693, 2391173]
[3612694, 2480152]
[3612695, 1901684]
[3612696, 3552494]
[3612697, 3462171]
[3612698, 1204237]
[3612699, 1806349]
[3612700, 2]
[3612701, 3612702]
[3612702, 0]
[3612703, 0]
[3612704, 0]
[3612705, 0]
[3612706, 0]
[3612707, 0]
[3612708, 0]
[3612709, 0]
[3612710, 0]
[3612711, 0]
[3612712, 0]
[3612713, 0]
[3612714, 0]
[3612715, 0]
[3612716, 0]
[3612717, 0]
[3612718, 0]
[3612719, 0]
[3612720, 0]
[3612721, 0]
[3612722, 0]
[3612723, 0]
[3612724, 0]
[3612725, 0]
[3612726, 0]
[3612727, 0]
[3612728, 0]
[3612729, 0]
[3612730, 0]
[3612731, 0]
[3612732, 0]
[3612733, 0]
[3612734, 0]
[3612735, 0]
[3612736, 0]
[3612737, 0]
[3612738, 0]
[3612739, 0]
[3612740, 0]
[3612741, 0]
[3612742, 0]
[3612743, 0]
[3612744, 0]
[3612745, 0]
[3612746, 0]
[3612747, 0]
[3612748, 0]
[3612749, 0]
[3612750, 0]