CodeIQ 「フィズ・バズ・エクストリーム」問題

CodeIQ の Kawazoe さん出題の問題。
他の方のコードが CodeIQ「フィズ・バズ・エクストリーム」問題みんなのコードにまとまっている。

$p_0, p_1, \cdots, p_K$ を互いに素な2以上の整数とし、f(n,k) を n 以下の正整数のうち $p_0, p_1, \cdots, p_k$ のいずれかの倍数となるものの和とする。このとき
$\Large m=\left\lfloor \frac{n}{p_k} \right\rfloor$
として
$\Large f(n,k) = f(n,k-1) + \frac{1}{2}m(m+1)p_k - f(m,k-1)p_k \hspace{50pt}(k=1,2,\cdots,K)$
が成立する。

例として $K=2,\:p_0=3,\:p_1=5,\:p_2=7$ として f(n,2) を考えると、第1項は 3, 5 のいずれかの倍数の和、第2項は 7 の倍数の和。
第1,2項だけだと、3, 5 のいずれかの倍数で、かつ、7 の倍数であるものを重複して足しているので、第3項でそのぶんを引いている。

この方針で Ruby で書いたのが下のコード。

def f(n, k = @p.size - 1)
  # 下の n == 0 の条件はなくても動くが、あったほうが効率はいい
  return 0 if k < 0 || n == 0
  q = @p[k]
  m = n / q
  f(n, k - 1) + q * (m * (m + 1) / 2 - f(m, k - 1))
end

@p = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31]

p f(10 ** 5), f(10 ** 9)

標準入力から n を入力し、n 以下の正整数のうち 31 以下の奇素数の倍数の和を出力するコードは、Ruby で72バイトで書ける。

f=->n,k=86{k<7?0:f[n,k-=8]-(f[n/=q=832751%k,k]+n*~n/2)*q};p f[gets.to_i]

少し普通に書き直したのが下のもの。

def f(n, k = 86)
  return 0 if k < 7
  q = 832751 % (k - 8)
  m = n / q
  f(n, k - 8) - (f(m, k - 8) + m * (-m - 1) / 2) * q
end
p f(gets.to_i)

3行目で、k は 14, 22, 30, …, 86 の10個の値のいずれかを取り、それに対応して q は 31 以下の奇素数を1回ずつ取る(832751, 86, 8 の組はプログラムで探索して求めた)。
これは、P.J.コーエンの「連続体仮説」で以前に読んだ次の定理*1を思い出して使っている。

任意の非負整数の有限列 $x_0, x_1, \cdots, x_m$ に対して、正整数 n, a, b を適当に取って、
$\Large x_k = n\,\bmod\,(ak+b)\hspace{50pt}(k=0,1,\cdots,m)$
とできる(mod は剰余の2項演算子)。

これ自体は中国剰余定理を使って簡単に証明できるが、数学基礎論という意外な場所で使われていたので印象に残っている。

追記

あんちもん2さんの #フィズバズエクストリーム問題拙解答の解説 #codeiq のゴルフ解。今は小さい素数表を参照してるわけだけど、これをフェルマーの小定理の逆を使って

a=->n,d=1{d<31?a[n,d+=2]-(2**d%d==2?d*(a[n/=d,d]+n*~n/2):0):0}
p a[10**5],a[10**9]

とすると、3バイト長くなるけど*2 *3 素数の上限をもっと伸ばせることに気がついた。
ideone.com で 67 まで行けた。http://ideone.com/9pfafJ
時間が無制限なら理屈上は 337 まで行ける。

*1:コーエンが示しているのは ak+b のところを ak+1 としたより強い定理

*2:2**d%d==2 のところは 2**d%d<3 と1文字けちれるようだ。

*3:あんちもん2さんがこれを修正して元のゴルフ解より短い解を見つけている。