nCk が偶数となるkを探すプログラム
東京大学の入試で出題された数学の問題で、 2015Cm が偶数となる最小の自然数 m を求めさせる問題が存在します。
普通に解いても面白いですが、プログラムでも簡単に nCk に拡張して書けそうだなと思いましたので、しばらく書いていなかった Haskell で書いてみました。
題
nCk が偶数となる最小の自然数 k を、 n に対してそれぞれ求める。
考察
nCkは次のようにかけます。
これは、次のようにも表せます。
従って、nC(k-1) がわかっていると、 nCk を少しの計算で求められます。
これにより、kを1ずつ増やしながら奇偶の判定を行うことができます。
実装
import Control.Monad maxN = 2020 odds :: [Integer] odds = [1,3..] main :: IO () main = do putStrLn "n: min k [nCk is even]" forM_ (take ((maxN + 1) `div` 2) odds) $ \n -> do putStrLn $ show n ++ ": " ++ show (loop n 1 1) loop :: Integer -> Integer -> Integer -> Integer loop n k t = let nt = t * (n - k + 1) `div` k in if nt `mod` 2 == 0 then k else if n <= k then -1 else loop n (k + 1) nt
(*) の式を使い、loop で kを1ずつ増やしながら奇偶をチェックしています。偶数となったら k を返せば、nに対して、題意のkを得られます。
補足
実は、 nC(k-1) が奇数の場合、nCk の奇偶は (n - k + 1) / k の奇偶に一致するため、 loop 中の t として保存している nCk の値は必要ないのですが、プログラムの意図を分かりやすくするために敢えて書いています。
これも分かり易さのために省略していますが、 nCk = nC(n-k) であることを考えれば、kはnまででなく、n/2まで調べれば良いこともわかります。
結果
上記プログラムでは 2020 までの奇数を選んで n とし、 最小の k を求めています。
出力の最後の方 (2000 ~) は次の通り、
2001: 2 2003: 4 2005: 2 2007: 8 2009: 2 2011: 4 2013: 2 2015: 32 2017: 2 2019: 4
n = 2015 のとき、題を満たす k は 32 です。
見た感じ、n+1 に素因数2をどれだけ含んでいるかが鍵となりそうです。
また、 n = 2^m - 1 のときは、どれも -1 が出力されていました。つまり k 無し。この辺りで問題も作れそうです。