The Haskell code works with arbitrary precision Integer, the C code with a fixed size int.
This is also a work for a library (BTW like Haskell does), you can use gmp or mpfr. This will just add one line to store x/2 in y and avoid its recomputation. You will also have to switch from intset to set. And there one can start to see the difference. The code refactoring will be longer since C doesn't support parametric polymorphism nor operator overloading.
Yes, Haskell is just great, so many things are hard-wired. Even if you use arbitrary precision Integer and appropriate set implementations, there is still no infinite, lazy list that avoids recomputation... I guess your C code either uses some non-standard includes or does not fit on a single page anymore. Just for the record: Using a 64-bit machine (1.5GHz Itanium2) and a well scaling intset (Judy1), (something like) your C code calculates: * within 1GB and in about 25 mins: a_{892163852} = 11314755057 max seen so far: a_{846081651} = 770163004735488 (50 bit) * and within 32GB and in about 22 hours: a_{28515445370} = 165480993670 max seen so far: a_{25880571766} = 32905425960566784 (55 bit) I guess that a Haskell program that verifies these values will depend on an external intset implementation. Or uses another data structure, for example some Set_of_Intervals... /BR, Mirko Rahn