第3問

奇数 $n$ で $f(n)=1$、$f(4)=16$、$n\ne4$ の偶数で $f(n)=2$ とする。これは bonza である:$a$ が奇数なら $f(a)=1$ は何でも割り切る;$a=4$ なら、奇数 $b$ で $b^4\equiv1\pmod{16}$ であること、$b\ne4$ の偶数で $16\mid b^4$ かつ $16\mid2^{16}$ であること、$b=4$ の場合を直接確認することから $16\mid b^4-f(b)^{16}$ が分かる;$a$ が偶数で $a\ne4$ なら、$b$ の各場合の偶奇から $2\mid b^a-f(b)^2$ を確認できる。$f(4)=16=4\cdot4$ なので、この関数は評価 $f(n)\le4n$ がこれ以上改善できないことを示し、$c=4$ が最適であることが分かる。