smith number

To write a haskell program to find the smith number is not difficult, but finding a efficient algorithm is quite a challenge. The key problem are the sparse smith numbers and no efficient algorithm has been found for factorization.

module Main where

ld n = ldf 2 n
    where ldf k n | n `mod` k == 0 = k
                  | k^2 > n = n
                  | otherwise = ldf (k+1) n

prime n = ld n == n

factorization 1 = []
factorization n = p : (factorization (div n p) )
    where p = ld n

sumN n = sum (decompose n)
    where decompose 0 = []
          decompose n = n `mod` 10 : (decompose (n `div` 10))

nextSmith n = head $ filter smith [n+1..]
    where smith n = not (prime n) && sumN n == (sum . (map sumN) . factorization) n



Fill in your details below or click an icon to log in: 徽标

You are commenting using your account. Log Out /  更改 )

Google photo

You are commenting using your Google account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s