Ulam numbers

From Rosetta Code
Revision as of 04:41, 1 December 2020 by rosettacode>Rds (Created page with "With the following initial conditions: <big><big> u<sub>1</sub> = 1 </big></big> <big><big> u<sub>2</sub> = 2 </big></big> we define the n-th Ulam number u<sub>n...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

With the following initial conditions:

      u1 = 1 
      u2 = 2 

we define the n-th Ulam number un as the number such that is greater than un-1 and uniquely written as a sum of two different Ulam numbers ui (<n) and uj (<n).

Task

Write a function to generate the n-th Ulam number.

References

Haskell

Lazy List

<lang haskell> ulam

 :: Integral i =>
    Int -> i

ulam 1 = 1 ulam 2 = 2 ulam n

 | n > 2 = ulams !! (n-1)

ulams

 :: Integral n =>
    [n]

ulams = 1:2:(nexts [2,1]) nexts us = u: (nexts (u:us))

 where
   n = length us
   [u] = head . filter isSingleton . group . sort  $ 
           [v | i <- [0 .. n-2], j <- [i+1 .. n-1] 
              , let s = us !! i
              , let t = us !! j
              , let v = s+t
              , v > head us
              ]

isSingleton :: [a] -> Bool isSingleton as

 | length as == 1 = True
 | otherwise      = False