7は孤独な数字

Haskell 30分プログラム

30分プログラム、その162。曰く7は孤独な数字。
理由は、

「1から10の数字を二組に分けて、両方ともグループの数字の積が一緒になる組み合わせはあるか？」という、某作家さんの本に書いてあったエピソードがなぜか忘れられないんです。
ちなみに、答えは「存在しない」です。その理由は、7があるから。
片方は７の倍数になるが、もう片方は絶対にならない。故に7は孤独な数字なんですって。

http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1013042090

ということは「1から10の数字」でなかったら、2つのグループの積が同じになる組合せはたくさんあるのかな?ということで試してみた。

# 「すべてがFになる」から引用しようと思ったのだけれども、どこに置いたか分からなかったのでやめた。

使い方

*Main> productSame [1]
Just ([1],[])

-- 1から10だと、そんな組合せはない
*Main> productSame [1..10]
Nothing

-- 7を抜くと見つかる
*Main> productSame [1,2,3,4,5,6,8,9,10]
Just ([1,8,9,10],[2,3,4,5,6])

確かに7は、孤独だ。

ソースコード

import Control.Monad.List
-- 二つの組を渡されて、その積が同じになるかをチェックする
isSame :: Num a=> [a] -> [a] -> Bool
isSame xs ys = product xs == product ys

-- 2つのグループに分ける
split :: [a] -> [([a],[a])]
split [] = [([],[])]
split (x:xs) = concatMap (\(l,r)->[(x:l,r),(l,x:r)]) $ split xs

-- 整数を二つのグループに分けたとき、その積が同じになるものがあるかを探す
productSame :: Num a => [a] -> Maybe ([a],[a])
productSame xs = let ys = filter (uncurry isSame) $ split xs in
                 if ys == [] then
                     Nothing
                 else
                     Just $ head ys

findSame = do n <- [1..100]
              let x = productSame [1..n]
              guard $ x /= Nothing
              return x

参考