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:

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:

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

What's the expected result ?

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

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

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 }

My direct attempt to solve that problem hangs up fsi after first 10-15 values :( (stack overflow?)

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)

>> 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# ?

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# ?

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.

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

#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

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]

Edit: BTW, it actually is a pretty famous problem. read about its history here: [link:en.wikipedia.org]

# Topic tags

- f# × 3672
- compiler × 264
- functional × 201
- websharper × 133
- c# × 119
- classes × 96
- web × 95
- book × 84
- .net × 82
- async × 72
- parallel × 43
- server × 43
- parsing × 41
- testing × 41
- asynchronous × 30
- monad × 28
- ocaml × 27
- haskell × 26
- tutorial × 26
- html × 22
- workflows × 22
- linq × 21
- fpish × 19
- introduction × 19
- silverlight × 19
- wpf × 19
- collections × 14
- pipeline × 14
- templates × 12
- monads × 11
- opinion × 10
- reactive × 10
- plugin × 9
- scheme × 9
- sitelets × 9
- solid × 9
- basics × 8
- concurrent × 8
- deployment × 8
- how-to × 8
- javascript × 8
- python × 8
- complexity × 7
- jquery × 7
- lisp × 6
- real-world × 6
- scala × 6
- workshop × 6
- xaml × 6
- conference × 5
- dsl × 5
- java × 5
- metaprogramming × 5
- ml × 5
- visual studio × 5
- formlets × 4
- fsi × 4
- lift × 4
- sql × 4
- teaching × 4
- alt.net × 3
- aml × 3
- enhancement × 3
- erlang × 3
- list × 3
- reflection × 3
- type provider × 3
- blog × 2
- clojure × 2
- compilation × 2
- computation expressions × 2
- corporate × 2
- courses × 2
- cufp × 2
- enterprise × 2
- entity framework × 2
- events × 2
- f# interactive × 2
- fsc × 2
- google maps × 2
- html5 × 2
- http × 2
- interactive × 2
- interface × 2
- iphone × 2
- iteratee × 2
- jobs × 2
- kendo × 2
- keynote × 2
- mvc × 2
- numeric × 2
- obfuscation × 2
- oop × 2
- packaging × 2
- pattern matching × 2
- performance × 2
- piglet × 2
- pipelines × 2
- rx × 2
- script × 2
- seq × 2
- sockets × 2
- stm × 2
- tcp × 2
- trie × 2
- type × 2
- typescript × 2
- xna × 2
- zh × 2
- .net interop × 1
- 2012 × 1
- abstract class × 1
- accumulator × 1
- active pattern × 1
- addin × 1
- agents × 1
- agile × 1
- alter session × 1
- android × 1
- anonymous object × 1
- appcelerator × 1
- architecture × 1
- array × 1
- arrays × 1
- asp.net 4.5 × 1
- asp.net mvc × 1
- asp.net mvc 4 × 1
- asp.net web api × 1
- aspnet × 1
- ast × 1
- b-tree × 1
- badimageformatexception × 1
- batching × 1
- bistro × 1
- bootstrap × 1
- bug × 1
- bundle × 1
- camtasia studio × 1
- canvas × 1
- class × 1
- client × 1
- clojurescript × 1
- closures × 1
- cloud × 1
- cms × 1
- coding diacritics × 1
- color highlighting × 1
- combinator × 1
- confirm × 1
- constructor × 1
- continuation-passing style × 1
- coords × 1
- coursera × 1
- csla × 1
- css × 1
- current_schema × 1
- data × 1
- database × 1
- declarative × 1
- delete × 1
- dhtmlx × 1
- discriminated union × 1
- distance × 1
- docs × 1
- documentation × 1
- dol × 1
- dom × 1
- domain × 1
- du × 1
- duf-101 × 1
- eclipse × 1
- edsl × 1
- em algorithm × 1
- emacs × 1
- emotion × 1
- error × 1
- etw × 1
- euclidean × 1
- event × 1
- example × 1
- examples × 1
- ext js × 1
- extension methods × 1
- extra × 1
- facet pattern × 1
- fantomas × 1
- fear × 1
- float × 1
- flowlet × 1
- fp × 1
- frank × 1
- fsdoc × 1
- fsharp.core × 1
- fsharp.powerpack × 1
- fsharpx × 1
- function × 1
- functional style × 1
- games × 1
- gc × 1
- generic × 1
- geometry × 1
- getlastwin32error × 1
- google × 1
- group × 1
- hash × 1
- hello world example × 1
- history × 1
- hosting × 1
- httpcontext × 1
- https × 1
- hubfs × 1
- ie 8 × 1
- if-doc × 1
- inheritance × 1
- installer × 1
- interpreter × 1
- io × 1
- iobservable × 1
- ios × 1
- ipad × 1
- issue × 1
- kendochart × 1
- kendoui × 1
- learning × 1
- license × 1
- licensing × 1
- macro × 1
- macros × 1
- maps × 1
- markup × 1
- marshal × 1
- math × 1
- message × 1
- metro style × 1
- micro orm × 1
- minimum-requirements × 1
- multidimensional × 1
- multiline × 1
- multithreading × 1
- mysql × 1
- mysqlclient × 1
- nancy × 1
- native × 1
- nested × 1
- nested loops × 1
- node × 1
- object relation mapper × 1
- object-oriented × 1
- offline × 1
- om × 1
- option × 1
- orm × 1
- osx × 1
- owin × 1
- paper × 1
- parameter × 1
- persistent data structure × 1
- phonegap × 1
- piglets × 1
- pola × 1
- powerpack × 1
- prefix tree × 1
- principle of least authority × 1
- programming × 1
- projekt_feladat × 1
- protected × 1
- provider × 1
- ptvs × 1
- quant × 1
- quotations × 1
- range × 1
- raphael × 1
- razor × 1
- rc × 1
- reactjs × 1
- real-time × 1
- reference × 1
- rest × 1
- restful × 1
- round table × 1
- runtime × 1
- scriptcs × 1
- scripting × 1
- service × 1
- session-state × 1
- sitelet × 1
- sitelet website × 1
- sqlentityconnection × 1
- standards × 1
- stickynotes × 1
- stress × 1
- strong name × 1
- structures × 1
- svg × 1
- tdd × 1
- template × 1
- text parsing × 1
- time travel × 1
- tracing × 1
- tsunamiide × 1
- type inference × 1
- type providers × 1
- typeprovider × 1
- upload × 1
- vb × 1
- vb.net × 1
- vector × 1
- visual f# × 1
- visual studio 11 × 1
- visual studio 2012 × 1
- visual studio shell × 1
- visualstudio × 1
- web api × 1
- webapi × 1
- windows 7 × 1
- windows 8 × 1
- windows-phone × 1
- winrt × 1
- xml × 1
- yield × 1
- zarovizsga × 1

Copyright (c) 2011-2012 IntelliFactory. All rights reserved. Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us |
Built with WebSharper |

Write a program that generates the following sequence:

a) 1 is in the sequence

b) An element j is in the sequence if and only if j=2n, 3n, or 5n, where n is in the sequence.

At first I thought this could be represented using a clever sequence expression, but then I decided it can't. So next I wrote a recursive function that uses Set.fold_left to add doubles, triples, and quintuples of elements to the set, and a recursion to build the entire sequence. But since there is no laziness involved the function to build the sequence will never terminate. I still haven't fully wrapped my head around the lazy evaluation or use of the y combinator, but my gut tells me they can come in handy here and this can somehow be represented by a seq<'a>. Anyone care to shed some light?

The solution isn't difficult using more complicated methods, but I want to see if there's a two or three liner that can do this elegantly with laziness.

Thanks