This is an old question, but I happened upon it as part of looking for neat ways to do prime sieving, and thought that I may as well contribute my idea:

The answer is in analyzing the problem, as the above sequence is the opposite of the wheel factorization used in prime sieving to automatically remove 1 and the factors of the first primes as in 2, 3, and 5 (or higher prime factors if desired). These numbers form a 30 element wheel as for example for the (2,3,5) problem posed: 7, 11, 13, 17, 19, 23, 29, 31 with the following sequence 37, 41, 43, and so on. Now the gaps between these numbers starting at 7 are 4, 2, 4, 2, 6, 2, 6 and this pattern repeats infinitely.

Thus, our algorithm can be just "the sequence of 1 plus the sequence of numbers that does not include the sequence of numbers formed starting at 7 and adding these gaps to the last number", or even simpler, the sequence of numbers starting at one and followed by 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30 and then repeating pattern as in 32, 33, and so on. Now notice that the gaps between the above starting from 2 are 1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 1, 2, 2 repeating. Given that, the algorithm to produce the sequence is simple:
1
2
3
4
5
6
let composites235 =
    let allothers =
        let pattern = [| 1;1;1;1;2;1;1;2;2;1;1;2;2;1;1;2;1;1;1;1;2;2 |]
        let inline roll (n,i) = (n + pattern.[i],if i < 21 then i + 1 else 0)
        Seq.unfold (fun (n,i) -> Some(n,roll (n,i))) (2,0)
    seq { yield 1; yield! allothers }
Now the same algorithm could be used for more complex version including all the composites of 2, 3, 5, 7, 11, and so on just by automatically generating the appropriate base pattern as an array and using that as a sequence
By on 6/26/2013 10:25 PM ()
What's the expected result ?

I had a try as follows, but it's still more awkward than in Haskell or OCaml.

1
2
3
4
5
6
7
8
9
10
11
let rec s = seq { yield 1
                  yield! (sn 2) |> combine (sn 3) |> combine (sn 5) }
and sn n = Seq.map (( * ) n) s
and combine sx sy =
  let x, y = Seq.hd sx, Seq.hd sy
  let x, sx, sy =
    if x < y then x, Seq.skip 1 sx, sy
    elif x > y then y, sx, Seq.skip 1 sy
    else x, Seq.skip 1 sx, Seq.skip 1 sy
  seq { yield x
        yield! combine sx sy }


By on 12/10/2008 12:35 PM ()
My direct attempt to solve that problem hangs up fsi after first 10-15 values :( (stack overflow?)

1
2
3
4
5
6
7
8
9
10
11
let rec f =
  seq {
    yield 1
    for i in 1..100 do
      if Seq.exists (fun a -> a = i) f then
        yield 2*i
        yield 3*i
        yield 5*i
  }

Seq.take 100 f |> Seq.iter (fun i -> printf "%d " i)


By on 12/11/2008 5:40 AM ()
>> Seq.exists (fun a -> a = i) f

Would this line keep on consuming f ? May be you need a takewhile or something like that.

I believe this is another case where the laziness of haskell fits more nicely. Though brian's solution is pretty much the same, other than the need for guarding empty sequence.

That brings up another interesting point.

In haskell, one can say

combine [] xs = xs

combine xs [] = xs

combine x:xs y:ys = ...

But that needs to be coded into the combine function f# making this kind of 'more guard' less 'declarative' in nature than haskell.

Is this style of coding possible in F# ?
By on 12/11/2008 8:01 PM ()
I have encountered this exact same problem before, years ago when working on FC++, it seems like a pretty famous problem.

Below is one solution, you can probably shorten it even a little more.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#light

let rec combine (LazyList.Cons(h1,t1) as ll1) (LazyList.Cons(h2,t2) as ll2) =
    if h1 = h2 then
        LazyList.consf h1 (fun() -> combine t1 t2)
    elif h1 < h2 then
        LazyList.consf h1 (fun() -> combine t1 ll2)
    else
        LazyList.consf h2 (fun() -> combine t2 ll1)
                    
let rec ll = LazyList.consf 1 (fun() ->
    let twos = LazyList.map (fun n -> 2*n) ll
    let threes = LazyList.map (fun n -> 3*n) ll
    let fives = LazyList.map (fun n -> 5*n) ll
    combine (combine twos threes) fives)

for x in LazyList.take 20 ll do
    printfn "%d" x
By on 12/7/2008 10:56 PM ()
This may be a dumb question, but why do we not have to worry about combine ever being called with an empty list? It seems like you would eventually end up with a MatchFailureException.

Edit: BTW, it actually is a pretty famous problem. read about its history here: [link:en.wikipedia.org]
By on 12/8/2008 6:17 AM ()
IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us
Built with WebSharper