defmodule Sequences do
@doc ~S"""
Natural Integers (Non-Negative Integers).
## Examples
# take 1..10
iex> Sequences.nats |> Enum.take(10)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
"""
def nats do
&nats(1, &1, &2)
end
defp nats(_, {:halt, acc}, _fun), do: {:halted, acc}
defp nats(n, {:suspend, acc}, fun), do: {:suspended, acc, &nats(n, &1, fun)}
defp nats(n, {:cont, acc}, fun), do: nats(n + 1, fun.(n, acc), fun)
@doc ~S"""
Fibonacci Sequence ([1, 1, 2, 3, ...]).
## Examples
# take first 10 Fibonacci Numbers.
iex> Sequences.fibs |> Enum.take(10)
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
# The 100th Fibonacci Number
iex> Sequences.fibs |> Enum.at(99)
354224848179261915075
"""
def fibs do
&fibs({1, 1}, &1, &2)
end
defp fibs(_, {:halt, acc}, _fun), do: {:halted, acc}
defp fibs(v, {:suspend, acc}, fun), do: {:suspended, acc, &fibs(v, &1, fun)}
defp fibs({a, b}, {:cont, acc}, fun), do: fibs({b, a + b}, fun.(a, acc), fun)
@doc ~S"""
Primes.
## Examples
# First 20 primes
iex> Sequences.primes |> Enum.take(20)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
# The 10000th prime
iex> Sequences.primes |> Enum.at(9999)
104729
"""
def primes do
&primes(2, &1, &2)
end
defp primes(_, {:halt, acc}, _fun), do: {:halted, acc}
defp primes(v, {:suspend, acc}, fun) do
{:suspended, acc, &primes(v, &1, fun)}
end
defp primes(2, {:cont, acc}, fun) do
primes(3, fun.(2, acc), fun)
end
defp primes(3, {:cont, acc}, fun) do
primes({%{}, 5, 2, nil}, fun.(3, acc), fun)
end
defp primes({h, p, d, nil}, {:cont, acc}, fun) do
m = next_m(h, p, p, 4, true)
n = p + d
next_h = h |> Map.put(m, p)
primes({next_h, n, 6 - d, Map.get(next_h, n)}, fun.(p, acc), fun)
end
defp primes({h, q, d, b}, {:cont, _} = acc, fun) do
k = if rem(q + b, 3) == 0, do: 2, else: 4
m = next_m(h, b, q, k, true)
n = q + d
next_h = h |> Map.put(m, b) |> Map.delete(q)
primes({next_h, n, 6 - d, Map.get(next_h, n)}, acc, fun)
end
defp next_m(_, _, m, _, false), do: m
defp next_m(h, n, pre_m, k, true) do
m = pre_m + n * k
next_m(h, n, m, 6 - k, Map.has_key?(h, m))
end
def run do
IO.
puts "Sequences.nats |> Enum.take(10)" Sequences.nats |> Enum.take(10) |> IO.inspect
IO.
puts "Sequences.fibs |> Enum.take(10)" Sequences.fibs |> Enum.take(10) |> IO.inspect
IO.
puts "Sequences.fibs |> Enum.at(99)" Sequences.fibs |> Enum.at(99) |> IO.inspect
IO.
puts "Sequences.primes |> Enum.take(20)" Sequences.primes |> Enum.take(20) |> IO.inspect
IO.
puts "Sequences.primes |> Enum.at(9999)" Sequences.primes |> Enum.at(9999) |> IO.inspect
end
end
Sequences.run
ZGVmbW9kdWxlIFNlcXVlbmNlcyBkbwogIEBkb2MgflMiIiIKICBOYXR1cmFsIEludGVnZXJzIChOb24tTmVnYXRpdmUgSW50ZWdlcnMpLgoKICAjIyBFeGFtcGxlcwogIAogICAgIyB0YWtlIDEuLjEwCiAgICBpZXg+IFNlcXVlbmNlcy5uYXRzIHw+IEVudW0udGFrZSgxMCkKICAgIFsxLCAyLCAzLCA0LCA1LCA2LCA3LCA4LCA5LCAxMF0KICAiIiIKICBkZWYgbmF0cyBkbwogICAgJm5hdHMoMSwgJjEsICYyKQogIGVuZAoKICBkZWZwIG5hdHMoXywgezpoYWx0LCBhY2N9LCBfZnVuKSwgZG86IHs6aGFsdGVkLCBhY2N9CiAgZGVmcCBuYXRzKG4sIHs6c3VzcGVuZCwgYWNjfSwgZnVuKSwgZG86IHs6c3VzcGVuZGVkLCBhY2MsICZuYXRzKG4sICYxLCBmdW4pfQogIGRlZnAgbmF0cyhuLCB7OmNvbnQsIGFjY30sIGZ1biksIGRvOiBuYXRzKG4gKyAxLCBmdW4uKG4sIGFjYyksIGZ1bikKCiAgQGRvYyB+UyIiIgogIEZpYm9uYWNjaSBTZXF1ZW5jZSAoWzEsIDEsIDIsIDMsIC4uLl0pLgoKICAjIyBFeGFtcGxlcwogIAogICAgIyB0YWtlIGZpcnN0IDEwIEZpYm9uYWNjaSBOdW1iZXJzLgogICAgaWV4PiBTZXF1ZW5jZXMuZmlicyB8PiBFbnVtLnRha2UoMTApCiAgICBbMSwgMSwgMiwgMywgNSwgOCwgMTMsIDIxLCAzNCwgNTVdCgogICAgIyBUaGUgMTAwdGggRmlib25hY2NpIE51bWJlcgogICAgaWV4PiBTZXF1ZW5jZXMuZmlicyB8PiBFbnVtLmF0KDk5KQogICAgMzU0MjI0ODQ4MTc5MjYxOTE1MDc1CiAgIiIiCiAgZGVmIGZpYnMgZG8KICAgICZmaWJzKHsxLCAxfSwgJjEsICYyKQogIGVuZAoKICBkZWZwIGZpYnMoXywgezpoYWx0LCBhY2N9LCBfZnVuKSwgZG86IHs6aGFsdGVkLCBhY2N9CiAgZGVmcCBmaWJzKHYsIHs6c3VzcGVuZCwgYWNjfSwgZnVuKSwgZG86IHs6c3VzcGVuZGVkLCBhY2MsICZmaWJzKHYsICYxLCBmdW4pfQogIGRlZnAgZmlicyh7YSwgYn0sIHs6Y29udCwgYWNjfSwgZnVuKSwgZG86IGZpYnMoe2IsIGEgKyBifSwgZnVuLihhLCBhY2MpLCBmdW4pCgogIEBkb2MgflMiIiIKICBQcmltZXMuCgogICMjIEV4YW1wbGVzCiAgCiAgICAjIEZpcnN0IDIwIHByaW1lcwogICAgaWV4PiBTZXF1ZW5jZXMucHJpbWVzIHw+IEVudW0udGFrZSgyMCkKICAgIFsyLCAzLCA1LCA3LCAxMSwgMTMsIDE3LCAxOSwgMjMsIDI5LCAzMSwgMzcsIDQxLCA0MywgNDcsIDUzLCA1OSwgNjEsIDY3LCA3MV0KICAKICAgICMgVGhlIDEwMDAwdGggcHJpbWUKICAgIGlleD4gU2VxdWVuY2VzLnByaW1lcyB8PiBFbnVtLmF0KDk5OTkpCiAgICAxMDQ3MjkKICAiIiIKICBkZWYgcHJpbWVzIGRvCiAgICAmcHJpbWVzKDIsICYxLCAmMikKICBlbmQKCiAgZGVmcCBwcmltZXMoXywgezpoYWx0LCBhY2N9LCBfZnVuKSwgZG86IHs6aGFsdGVkLCBhY2N9CiAgZGVmcCBwcmltZXModiwgezpzdXNwZW5kLCBhY2N9LCBmdW4pIGRvCiAgICB7OnN1c3BlbmRlZCwgYWNjLCAmcHJpbWVzKHYsICYxLCBmdW4pfQogIGVuZAogIGRlZnAgcHJpbWVzKDIsIHs6Y29udCwgYWNjfSwgZnVuKSBkbwogICAgcHJpbWVzKDMsIGZ1bi4oMiwgYWNjKSwgZnVuKQogIGVuZAogIGRlZnAgcHJpbWVzKDMsIHs6Y29udCwgYWNjfSwgZnVuKSBkbwogICAgcHJpbWVzKHsle30sIDUsIDIsIG5pbH0sIGZ1bi4oMywgYWNjKSwgZnVuKQogIGVuZAogIGRlZnAgcHJpbWVzKHtoLCBwLCBkLCBuaWx9LCB7OmNvbnQsIGFjY30sIGZ1bikgZG8KICAgIG0gPSBuZXh0X20oaCwgcCwgcCwgNCwgdHJ1ZSkKICAgIG4gPSBwICsgZAogICAgbmV4dF9oID0gaCB8PiBNYXAucHV0KG0sIHApCiAgICBwcmltZXMoe25leHRfaCwgbiwgNiAtIGQsIE1hcC5nZXQobmV4dF9oLCBuKX0sIGZ1bi4ocCwgYWNjKSwgZnVuKQogIGVuZAogIGRlZnAgcHJpbWVzKHtoLCBxLCBkLCBifSwgezpjb250LCBffSA9IGFjYywgZnVuKSBkbwogICAgayA9IGlmIHJlbShxICsgYiwgMykgPT0gMCwgZG86IDIsIGVsc2U6IDQKICAgIG0gPSBuZXh0X20oaCwgYiwgcSwgaywgdHJ1ZSkKICAgIG4gPSBxICsgZAogICAgbmV4dF9oID0gaCB8PiBNYXAucHV0KG0sIGIpIHw+IE1hcC5kZWxldGUocSkKICAgIHByaW1lcyh7bmV4dF9oLCBuLCA2IC0gZCwgTWFwLmdldChuZXh0X2gsIG4pfSwgYWNjLCBmdW4pCiAgZW5kCgogIGRlZnAgbmV4dF9tKF8sIF8sIG0sIF8sIGZhbHNlKSwgZG86IG0KICBkZWZwIG5leHRfbShoLCBuLCBwcmVfbSwgaywgdHJ1ZSkgZG8KICAgIG0gPSBwcmVfbSArIG4gKiBrCiAgICBuZXh0X20oaCwgbiwgbSwgNiAtIGssIE1hcC5oYXNfa2V5PyhoLCBtKSkKICBlbmQKCiAgZGVmIHJ1biBkbwogICAgSU8ucHV0cyAiU2VxdWVuY2VzLm5hdHMgfD4gRW51bS50YWtlKDEwKSIKICAgIFNlcXVlbmNlcy5uYXRzIHw+IEVudW0udGFrZSgxMCkgfD4gSU8uaW5zcGVjdAogICAgSU8ucHV0cyAiU2VxdWVuY2VzLmZpYnMgfD4gRW51bS50YWtlKDEwKSIKICAgIFNlcXVlbmNlcy5maWJzIHw+IEVudW0udGFrZSgxMCkgfD4gSU8uaW5zcGVjdAogICAgSU8ucHV0cyAiU2VxdWVuY2VzLmZpYnMgfD4gRW51bS5hdCg5OSkiCiAgICBTZXF1ZW5jZXMuZmlicyB8PiBFbnVtLmF0KDk5KSB8PiBJTy5pbnNwZWN0CiAgICBJTy5wdXRzICJTZXF1ZW5jZXMucHJpbWVzIHw+IEVudW0udGFrZSgyMCkiCiAgICBTZXF1ZW5jZXMucHJpbWVzIHw+IEVudW0udGFrZSgyMCkgfD4gSU8uaW5zcGVjdAogICAgSU8ucHV0cyAiU2VxdWVuY2VzLnByaW1lcyB8PiBFbnVtLmF0KDk5OTkpIgogICAgU2VxdWVuY2VzLnByaW1lcyB8PiBFbnVtLmF0KDk5OTkpIHw+IElPLmluc3BlY3QKICBlbmQKZW5kCgpTZXF1ZW5jZXMucnVu