Farey sequence: Difference between revisions

=={{header|D}}==

This imports the module from the Arithmetic/Rational task.

{{trans|Python}}

<lang D>import std.stdio, std.algorithm, std.range, arithmetic_rational;

auto farey(in ulong n) {

alias R = RationalT!long;

auto arr = [R(0, 1)];

foreach (immutable k; 1 .. n + 1)

foreach (immutable m; 1 .. k + 1)

arr ~= R(m, k);

return arr.sort().uniq;

}

ulong fareyLen(in ulong n) pure nothrow {

return (n * (n + 3)) / 2 -

iota(2, n + 1).map!(k => fareyLen(n / k)).sum;

}

void main() {

writefln("Farey sequence for order 1 through 11:\n%(%s\n%)",

iota(1, 12).map!farey);

writeln("Number of fractions in the Farey sequence "

"for order 100 through 1_000 by hundreds:\n",

iota(100, 1_001, 100).map!fareyLen);

}</lang>

{{out}}

<pre>Farey sequence for order 1 through 11:

[0, 1]

[0, 1/2, 1]

[0, 1/3, 1/2, 2/3, 1]

[0, 1/4, 1/3, 1/2, 2/3, 3/4, 1]

[0, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1]

[0, 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6, 1]

[0, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 2/5, 3/7, 1/2, 4/7, 3/5, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 1]

[0, 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8, 1]

[0, 1/9, 1/8, 1/7, 1/6, 1/5, 2/9, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 4/9, 1/2, 5/9, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 7/9, 4/5, 5/6, 6/7, 7/8, 8/9, 1]

[0, 1/10, 1/9, 1/8, 1/7, 1/6, 1/5, 2/9, 1/4, 2/7, 3/10, 1/3, 3/8, 2/5, 3/7, 4/9, 1/2, 5/9, 4/7, 3/5, 5/8, 2/3, 7/10, 5/7, 3/4, 7/9, 4/5, 5/6, 6/7, 7/8, 8/9, 9/10, 1]

[0, 1/11, 1/10, 1/9, 1/8, 1/7, 1/6, 2/11, 1/5, 2/9, 1/4, 3/11, 2/7, 3/10, 1/3, 4/11, 3/8, 2/5, 3/7, 4/9, 5/11, 1/2, 6/11, 5/9, 4/7, 3/5, 5/8, 7/11, 2/3, 7/10, 5/7, 8/11, 3/4, 7/9, 4/5, 9/11, 5/6, 6/7, 7/8, 8/9, 9/10, 10/11, 1]

Number of fractions in the Farey sequence for order 100 through 1_000 by hundreds:

[3045, 12233, 27399, 48679, 76117, 109501, 149019, 194751, 246327, 304193]</pre>